Aula2

Teoria da Computação
Conceitos Básicos
Prof. Rodrigo Pinto de Carvalho, Msc profrodrigocarvalho.blogspot.com Procedimento Efetivo
Definimos na aula passada como um programa é resultado de análise de computabilidade e complexidade de um problema a ser modelado.
Pode ser representado por um formalismo(Gödel).
Linguagem de programação?
Church e Kleene em 1936 utilizaram-se desse conceito para contradizer o princípio de Hilbert David.
Utilizaram-se de princípios da computabilidade e da recursividade. Turing
Propôs no mesmo ano, 1936, um formalismo para representar o procedimento efetivo. Foi a primeira máquina de computar. A máquina de Turing. Foi o primeiro trabalho a identificar e considerar programas escritos.

“O computador mais poderoso que já se construiu.”

Prática Máquina de Turing
• Uma fita infinita dividida em quadrados
• Cada quadrado ou está vazio ou contém um símbolo
• A máquina pode ler, escrever e apagar símbolos.
• Em geral os símbolos são denotados por letras do alfabeto ou por números.
• Programa = regra
• 5 regras básicas = estado atual, símbolo atual, símbolo a escrever, direção do movimento e novo estado

Máquina escreve três 1’s na fita e pára.
Considerar 3 estágios - instruções q1, q2, q3
Símbolos - 0 - casa vazia, 1 - casa escrita
E- movimento para esquerda
D - movimento para direita
Ordem de operação - leitura e depois, escrita

q1 1 q101 q1,

Q3

Q2

Q1

1

1

1

q1 E q11E q2,

q2 q2 1 q201 q2,

q2 E

q3 q3 1

q21E q3,

q3

q301 q3

Termos Básicos
Símbolo ou Caracter
Alfabeto - conjunto finito de símbolos
Cadeia de Símbolos - seqüência de zero ou mais símbolos de um conjunto(alfabeto)
Palavra - cadeia de símbolos finita

Exemplos
• A, (a,b,c,d,e.....x,z), casa, cadeira
A - Símbolo qualquer
(a,b,c,d,e.....x,z) - alfabeto a que pertence o símbolo casa - cadeia de símbolos de um conjunto cadeira - palavra

Terminologia

(ésilon) denota a cadeia vazia ou palavra vazia
*

 (alfabeto),  (todas as palavras possíveis sobre )
+ denota