Ciência da Computação Teórica

Parte: Ciência da Computação · Capítulo: Ciência da Computação Teórica · Edição: 2026-07-12
Palavras-chave: autômatos, complexidade, computabilidade, algoritmos, lógica
Glossário: turing machine, P vs NP, algoritmo, decidibilidade — veja GLOSSÁRIO

Em resumo

A ciência da computação teórica estuda o que pode ser computado, quão difícil isso é, e como prová-lo.
Modelos (autômatos, máquinas de Turing) fundamentam as classes de complexidade.
Lógica e sistemas de prova sustentam a verificação — inclusive de procedimentos de que dependemos em sistemas de conhecimento.

Referências online (verificadas)

Instantâneos offline (proteção contra links quebrados)

Instantâneo offline omitido nesta edição web. Instantâneo offline · Theoretical computer science · https://en.wikipedia.org/wiki/Theoretical_computer_science · recuperado em 2026-07-12

Theoretical computer science

Instantâneo offline omitido nesta edição web. Instantâneo offline · Computational complexity theory · https://en.wikipedia.org/wiki/Computational_complexity_theory · recuperado em 2026-07-12

Computational complexity theory

Instantâneo offline omitido nesta edição web. Instantâneo offline · Turing machine · https://en.wikipedia.org/wiki/Turing_machine · recuperado em 2026-07-12

Turing machine

Este capítulo mapeia a lógica da computação: o que pode ser computado, com quais recursos, e como isso pode ser provado. É um índice do campo — de máquinas abstratas à complexidade, aos algoritmos, à lógica e aos métodos formais — e não um livro-texto.

Aplicações na Keyne Digital Assets

Modelos formais, classes de complexidade e sistemas de prova são a linguagem que usamos quando perguntamos se um procedimento termina, se uma tabela de regras é conservativa, ou se uma consulta pode ser verificada em vez de apenas executada. Este capítulo orienta esse trabalho. Não é a afirmação de que o Situation Monitor implementa cada modelo listado aqui.

Índice Definitivo de Ciência da Computação Teórica (TCS)

1. Teoria da Computação & Autômatos

A análise de dispositivos de computação abstratos e a “Gramática” do cálculo.

Autômatos finitos Deterministas (AFD), Não Deterministas (NFA), e Máquinas de Mealy/Moore.
Linguagens Regulares: Expressões Regulares, lema do bombeamento para linguagens regulares, e Teorema de Myhill-Nerode.
Linguagens Contextuais: Máquinas de Pilha (PDA), Forma Normal de Chomsky, e Forma Normal de Greibach.
Máquinas de Turing (TM):
Máquinas de Turing com várias fitas, Não Deterministas, e Universal.
Problema da parada e Teorema de Rice.
Teorema da Chomsky.
Hierarquia de gramáticas Formais: Classificação de gramáticas formais (Tipo 0 a Tipo 3).

2. Teoria da Complexidade Computacional

Classificar problemas pelos recursos (tempo, espaço, energia) necessários para resolvê-los.

Classes Fundamentais: P, NP, co-NP, e a questão $P \stackrel{?}{=} NP$ .
Hardness & Completeness: NP-Completeness (Teorema de Cook-Levin) e Reduções Polinomial.
Hierarquia de espaço: L (Espaço Logarítmico), PSPACE, e Teorema de Savitch ( $NPSPACE = PSPACE$ ).
Complexidade Probabilística: BPP (Tempo Polinomial de Erro Bounded), RP, e ZPP.
Complexidade Quântica: BQP (Tempo Polinomial de Erro Quântico) e sua relação com P e NP.
Provas Interativas: IP = PSPACE, e Teorema da PCP (provas verificáveis probabilisticamente).
Complexidade Circuitária: Circuitos Booleanos, Limites de Shannon, e a Hierarchy $NC$.

O desenho de procedimentos eficientes para resolver problemas específicos.

Paradigmas Fundamentais: algoritmos gulosos, dividir para conquistar, programação dinâmica (DP).
Algoritmos de Grafos:
Rastreamento de Caminho: Dijkstra, A*, Bellman-Ford, Floyd-Warshall.
Conexão: Tarjan’s SCC, Fluxo de Redes (Ford-Fulkerson, Max-flow Min-cut).
Algoritmos Aleatórios: Quicksort (média de casos), Monte Carlo vs. Las Vegas algoritmos, amostragem por reservatório.
Algoritmos de Aproximação: Tratando problemas NP-duros (problema da mochila, problema do caixeiro-viajante) usando $1+\epsilon$ razões.
Algoritmos Online: Análise competitiva e o problema “Aluguel de Skis”.
Estruturas de Dados Avançadas:
árvores autoequilibradas (AVL, Red-Black, Splay Trees).
Análise amortizada (Fibonacci Heaps, Union-Find).
Hash ing: Bloom Filters, Cuckoo Hashing, Locality-Sensitive Hashing (LSH).

4. Lógica e Métodos Formais

A verificação matemática de硬件 e software.

Lógica proposicional e lógica predicativa: Solvers de SAT e SMT (Satisfiability Modulo Theories).
Model Checking: Lógica Temporal Linear (LTL) e Lógica de Árvore de Comutabilidade (CTL).
Teoria de Tipos: Lébra Calculo ( $\lambda$ -calculo), Tipos Dependentos e a Isomorfismo Curry-Howard.
Semântica de Programas: Semântica Operacional, Semântica Denotacional e Semântica Axiomatizada (Hoare Logic).
Verificação Formal: Provedores de Teorema Interativos como Coq, Isabelle/HOL e Lean.

5. Teoria da Economia e Teoria da Jogo Algorítmica

O que se une à computação e à comportamento social.

Equilíbrio de Nash: Cálculo de equilíbrios e o Preço da Anarquia.
Design de Mecanismos: Teoria de Ações, mecanismos VCG (Vickrey-Clarke-Groves).
Teoria da Cooperação Social: Teorema de Arrow e algoritmos de votação.
Mercados de Mapeamento: Problema do Casamento Estável e algoritmo Gale-Shapley.

6. Matemática Discreta e Combinatória

A “Língua” do TCS.

Teoria de Grafos: Grafos extremos, Teoria de Ramsey, e Grafos Aleatórios (Erdős–Rényi).
Optimização Combinatória: Programação Linear (Metodologias de Simplex e Interior-Point) e Teoria de Matrizes.
Funções de Gerar: Usadas para analisar a complexidade temporal de algoritmos recursivos.
Teoria da Probabilidade: Inequalidades de Concentração (Chernoff, Hoeffding) usadas em análise aleatória.

7. Geometria Computacional

Algoritmos para pontos, linhas, e polígonos.

Contorno Convexo: Algoritmos de Graham e Quickhull.
Partição Espacial: Diagramas de Voronoi e Triângulos de Delaunay.
Busca em Rango: Árvores de K-D e Árvores de Rango.
Planejamento de Movimento: Algoritmos para navegação de robôs por obstáculos.

8. Fronteiras emergentes teóricas (2026 foco)

Teoria da Informação Quantética: entrelaçamento quântico como recurso computacional.
Fairness Algorítmica: definições matemáticas de preconceito e justiça em decisões automatizadas.
Complexidade Fina: conjecturas de dificuldade dentro da classe P (por exemplo, dificuldade 3SUM).
Biologia Computacional: alinhamento de sequências (Needleman-Wunsch) e complexidade da encaixe de proteínas.
Teoria da Computação Distribuída: consenso em sistemas asincrónicos e o Teorema CAP.

Comparação de Fundamentos Principais

Fachada	Objetivo Principal	Método Matemático Central
Automatização	Definir o que é um computador	Gramáticas Formais
Complexidade	Medir “dificuldade”	Reduções & Lógica
Algoritmos	Encontrar a “mais rápida” rota	Indução & Recursão
Métodos Formais	Provar a “correção”	Teoria de Tipos & Assistente de Prova

Seria legal expandir a seção 2 (Complexidade) listando os níveis específicos da “Política Híperpolinomial” ou expandir a seção 4 (Lógica) detalhando as regras do Lambda Calculus?

Theoretical computer science

Automaton

A Teoria da Computação é uma ramo da ciência da computação e da matemática que se ocupa da eficiência com que problemas podem ser resolvidos em um modelo de computação usando um algoritmo. Esta área abrange diversos tipos de modelos de computação, incluindo, mas não se limitando a: máquinas de Turing, automatos finitos e automatos de pilha, e explora as limitações e as capacidades desses modelos.

Teoria de Automatos é uma área fundacional da Teoria da Computação que envolve o estudo de máquinas abstratas (autômatos) e os problemas que elas podem resolver. Ela se concentra principalmente nas propriedades matemáticas dessas máquinas e na sua capacidade para lidar com linguagens formais.

Automatas Finitos (AF) são modelos simples para computadores com um volume de memória muito limitado. Eles são frequentemente usados para representar sistemas simples ou como bloco para modelos computacionais mais complexos. Eles consistem em estados e transições entre esses estados, com cada transição sendo acionada por um símbolo de entrada da alfabeto finito.

Automatística é uma ramo da ciência da computação teórica que se ocupa da criação de dispositivos autônomos que seguem automaticamente uma sequência predeterminada de operações. Um automônato com um número finito de estados é chamado de Automônato Finito (FA), e é uma das modelos mais simples de computação. Os automônatos são usados para modelar e estudar as comportamentos e propriedades de diferentes sistemas computacionais.

Índice de Contribuições Principais de John von Neumann

John von Neumann (1903–1957) foi um polymath húngaro-americano que abrangia trabalhos em matemática pura, matemática aplicada, física, economia, computação e mais. A seguir está um índice de suas contribuições e teorias fundamentais, agrupados por campo, com uma breve descrição para cada um.

Matemática

Axiomatização da Teoria dos Conjuntos
Proporcionou uma das primeiras estruturas axiomáticas rigorosas para a teoria dos conjuntos (teoria de conjuntos de von Neumann–Bernays–Gödel), resolvendo paradoxes e introduzindo a distinção entre conjuntos e classes.
Formalismo de Espaço de Hilbert
Extendeu a teoria espectral dos operadores em espaços de Hilbert, fundacional para análise funcional e teoria dos operadores.
Algebras de Von Neumann (Riis de Operadores)
Introduziu algebras de operadores auto-adjuntas de operadores lineares limitados em espaços de Hilbert (atualmente chamadas de algebras de von Neumann), central para teoria moderna de álgebras de operadores.
Teoria Ergódica
Proveu o teorema ergódico médio (1932), fornecendo uma fundação rigorosa para a teoria ergódica em dinâmica.

ical sistemas.

Geometria Continua
Fundou a área da geometria contínua, uma analogia à geometria projeccional onde as dimensões podem ser contínuas ao invés de discretas.
Contributiones à Teoria da Medida
Avançou a teoria de funções medíveis e integração, incluindo trabalhos sobre igualdade em todo o domínio.
Teoria de Lattice e Geometria Projeccional
Juntou a teoria de lattes com a geometria projeccional, fundando as bases para abordagens modernas de geometria algebraica.

Mecânica Quântica e Física

Fundamentos Matemáticos da Física Quântica
Escreveu o seminal livro Mathematische Grundlagen der Quantenmechanik em 1932, estabelecendo as axiomas de Dirac e von Neumann e a formalismo de espaço de Hilbert para a teoria da física quântica.
Lógica Quântica
Explorou estruturas algebráicas para proposições quânticas, influenciando a lógica quântica.
Sobredeterminação de Entropia de Von Neumann
Definiu a entropia para estados quânticos, fundamental em teoria da informação quântica.
Design de Implosão para Bombas Atômicas
Contribuições-chave para o Projeto Manhattan, incluindo o design de lentes explosivas para a implosão de plutônio na bomba Fat Man.
Computações Hidrodinâmicas para Bombas Termonucleares
Avançou em simulações para armas termonucleares b desenvolvimento.

Teoria do Jogo e Economia

Teorema da minimax
Provado em 1928: em jogos de soma zero, os jogadores têm estratégias ótimas que minimizam a perda máxima; base da teoria dos jogos.
Teoria dos jogos e comportamento econômico (com Oskar Morgenstern, 1944)
Estabeleceu a teoria dos jogos como disciplina matemática, aplicando-a à economia e à decisão estratégica.
Modelo econômico expandido
Desenvolveu um modelo setorial de crescimento econômico equilibrado (1937), com influência sobre a economia matemática.

Computação e Teoria de Automatas

Arquitetura de Von Neumann
Descrição na reportagem EDVAC de 1945: a concepção de programação armazenada onde as instruções e os dados compartilham a mesma memória, fundamento para quase todos os computadores modernos.

Instantâneo offline omitido nesta edição web.

Algoritmo de Merge Sort
Inventado em 1945, um dos primeiros algoritmos eficientes de ordenação.
Automatas Celulares
Pioneiro na teoria dos autômatos autônomos reproduzíveis, provar que a construção universal é possível em uma grade; precursor do Jogo de Vida de Conway.
Método Monte Carlo (com Stanisław Ulam)
Desenvolvido técnicas de simulação probabilística usando amostragem aleatória, amplamente usada em física e computação.
Computador MANIAC
Lider na desenvolvimento do IAS (influenciando o MANIAC), um dos primeiros computadores operacionais com programação armazenada.
Análise de Estabilidade Numérica
Introduziu métodos (por exemplo, análise de stabilité de von Neumann) para avaliar os erros em soluções numéricas para

PDEs.

Claude Elwood Shannon (1916–2001) foi um matemático americano, engenheiro elétrico, criptógrafo e inventor, amplamente conhecido como o “pai da teoria da informação.” Seu trabalho firmou a base para o século XXI, unificando comunicação, computação e criptografia.

Design de Circuitos Digitais e Computação

Aplicação da Álgebra Booleana às Circuitos de Switching
Em sua tese de mestrado de 1937 (Análise Simbólica de Circuitos de Relâmpago e de Switching), Shannon mostrou como a lógica de George Boole, de 19 século, podia ser usada para designar circuitos de relâmpago e de switch, fornecendo a base teórica para todas as circuitos digitais e computadores.
Theseus (Mouse de Solução de Mauromazes)
Construído em 1950, este mouse electromecânico navegou por um labirinto e “aprendeu” o caminho correto através de tentativa e erro, uma demonstração antecipada de aprendizado de máquina e sistemas adaptativos.
Programação de Computadores para xadrez
Em um artigo de 1950, Shannon descreveu os princípios para xadrez de computador, incluindo o algoritmo minimax e a avaliação.

n funções, estabelecendo o fundamento para inteligência artificial de jogos.

Primeiro Computador a Usar (com Edward Thorp)
Co-inventou um dispositivo oculto em 1960 para prever as saídas do rolo de roleta usando a tempo, considerado o primeiro computador a usar.

Teoria da Informação e Comunicação

Teoria Matemática da Comunicação (1948)
Pequeno artigo seminal que introduziu a teoria da comunicação, definindo a entropia como uma medida de incerteza/informação e modelando a comunicação como fonte → codificador → canal (com ruído) → decodificador → receptor.
Entropia de Shannon
Formalizou a informação como a negativa do logaritmo da probabilidade (medido em bits), quantificando a incerteza e permitindo a compressão de dados.
Teorema da Codificação da Corrente
Proveu que a comunicação segura é possível em canais com ruído se o taxa for abaixo da capacidade do canal, fundamentando-se em código de correção de erros (por exemplo, em CDs, modems e comunicações espaciais).
Teorema de Shannon-Hartley
Definiu a capacidade do canal.

for Gaussian noise channels, giving the maximum data rate as $C = B \log_2(1 + \text{SNR})$ .

The Source Coding Theorem
Established limits on lossless data compression, showing the minimum rate equals entropy.
Introdução do termo “bit”
Cunhou “bit” (binary digit) como unidade de informação.

Cryptography and Other Fields

Teoria da Comunicação de Sistemas de Segredo (1949)
Fundamento matemático para a criptografia, provar a insegurança do pad de uma vez só e introduzir conceitos como perfeita segredo.
Gráficos de Fluxo de Sinal
Inventado em 1942 para analisar sistemas lineares, amplamente usado em teoria da controle e em eletrônica.
Teoria Matemática do Jogaço
Desenvolvido “Teorema do Jogaço de Shannon” relacionando o número de bolas, tempo de abdicação e tempo de voo; ele era um entusiasta do jogaço e construiu máquinas de jogaço.

Shannon’s insights revolutionized digital communication, computing, AI precursors, and even fields like genetics and physics. His playful inventions (unicycle juggling, flame-throwing trumpets) reflected his boundless curiosity, bridging profound theory with practical whimsy.

A small history

Segue um panorama breve de cada uma dessas figuras influentes:

Vannevar Bush (1890–1974): Um engenheiro e inventor americano, Bush é melhor conhecido por seu trabalho em computação analógica e por seu conceito de “Memex.” Esteve presente em seu artigo de 1945 “Como Podemos Pensar,” onde o Memex era uma dispositivo hipotético para armazenar e recuperar informações, um conceito fundamental para ideias futuras de hipertexto e computação pessoal.
Ted Nelson: Um pioneiro da tecnologia da informação americano, Nelson criou o termo “hypertext” na década de 1960. Ele é conhecido por seu trabalho em Project Xanadu, uma proposta para uma rede mundial de computadores que antecedeu e influenciou o desenvolvimento do World Wide Web.
Alan Turing (1912–1954): Um matemático, lógico e criptógrafo britânico, Turing é um dos pioneiros da computação.

tanalyst, Turing é amplamente considerado como o pai da ciência da computação teórica e inteligência artificial. Seu trabalho durante a Segunda Guerra Mundial na destruição da codificação do Enigma alemão foi crucial.

Grace Hopper (1906–1992): Uma cientista da computação americana e capitão da Marinha dos Estados Unidos, Hopper foi pioneira na tecnologia da computação. Ela foi uma das primeiras programadoras do computador Harvard Mark I e desenvolveu o primeiro compilador para uma linguagem de programação.
Alan Kay: Um cientista da computação americano, Kay é melhor conhecido por seu trabalho pioneiro em programação orientada a objetos e na desenvolvimento da interface gráfica (GUI). Ele foi um membro-chave do Xerox.

x PARC team that developed the Alto, an early personal computer.

Douglas Engelbart (1925–2013): Um engenheiro e inventor americano, Engelbart é melhor conhecido por seu trabalho em desenvolver a interface do computador humano. Seu maior invento é o mouse de computador. Ele também desempenhou um papel importante em desenvolver o hipertexto, computadores de rede, e primeiros GUIs.
Steve Wozniak: Um inventor, engenheiro eletrônico e programador americano, Wozniak co-fundou a Apple Inc. com Steve Jobs e Ronald Wayne. Ele é o principal desenvolvedor dos computadores Apple I e Apple II.
Steve Jobs (1955–2011): Um empreendedor, inventor e magnata da negócios americano, Jobs foi o co-fundador, presidente e CEO da

Apple Inc. Ele foi pioneiro na revolução do computador pessoal e teve um papel crucial na desenvolvimento do Macintosh, iPod, iPhone, e iPad.

Marc Andreessen: Um empreendedor, investidor e engenheiro de software americano, Andreessen é conhecido principalmente por seu trabalho em Mosaic, o primeiro navegador web amplamente usado, e por co-fundar a Microsoft Corporation.
Bill Gates: Um magnata da indústria da tecnologia, desenvolvedor de software e filantropo americano, Gates co-fundou a Microsoft Corporation, a maior empresa de software de computador do mundo. Ele desempenhou um papel significativo na revolução do computador pessoal.
Tim Berners-Lee: Um cientista da computação britânico, Berners-Lee é melhor conhecido como inventor do

O criador do mundo-wide web. Ele propôs um sistema de gerenciamento de informações em 1989, o que resultou na desenvolvimento do primeiro navegador web e servidor web.

Aqui está uma visão mais detalhada das concepções do ponto de vista de um iniciante:

Autômatos finitos (AF)

Os automatos finitos são frequentemente o ponto de partida para o estudo da Teoria de Automatos. Existem duas principais classes de automatos finitos:

Automato Finito Determinístico (AFD): Em um AFD, para cada estado, existe exatamente uma transição para cada símbolo da alfabeto que o automato opera sobre. Isso significa que, dado um estado e um símbolo de entrada, o automato pode se mover para exatamente um estado.
Automato Finito Nondeterminístico (AFN): NFAs diferem dos AFDs no fato de que permitem múltiplas ou nenhuma transição para cada par de estado e símbolo de entrada. Eles também podem ter transições ε, que são transições que o automato pode tomar sem consumir nenhum símbolo de entrada.
Relação com Máquinas de Turing

Turing Machines (TMs) são um modelo de computação mais poderoso que foi proposto por Alan Turing em 1936. Um Turing Machine é uma máquina teórica usada como modelo de computação para definir algoritmos gerais e pode simular qualquer algoritmo de computador. Ele consiste em:

Uma tampa dividida em células onde pode ler e escrever símbolos.
Uma cabeça que pode ler e escrever símbolos e mover na tampa.
Uma tabela finita de regras (a função de transição) que determina o que a máquina faz (i.e., como ela se move e o que ela escreve).

Enquanto os autômatos finitos têm memória finita, as máquinas de Turing dispõem de memória infinita na forma da fita. Essa diferença as torna estritamente mais poderosas: há problemas que uma máquina de Turing resolve e um autômato finito não.

Relation to Calculators

Calculadores podem ser pensados como computadores especializados projetados para realizar operações aritméticas. As operações básicas de um calculador (adição, subtração, multiplicação e divisão) podem ser pensadas como algoritmos que podem ser implementados em uma Máquina de Turing. A teoria da automação fornece a abstração matemática para entender as capacidades e limitações desses dispositivos.

Modelos Matemáticos Relacionados

No contexto da teoria das automações, existem vários modelos matemáticos relacionados de computação:

Automato de Preenchimento (AP): Estes são automatos que têm acesso a uma pilha, o que lhes dá mais poder computacional do que os automatos finitos, mas menos do que as Máquinas de Turing. APs são usados para modelar o poder computacional das linguagens de contexto-fáceis, que incluem a maioria dos linguagens de programação.
Automato Linearmente Limitado (AL): Estes são como as Máquinas de Turing, mas com a restrição de que sua pilha não é de tamanho fixo e não se estende indefinidamente. LBAs são usados para definir as linguagens de contexto-sensíveis.
Automatôma Celular (AC): Estes são modelos de computação que consistem em uma grade de células, cada uma em um dos estados finitos de uma quantidade limitada de estados. A mudança de estado de cada célula ocorre com base em um s t das regras que dependem das condições dos vizinhos de células.
Automatas Probabilísticos e Automatas Quânticos: Estes introduzem, respectivamente, a randomização e efeitos quânticos na modelagem de computação.

Significância

A importância da teoria dos automatos reside na capacidade de fornecer um framework para compreender as capacidades e limitações de diferentes sistemas de computação, para classificar problemas em função de sua complexidade computacional, e para oferecer uma maneira de desenhar e analisar algoritmos. A pesquisa na teoria dos automatos tem levado a importantes descobertas na ciência da computação, como a definição formal da computação e a estabelecimento do campo da complexidade computacional.

Construção de Conjuntos de Poder

Também conhecido como Construção de Subconjuntos, é um método usado para converter um NFA em um DFA equivalente. O DFA reconhecerá a mesma linguagem que o NFA original. O termo “podereset” refere-se à verdadeira que a construção envolve a criação de estados no DFA que correspondem a conjuntos de estados no NFA. Aqui está como isso geralmente funciona:

Estado Inicial: O estado inicial do DFA é o conjunto de estados NFA que podem ser alcançados do estado inicial do NFA, incluindo através de transições epsilon (transições que não consumem nenhuma símbolo de entrada).
Transições: Para cada estado no DFA (que é um conjunto de estados NFA) e para cada símbolo na alfabeto, você determina o conjunto de estados NFA que podem ser alcançados de qualquer estado nesse conjunto quando o símbolo de entrada é consumido. Isso se torna o estado de destino para aquele símbolo no DFA.
Estados Aceitáveis: Um conjunto de estados NFA no DFA é um estado aceitável se qualquer um dos estados no conjunto for um estado aceitável.

Esta construção pode resultar em um DFA com um número de estados potencialmente exponencial em relação ao número de estados do NFA, especificamente (2^n) se o NFA tiver (n) estados (pois este é o número de subconjuntos, ou o “poderetê,” do conjunto de estados do NFA).

A Construção de Subconjuntos é essencial porque permite a conversão de NFAs em DFAs, que podem ser mais fáceis de implementar prática, já que a comportamento de um DFA é mais previsível e fácil de simular. DFAs não requerem retroalimentação ou se manterem ativos em múltiplos estados possíveis, o que torna-os mais eficientes para certos aplicativos.

Entender a Construção de Subconjuntos também é crucial para fins teóricos — é uma demonstração concreta de que NFAs e DFAs têm poder expressivo equivalente, que é um resultado fundamental na teoria das linguagens regulares e autômatos. Esta equivalência é central para o estudo de expressões regulares e suas aplicações em processamento de texto, compiladores e outras áreas da ciência da computação.

A relação entre a teoria da computação e a obra de Noam Chomsky é principalmente através de sua contribuição para a teoria formal de linguagens, que é um componente chave tanto da teoria da computação quanto da teoria de automatos. Noam Chomsky, que é mais conhecido por suas contribuições para a linguística, também fez contribuições significativas para o campo da teoria da computação.

Aqui estão algumas das maneiras em que a obra de Chomsky está relacionada à teoria da computação:

Hierarchy de Chomsky

Chomsky introduziu a hierarquia de Chomsky, uma classificação de linguagens formais de acordo com sua potência geradora. A hierarquia divide as classes de gramáticas em quatro níveis:

Gramáticas de primeira ordem (Type 0): Gramáticas que podem ser descritas por expressões regulares.
Gramáticas de segunda ordem (Type 1): Gramáticas que podem ser descritas por gramáticas regulares.
Gramáticas de terceira ordem (Type 2): Gramáticas que podem ser descritas por gramáticas regulares.
Gramáticas de quarta ordem (Type 3): Gramáticas que podem ser descritas por gramáticas regulares.

Chomsky’s Grammars

As gramáticas de Chomsky são gramáticas formais usadas para descrever a estrutura das línguas naturais. Definem-se por um conjunto de regras que especificam como as palavras se combinam em sintagmas e orações. Costumam ser empregadas no estudo da aquisição da linguagem e no desenvolvimento de algoritmos de processamento de língua.

Chomsky’s Universal Grammar

A Gramática Universal (UG) de Chomsky é um conjunto de princípios que governariam a estrutura de todas as línguas humanas. Inclui traços como a recursão, o uso de marcadores de caso e a presença de certas classes de palavras (por exemplo, nomes, verbos, adjetivos). O estudo da UG é parte importante da linguística e tem implicações para a aquisição da linguagem e o processamento linguístico.

Chomsky’s Syntactic Categories

As categorias sintáticas de Chomsky descrevem a estrutura das orações de uma língua. Incluem noções como sujeito, verbo, objeto e sintagmas adverbiais. O estudo dessas categorias é parte importante da linguística e tem implicações para a aquisição da linguagem e o processamento linguístico.

Chomsky’s Phrase Structure Grammar

A gramática de estrutura de constituintes (PSG) de Chomsky é uma gramática formal usada para descrever a estrutura das orações. Define-se por regras que especificam como as palavras se combinam em sintagmas e orações. Costuma ser empregada no estudo da aquisição da linguagem e no desenvolvimento de algoritmos de processamento de língua.

Chomsky’s Transformational Grammar

A gramática transformacional (TG) de Chomsky é uma gramática formal usada para descrever a estrutura das orações. Define-se por regras que especificam como as palavras se combinam em sintagmas e orações, e por transformações sobre essas estruturas.

Chomsky’s Transformational-Grammatical Grammar

A chamada gramática transformacional-gerativa (TGG) de Chomsky é uma gramática formal usada para descrever a estrutura das orações. Define-se por regras que especificam como as palavras se combinam em sintagmas e orações, e por um componente transformacional.

Chomsky’s Transformational-Grammatical Grammar (TGG)

Chomsky

Tipos 0 (Gramáticas Recursivamente Enumeráveis): Estas são as gramáticas mais generalizadas (gramáticas não restritas), capazes de gerar todos os linguagens que podem ser reconhecidas por um Turing Machine. As linguagens nesse tipo são conhecidas como recursivamente enumeráveis; não todas podem ser decididas por um Turing Machine.
Tipos 1 (Gramáticas Contextuais): Geradas por gramáticas contextuais, essas linguagens exigem mais poder computacional do que as gramáticas contextuais, mas menos do que as gramáticas recursivamente enumeráveis. Elas podem ser reconhecidas por um automóvel limitado por tampa (LBA), que é um Turing Machine com recursos limitados.
Tipos 2 (Gramáticas Contextuais): Geradas por gramáticas contextuais.

rammars, essas linguagens podem ser reconhecidas por autômatos de tipagem push-down. As linguagens contextuais são fortes o suficiente para descrever a sintaxe de muitas linguagens de programação.

Tipo 3 (Linguagens Regulares): Geradas por gramáticas regulares, essas são as linguagens mais simples e podem ser reconhecidas por autômatos finitos. As linguagens regulares são frequentemente usadas para padrões de pesquisa e são o fundamento para expressões regulares.

Conclusão à Linguística e Computação

A obra de Chomsky em linguística, especialmente sua teoria de gramática transformacional-ganativa, também influenciou modelos computacionais de processamento de linguagem e processamento de linguagem natural (NLP). Suas teorias sobre a estrutura da linguagem e as regras que governam a sintaxe ajudaram a moldar algoritmos e métodos utilizados para desambiguar e compreender as línguas humanas em sistemas computacionais.

Teoria de Automatos

No automata teoria, a hierarquia de Chomsky fornece um framework para entender a relação entre a complexidade dos estruturas de linguagem e a potência computacional necessária para processá-las. Também corresponde a diferentes classes de autômatos, como cada classe de gramática na hierarquia é associada a uma classe de automato capaz de reconhecer ou gerar seus linguagens.

Em resumo, o trabalho de Chomsky estabeleceu o fundamento para o estudo de gramáticas formais e linguagens formais, que são essenciais para teoria da computação. Sua hierarquia ajuda a entender as limitações dos modelos computacionais e a complexidade das algoritmos necessárias para processamento de linguagem.

Comparências

Uma máquina de Turing é, de fato, um tipo de autômato. Na teoria dos autômatos, um autômato é qualquer máquina abstrata que muda de estado em resposta a um conjunto de entradas, segundo regras determinadas. Essa definição abrange vários modelos de computação, inclusive autômatos finitos, autômatos de pilha, autômatos linearmente limitados e máquinas de Turing.

Como as máquinas de Turing se encaixam no conceito de autômato:

Definição de um Automônio

Um automônio é definido por:

Uma coleção de estados, um deles sendo designado como estado de início.
Uma alfabeto de símbolos que o automóvel lê.
Um conjunto de regras de transição que determinam como o automóvel se move de um estado para outro, baseado no símbolo de entrada que lê.
Um conjunto de estados aceitáveis (para autômatos que aceitam ou rejeitam entradas).

Turing Machines como Automatos

Um Turing machine expande o conceito de um automóvel com as seguintes:

Uma fita que serve tanto como entrada quanto como armazenamento de memória infinita. A fita é dividida em células, cada uma das quais pode conter um símbolo.
Um cabeçote que pode ler da fita e escrever na fita e mover-se para a esquerda ou para a direita uma célula a cada vez.
Uma coleção de estados, juntamente com uma função de transição que determina como o computador reage ao símbolo que lê da fita. Isso inclui mudar de estado, escrever um novo símbolo na fita e mover o cabeçote.
Um estado de início, e, possivelmente, um estado de parada, onde o computador para de processar.

A máquina de Turing é um modelo de computação mais poderoso do que outros automatos devido à sua capacidade de simular os processos computacionais de qualquer máquina, se tiverem tempo suficiente e tape. Isso é conhecido como Turing completidade. A concepção de Turing fornece uma definição fundamental de um computador geral e é central para a teoria de Turing, que postula que qualquer computação que pode ser realizada por algum algoritmo pode ser realizada por uma máquina de Turing.

Classificação Hierárquica

Na hierarquia de gramáticas formais de Chomsky, cada nível corresponde a uma classe de automatos capazes de reconhecer as linguagens geradas pelas gramáticas no nível correspondente:

Tipo 3 (Linguagens Regular): Reconhecidos por autômatos finitos.
Tipo 2 (Linguagens Contextuais): Reconhecidos por autômatos de pilha.
Tipo 1 (Linguagens Contextual): Reconhecidos por autômatos lineares limitados.
Tipo 0 (Linguagens Recursivamente Enumeráveis): Reconhecidos por máquinas de Turing.

Portanto, na teoria dos automatos, as máquinas de Turing representam a classe de automatos mais poderosa capaz de reconhecer as linguagens de maior complexidade descritas pela hierarquia de Chomsky.

Índice da parte

O mapa científico, as equações e o conjunto bibliográfico desta parte da base de conhecimento estão nos índices de parte:

Geral · Engenharia · Ciência da computação · Playbooks
Índices · Glossário · SUMÁRIO

Os retratos da Wikipédia no cartão do capítulo servem de orientação offline; os índices de parte reúnem as trilhas completas de citação.