Parte 1

Prévia do material em texto

Teoria da Computação 
 
Núcleo de Educação a Distância | Faculdade Impacta 
Texto base 
1 
 
Teoria da Computação 
Ana Paula Ferreira da Rocha 
Resumo 
O conceito histórico é de suma importância para a compreensão do surgimento da 
Teoria da Computação, seus conceitos e das teorias que deram o impulsionamento para 
que fosse possível termos acesso à tecnologia dos dias atuais. Para isso estudaremos o 
histórico e evolução da Teoria da Computação e seus conceitos básicos para 
abordarmos assertivamente as teorias dos autômatos, da complexidade, da 
computabilidade e máquina de Turing. 
Introdução 
 Iremos revisar a Evolução da Teoria da Computação e sua história veremos 
todas as principais contribuições que tivemos ao longo dos séculos para a computação e 
revisaremos os conceitos básicos relacionados para o aprofundamento de nosso 
conhecimento nas demais teorias que abordaremos. 
 
 
1.1. Histórico e Evolução da Teoria da Computação 
Quando pensamos em computação, imaginamos o sistema computacional e seus 
principais componentes: hardware, interface, processador e demais componentes. 
Contudo a história da computação nos remete a uma antiguidade onde não possuíamos 
os componentes utilizados nos dias atuais. Sendo utilizada para armazenar informações, 
desenvolvimento de resoluções complexas bem como utilizada em operações de 
contagem. 
Para Brookshear (2013) a definição de computação pode ser definida como um processo 
automatizado de um conjunto de dados de entrada, onde a computação realiza o 
processamento destes dados por meio de cálculos e modelos para que se obtenha os 
resultados dos dados informados. 
 
Teoria da Computação 
 
Núcleo de Educação a Distância | Faculdade Impacta 
Devemos lembrar que o sistema computacional é divido em dois componentes 
principais que são o software (que consiste de algoritmos em conjunto com suas 
representações teremos os programas que são executados) e o hardware (que consiste 
nos periféricos elétricos e eletrônicos onde encontramos a memória, o processador, os 
circuitos integrados e demais dispositivos como impressoras, cabos e demais auxiliares). 
Consideramos como início da história da computação a criação do ábaco, na 
Mesopotâmia há mais 5.500 anos (PERES, 2013). Sendo considero o instrumento de 
cálculo mais antigo onde as operações matemáticas básicas e complexas, como raiz 
quadrada e cúbica, começaram a ser realizadas de forma mais eficiente. Na figura a 
seguir temos o ábaco: 
 
O ábaco foi o primeiro computador desenvolvido e amplamente utilizado em operações matemáticas 
básicas e complexas 
Fonte: Kirpmun, Shutterstock, 2018. 
 
Como podemos verificar na figura, o modelo mais básico é composto de uma moldura 
externa com bastões paralelos (no sentido vertical), onde cada um representa uma 
posição digital (unidade, dezena, centena e etc.). Os elementos de contagem de cada 
bastão podem ser representados por fichas, bolas e etc. 
Conforme Stallings (2009), no século XVII, surgiram as primeiras máquinas de calcular 
que funcionavam por meio de força mecânica. Já a primeira calculadora que realizava as 
operações de adição e subtração foi criada em 1642 pelo matemático Blaise Pascal. Em 
1671 o matemático Gottfried Leibniz desenvolveu uma calculadora para realizar as 
operações de divisão e multiplicação por meio de adições e subtrações sucessivas. 
Apenas em 1820 Charles Tomas, utilizando o mesmo princípio da calculadora utilizado 
por Leibniz, produz a primeira calculadora comercializada com sucesso. 
Outro importante acontecimento do século XIX para a computação moderna é o 
nascimento da primeira programadora Ada Lovelace (1815 – 1852) que contribuiu para 
a criação da primeira máquina de cálculo. A Máquina Analítica criada por Charles 
Baggage contou com o apoio de Lovelace para o desenvolvimento do primeiro 
algoritmo da história, utilizado para calcular funções matemáticas. 
Já no século XX nasce o pai da ciência da computação e da inteligência artificial Alan 
Turing (1912 – 1954). Matemático, criptoanalista, cientista da computação e lógico seu 
papel foi decisivo para a área da computação. Responsável pelo desenvolvimento da 
Máquina de Turing, uma máquina hipotética com capacidade para realizar todo e 
qualquer tipo de computação, criando assim o conceito de algoritmo. 
 
Teoria da Computação 
 
Núcleo de Educação a Distância | Faculdade Impacta 
 
Você conhece? 
Alan Turing considerado o pai da ciência da computação e da inteligência artificial 
desenvolveu uma importante máquina hipotética durante a Segunda Guerra Mundial 
que contribui de forma significativa para os aliados conseguirem decifrar as 
mensagens secretas que eram transmitidas via rádio pelos nazistas. Com a Máquina de 
Turing foi criado o conceito de algoritmo. Quer conhecer mais sobre a fascinante 
história de Turing? Assista ao filme Enigma – O jogo da imitação. Disponível em: 
<https://www.youtube.com/watch?v=lRid96uWpqo>. Acesso em: 12 abr. 2023. 
 
 
Outro marco importante para a teoria da computação foi o trabalho desenvolvido pelo 
matemático David Hilbert (1862 – 1943) foi o Entscheidungsproblem (problema de 
decisão) desafio que foi formalizado em 1928 como segue: 
 
Encontrar um algoritmo que recebe como entrada a descrição de uma linguagem formal e uma sentença 
nesta linguagem e tem como saída “verdadeiro” ou “falso” dependendo se a sentença de entrada é 
verdadeira ou falsa. (Diverio, 2011, p.23). 
 
Por ser frequentemente identificado como uma decisão lógica de primeira ordem, 
determinar algoritmicamente a sequência lógica de primeira ordem consiste se ela é 
válida ou não. Para Hilbert este procedimento era justificado pela ideia de que todo 
problema, estando bem definido, poderia ser resolvido. Até 1930, este era seu 
pensamento que não existia problema sem solução. 
Em 1931, o matemático Kurt Gödel (1906 – 1978) publicou o trabalho incompleteness 
theorem (teorema da não completude) onde demonstrou que qualquer sistema 
axiomático que define a multiplicação e a adição no conjunto dos números naturais não 
pode ser simultaneamente completo e consistente: se consistente existem proposições 
que não podem ser verificadas, sendo assim incompletos; se completos não poderá 
validar a si mesmo, sendo inconsistente. (Gödel, 1965). 
No trabalho de Gödel a característica importante é a utilização dos números naturais 
para codificar formulas lógicas. Realizando assim uma enumeração das mesmas, sendo 
considerado o primeiro a identificar o formalismo para definir a noção de procedimento 
efetivo. 
Contudo o problema de decisão de Hilbert ainda não havia sido resolvido e em 1936 
Alonzo Church (1903 – 1995) entende que o mesmo não possui solução. Para tal 
entendimento Church conta com o apoio de Turing com a formalização do algoritmo. 
Utilizaram para este entendimento dois formalismos: cálculo Lambda (Church, 1936) e 
funções recursivas (Kleene, 1936) que após a verificação de Kleene surge a tese de 
Church: 
Tais formalismos são caracterizações tão gerais da noção do efetivamente computável quanto consistentes 
com o entendimento intuitivo usual (Church,1936) 
 
 
Teoria da Computação 
 
Núcleo de Educação a Distância | Faculdade Impacta 
Podemos notar que a tese de Church é fundamentada em uma noção intuitiva, não 
formal, mas como todas as evidências indicavam ser verdadeiras, assumiu-se a tese 
como uma hipótese para todo teoria da computação e hoje é conhecida como Hipótese 
de Church. 
Em paralelo Turing trabalhava em um formalismo para representação de procedimentos 
efetivos. Seu trabalho foi muito significativo por ter sido o primeiro a identificar 
programas escritos para uma máquina computacional utilizando noções intuitivas do 
efetivamente computável. A máquina de Turing é um formalismo simples, conhecido 
universalmente e o mais usado como modelo teórico da computação. Sendo a 
fundamentação teóricautilizada para o desenvolvimento dos modelos de computadores 
atuais. 
Muitos outros formalismos foram propostos que possuem o mesmo poder 
computacional como por exemplo: máquina de Turing (1936), máquina de Norma 
(1976), sistema canônico de Post (1943), algoritmo de Markov e linguagem Snobol 
(1954), máquina de registradores (1963) e RASP (Random Access Stored Programs 
(Programas armazenados de acesso aleatório) – 1964). 
Com base no que exploramos define-se programa como um procedimento efetivo, que 
podemos descrever utilizando os formalismos correspondentes acima. Com isso 
podemos afirmar que qualquer um destes formalismos irá permitir descrever os 
possíveis procedimentos que serão executados em um computador. 
 
1.2. Conceitos Básicos 
Conforme Diverio (2011) linguagem trata-se do conceito fundamental na teoria da 
computação, utilizada por sua precisão para expressar problemas, permitindo o 
desenvolvimento e a formalização adequada ao estudo da computabilidade. O que 
iremos ver mais adiante estará relacionado ao estudo do solucionabilidade de um 
problema proposto, ao considerá-la como a investigação da existência de um algoritmo 
que possa determinar se uma palavra pertence ou não à linguagem que soluciona esse 
desafio. 
Segundo o dicionário Michaelis podemos definir linguagem como: 
 
Faculdade que tem todo homem de comunicar seus pensamentos e sentimentos (MICHAELIS, 2023). 
 
Contudo esta definição não atende a necessidade do desenvolvimento matemático da 
teoria baseada em linguagens. Sabemos que a linguagem é um dos conceitos mais 
importante da computação. Mas para definirmos linguagem, neste âmbito, precisamos 
primeiro entender os conceitos de alfabeto, palavra e/ou cadeia de caracteres. 
Desta maneira vamos abordar estas principais definições baseadas em noções de 
símbolo e caractere. Tratando-se de uma entidade abstrata básica, que não pode ser 
definida formalmente. As letras e dígitos são utilizados como exemplos de símbolos 
regularmente utilizados. 
 
Teoria da Computação 
 
Núcleo de Educação a Distância | Faculdade Impacta 
1.3. Alfabeto 
Um alfabeto é um conjunto finito de símbolos ou caracteres e é representado por Σ ( lê-
se sigma) 
Se o conjunto for definido como infinito ele não é um alfabeto, entretanto se ele for um 
conjunto vazio ele é um alfabeto. 
Por exemplo: 
{a,b,c} 
Ø (conjunto vazio) 
Já os exemplos abaixo não são considerados alfabetos: 
 
N (Conjunto de números naturais) 
{a, b, aa, ab, ba, bb, aaa, ...} 
 
Quando falamos de alfabeto na linguagem de programação consideramos todos os 
símbolos usados na construção dos programas, onde incluímos letras, dígitos, caracteres 
especiais como “>”, “/”, espaço ou “branco”. 
Na construção do código é utilizado um alfabeto binário, geralmente usa-se o alfabeto 
{a,b}, já que o valor de um bit é binário esta representação mantem a analogia interna 
dos computadores, simplificando a manipulação dos símbolos utilizados em várias 
abordagens que serão desenvolvidas no decorrer da codificação. 
 
Você sabia? 
Segundo Vieira (2006) todo alfabeto está associado a uma Linguagem. Sendo o 
alfabeto um conjunto finito não vazio de elementos que serão referidos como 
símbolos. Quer conhecer mais sobre Alfabeto? Assista ao vídeo Teoria da 
Computação 01 – Símbolos, Alfabetos e Linguagens. Disponível em: 
<https://www.youtube.com/watch?v=utzVhv4WWfg&list=PLDDV68kBkoTZ3kuL0
Td05gD-_MM-bJWrW>. Acesso em: 16 abr. 2023. 
 
1.4. Cadeia de símbolos, palavra 
Cadeia de caracteres de um alfabeto é uma sequência finita de símbolos deste alfabeto 
justapostos. 
Sendo assim, considerando o alfabeto Σ = {a,b} podemos considerar as seguintes 
cadeias (que é representada por: w): 
w = λ (representa a cadeia vazia, sem símbolos) 
 
Teoria da Computação 
 
Núcleo de Educação a Distância | Faculdade Impacta 
w = a 
w = b 
w = ab 
w = ba 
w = aab 
 
Uma cadeia de símbolos sobre o alfabeto Σ trata-se de uma sequência de zero ou mais 
símbolos de Σ. Já uma palavra sobre Σ é uma cadeia finito de símbolos, assim sendo 
uma cadeia sem símbolos é uma palavra válida: 
 
λ (representa uma cadeia vazia ou palavra vazia) 
 
1.5. Comprimento, tamanho de uma palavra 
O tamanho ou comprimento de uma cadeia (w) é representado por |w| que corresponde 
ao número de caracteres que compõe a cadeia. Por exemplo: 
 
w = λ |w| = 0 
w = a |w| = 1 
w = ab |w| = 2 
w = abb |w| = 3 
w = bbaa |w| = 4 
1.6. Prefixo, sufixo, subpalavra 
Prefixo é qualquer sequência de símbolos iniciais da cadeia (w). 
Sufixo é qualquer sequência de símbolos do final da cadeia (w). 
Subpalavra é qualquer sequência de símbolos que compõe a cadeia (w). 
Para um melhor entendimento dos conceitos acima, usaremos um exemplo prático de 
demonstração. 
Se consideramos a cadeia: 
 
w = abcde 
 
Teremos: 
 
Prefixo: λ, a, ab, abc, abcd, abcde 
Sufixo: λ, e, de, cde, bcde 
Subpalavra: bc, bcd, cd, e assim por diante 
 
1.7. Conjuntos 
Segundo o dicionário Michaelis podemos definir conjunto: 
 
Teoria da Computação 
 
Núcleo de Educação a Distância | Faculdade Impacta 
 
Conceito primitivo, de difícil precisão e definição, que corresponde à ideia intuitiva de reunião, coleção 
ou agrupamento de objetos ou elementos, determinados de diferenciáveis, próprios da realidade exterior 
ou oriundos das construções do pensamento. (MICHAELIS, 2023). 
Sendo assim para podemos afirmar que os elementos de um conjunto podem ser 
também conjuntos. Para se dizer que este elemento pertence a um conjunto, ou seja, faz 
parte do conjunto, usamos notação (por exemplo a ∈ A) e para dizermos que o elemento 
não faz parte do conjunto utilizamos a notação (por exemplo a ∉ A). 
Os conjuntos finitos geralmente são definidos ao se listar seus elementos entre chaves e 
separados por vírgulas. Neste momento a ordem dos elementos torna-se irrelevante, já 
que aos se ter dois conjuntos com os mesmos elementos dizemos que são iguais, o que 
significa que são o mesmo conjunto. 
Para exemplificar um conjunto de objetos homogêneos podemos utilizar o conjunto do 
sistema solar: 
{mercúrio, marte, vênus, terra, saturno, plutão, netuno, júpiter, urano}. 
E como vimos um conjunto pode ser composto de outro conjunto e para demonstrar 
vamos incluir o conjunto de números inteiros aos nosso conjunto do sistema solar: 
{07, júpiter {1}, {saturno, urano, 0, 2,3}}. 
Quando falamos que os conjuntos podem ser iguais, ou o mesmo conjunto podemos 
exemplificar desta maneira: 
{1, 2} = {2, 1} = {1, 2, 1} = {2, 1 + 1, 2 - √4}. 
Quando um conjunto não possui elementos, chamamos de conjunto vazio e 
representamos por ∅, ou seja, ∅ = { }. Contudo ainda temos os conjuntos infinitos, o 
que significa que termos uma quantidade infinita de elementos nestes conjuntos. 
Destacamos os seguintes conjuntos infinitos: 
• N, conjunto de números naturais (inteiros não negativos); 
• Z, conjunto de números inteiros; 
• R, conjunto de números reais; 
• Q, conjunto de números racionais (onde apresentamos números reais que podem 
ser expressos como m/n, onde m e n serão números inteiros. 
Possuímos diversas formas para definir conjuntos, não apenas listando seus elementos 
dentre as chaves. Por esta razão é comum utilizar a expressão { 𝓍 | 𝑃 (𝓍)} onde lê-se: o 
conjunto de todos os elementos x tais que x satisfaz a propriedade P. Para evitarmos o 
surgimento de paradoxos como o de Russell a definição adotada comumente é “o 
conjunto dos elementos do conjunto A que satisfaz a propriedade P”, com isso veremos 
com frequência a expressão {𝓍 ∈ 𝐴 | 𝑃(𝓍)} e sua denotação é {𝓍 | 𝑥 ∈ 𝐴 𝔢 𝑃(𝓍)}. 
Já o conjunto de números naturais ímpares podemos descrever como: {𝑘 | 𝑘 = 2𝑛 +
1 𝔢 𝑛 ∈ 𝑁} . 
E quando queremos descrever o conjunto de números reais entre 0 e 1, incluindo 0 e 1, 
utilizamos a seguinte expressão: 𝑘 ∈ 𝑅 | 0 ≤ 𝑘 ≤ 1}. 
 
Teoriada Computação 
 
Núcleo de Educação a Distância | Faculdade Impacta 
Possuímos também os conjuntos unitários, como o próprio nome diz trata-se dos 
conjuntos que possuem apenas um elemento, por exemplo: {𝑡𝑒𝑟𝑟𝑎}, {5}, {∅}. Sendo o 
último um conjunto vazio em que seu único elemento é o vazio. 
Que tal falarmos um pouco sobre as operações que realizamos com os conjuntos? 
Quando possuímos elementos iguais em dois conjuntos diferentes dizemos que os 
mesmos estão contidos, ou seja, se todo elemento do conjunto A é elemento do conjunto 
B: 𝐴 ⊆ 𝐵 , sendo assim descrevemos: 
𝐴 ⊆ 𝐵 ⟷ 𝑝𝑎𝑟𝑎 𝑡𝑜𝑑𝑜 𝑥, 𝑠𝑒 𝑥 ∈ 𝐴 𝑒𝑛𝑡ã𝑜 𝑥 ∈ 𝐵. 
Quando possuímos o conjunto A como subconjunto de B dizemos que A está contido 
em B porém não é igual a B: 𝐴 ⊂ 𝐵. Onde será descrito: 
𝐴 ⊂ 𝐵 ↔ 𝐴 ⊆ 𝐵 𝑒 𝐴 ≠ 𝐵. 
Ao falarmos de união de dois conjuntos, utilizaremos novamente o exemplo de A e B, 
onde o conjunto é constituído da união dos elementos comuns de A e B = 𝐴 ∪ 𝐵, 
podendo ser descrito como: 
𝐴 ∪ 𝐵 = {𝑥 | 𝑥 ∈ 𝐴 𝑜𝑢 𝑥 ∈ 𝐵}. 
Já na interseção dos conjuntos teremos um conjunto constituído pelos elementos 
comuns entre os conjuntos: 𝐴 ∩ 𝐵, que será descrito: 
𝐴 ∩ 𝐵 = {𝑥 | 𝑥 ∈ 𝐴 𝑒 𝑥 ∈ 𝐵}. 
Contudo quando falamos de diferença entre os conjuntos teremos um conjunto 
constituído de elementos que não pertencem ao outro conjunto: 𝐴 − 𝐵, descrito como: 
𝐴 − 𝐵 = {𝑥 | 𝑥 ∈ 𝐴 𝑒 𝑥 ∉ 𝐵}. 
Você quer ler? 
Conjuntos é um tema de extrema importância para a compreensão das demais teorias 
tais como autômatos, teria da computabilidade, máquina de Turing, teoria da 
complexidade e etc. Sugerimos a leitura do capitulo 1.3 do livro Introdução aos 
Fundamentos da Computação: Linguagens e Máquinas do escritor Newton José 
Vieira que se encontra disponível na biblioteca para acesso de todos os estudantes. 
 
Considerações finais 
 Como podemos ver a importância histórica da Teoria da Computação nos remete 
ao início da matemática, sendo suas maiores contribuições a partir do século XX onde 
se destaca os trabalhos de Hilbert com o problema de decisão, com Church 
apresentando o cálculo de Lambda e a hipótese de Church e de Turing que com a 
máquina de Turing e o problema de parada nos traz a certeza de que o estudo da Teoria 
da Computação é muito além e independente do estudo do computador, já que nosso 
foco é a lógica não sendo considerado software e hardware. Contribuindo para soluções 
de questões como: Quais os limites do que pode ser computado? Existem problemas 
sem solução computacional? E não menos importante: O que é uma solução 
computável? 
 
Teoria da Computação 
 
Núcleo de Educação a Distância | Faculdade Impacta 
Referências 
DIVERIO, Tiarajú Asmuz; MENEZES, Paulo Blauth. Teoria da Computação: 
máquinas universais e computabilidade. Porto Alegre: Bookman, 2011. 
MICHAELIS. In: Michaelis Dicionário Brasileiro da Língua Portuguesa. São Paulo, 
Editora Melhoramentos, 2023. Disponível em: <https://michaelis.uol.com.br/moderno-
portugues/busca/portugues-brasileiro/linguagem/>. Acesso em: 15/04/2023. 
MICHAELIS. In: Michaelis Dicionário Brasileiro da Língua Portuguesa. São Paulo, 
Editora Melhoramentos, 2023. Disponível em: < https://michaelis.uol.com.br/moderno-
portugues/busca/portugues-brasileiro/conjunto/>. Acesso em: 17/04/2023. 
VIEIRA, Newton José. Introdução aos Fundamentos da Computação: Linguagens e 
Máquinas. São Paulo: Cengage Learning, 2006.