Outras abordagens à

computabilidade

3.1

Nota
• Os presentes acetatos foram baseados
quase na sua totalidade nos acetatos
realizados pela Professora Teresa
Galvão da Universidade de Porto para a
cadeira Teoria da Computação I, a cargo
do Professor João Falcão e Cunha.
• Agradecemos-lhes pela permissão para
utilizar o material.
3.2

1
 3. Outras abordagens à computabilidade

3.1 Outras abordagens à computabilidade

3.2 Funções parciais recursivas
3.3 Funções recursivas primitivas
3.4 Computabilidade de Turing
3.5 Sistemas de Post e Markov
3.6 Computabilidade noutros domínios
3.7 Tese de Church

3.3

3.1 Outras abordagens à computabilidade

Nos últimos 70 anos têm sido apresentadas diferentes propostas para

uma completa caracterização matemática da noção intuitiva de
computabilidade. A abordagem URM é uma das mais recentes.
Algumas das abordagens alternativas são as seguintes:
(a) Gödel-Herbrand-Kleene (1936) Funções recursivas gerais definidas por
cálculo equacional
(b) Church (1936) Cálculo lambda ( λ -calculus)
(c) Gödel-Kleene (1936) Funçõesµ -recursivas e funções parciais recursivas
(d) Turing (1936) Funções computáveis por máquinas de Turing
(e) Post (1943) Funções definidas por sistemas de dedução canónicos
(f) Markov (1951) Funções dadas por certos algoritmos em alfabetos finitos
(g) Shepherdson-Sturgis (1963) Funções computáveis por URM

3.4

2
 3.1 Outras abordagens à computabilidade

Resultado fundamental

Cada uma das anteriores propostas para uma completa

caracterização da noção de computabilidade efectiva dá
origem à mesma classe de funções , a classe C .

3.5

3.2 Funções parciais recursivas (Gödel-Kleene)

Definição
A classe R das funções parciais recursivas é a menor classe de
funções parciais que contém as funções básicas 0, x+1, Uin e é
fechada para a substituição, recursão e minimização.

(Ou seja, R é a classe de funções parciais que podem ser geradas a partir das funções
básicas por um número finitos de operações de substituição, recursão e minimização.)
Note-se que nenhuma restrição é colocada ao uso do operador- µ , logo R contém
funções não totais.

Teorema: R =C

3.6

3
 3.3 Funções recursivas primitivas

Definição
A classe PR das funções recursivas primitivas é a menor
classe de funções que contém as funções básicas 0, x+1,
Uin e é fechada para a substituição e recursão.

Notas:
• PR é fechada para a soma, produto e minimização limitadas.
• Nem todas as funções computáveis são recursivas primitivas
(cf. Função de Ackermann).

3.7

Alan Turing

Alan Turing nasceu em 1912 em Londres.

Turing interessou-se por uma das questões levantadas por Russel, que consistia
na possibilidade de mecanizar o raciocínio matemático, capturando num único
sistema todos os princípios válidos da matemática. Nesse sistema, as verdades
fluiriam mecânicamente como consequências imediatas de um pequeno
conjunto de axiomas (como automóveis numa linha de produção).
Quando, em 1931, o austríaco Kurt Gödel demonstrou a impossibilidade de uma
perfeita formalização do raciocínio matemático, dada a existência de
proposições indecidíveis em qualquer sistema axiomático consistente, Turing
tentou construir um sistema que fosse capaz de determinar se uma proposição
era indecidível nesse sistema.
Surge então a Máquina de Turing.

3.8

4
 Alan Turing
A máquina de Turing, considerada como um precursor do computador, foi
inventada em 1936, dez anos antes de serem construídos os primeiros
computadores. Mais tarde, Turing foi um dos pioneiros do seu desenvolvimento.
Entretanto, durante os anos da 2ª guerra mundial, Turing foi destacado para
auxiliar a descodificação das mensagens dos alemães. A sua contribuição foi
fundamental para a localização dos submarinos germânicos.
No final da guerra tentou conseguir fundos para a construção de uma máquina
inteligente. Nunca os conseguiu.
Morreu com 41 anos, provavelmente por suicídio.

3.9

“As máquinas podem pensar ?”

Turing chegou à conclusão que a construção de uma máquina que detectasse (e

eliminasse) de um sistema as suas proposições indecidíveis era impossível,
confirmando o resultado de Gödel.
Contudo, Turing sempre acreditou na possibilidade de criar uma máquina
“inteligente” e num célebre artigo, descreveu um jogo, conhecido agora como o
Teste de Turing:
“ Três pessoas: um homem (A), uma mulher (B) e o interrogador (C) (pode ser
de qualquer sexo). O interrogador encontra-se numa sala, separado dos outros
dois. O objectivo do jogo é o interrogador determinar quem é o homem e quem é
a mulher. Ele conhece-os pelas letras X e Y. No final, deve dizer: X é A e Y é B.
O interrogador pode colocar questões a ambos, mas desconhece que o objectivo
de A é enganá-lo e o de B é ajudá-lo. O que acontece se for um computador a
fazer o papel de A ? O interrogador enganar-se-á tantas vezes quantas as que
se engana quando o jogo é entre um homem e uma mulher?”

3.10

5
 3.4 Computabilidade de Turing
Máquina de Turing Símbolo ‘em branco’

Fita A B A ^ 3 ^ ^ ^

{
0 1 2 3 4 5 6 7

Símbolos do alfabeto S
Número do registo
(não visível para a fita)
Conjunto de estados
estado inicial

estados finais

Tabela de instruções
{ Cabeça da Máquina de Turing

3.11

3.4 Computabilidade de Turing

Componentes da Máquina de Turing

Uma máquina de Turing consiste numa fita e numa cabeça que se move para a
esquerda e para a direita, lendo ou escrevendo à medida que se move. Em cada
momento, a máquina encontra-se num dado estado, de entre um conjunto finito
de estados possíveis. Dependendo do estado em que se encontra, uma tabela
de instruções comunica-lhe a acção a executar.

A fita
É a memória da MT. É composta por um conjunto infinito de registos, numerados
de 0, 1,...

O alfabeto
Em cada registo é escrito um único símbolo, pertencente a um alfabeto finito
com n símbolos. Este alfabeto tem pelo menos dois símbolos, um dos quais é o
símbolo “em branco” ( ^), que significa que o registo está vazio.
3.12

6
 3.4 Computabilidade de Turing

A cabeça de leitura e escrita

Permite ler e escrever num dado registo da fita.

O conjunto de estados
Em cada momento a máquina encontra-se num determinado estado. O
conjunto finito de estados possíveis é descrito por {q1,…, qm}.

A tabela de instruções (Especificação)

A acção a executar em cada momento depende do estado em que a
máquina se encontra e do símbolo que está a ser lido. A especificação é
um conjunto finito de instruções.

3.13

3.4 Computabilidade de Turing

Os quádruplos têm a seguinte forma: qi sj a ql , onde 1 ≤ i, l ≤ m e

0 ≤ j, k ≤ n

De acordo com cada instrução, amáquina opera do modo seguinte:

(1) Se a máquina se encontra no estado qi e o símbolo a ser lido é sj ,
então:
Se a = sk, apaga sj e escreve sk no registo corrente;
Se a = R, move a cabeça para a direita;
Se a = R, move a cabeça para a esquerda;
(2) A máquina passa para o estado ql .
Para cada par qi sj , deve existir, no máximo, um quádruplo da forma
qi sj a ql , para evitar ambiguidades.

3.14

7
 3.4 Computabilidade de Turing

Para iniciar a execução de uma MT é necessário que a cabeça esteja colocada

na posição inicial e que um estado inicial seja atribuído.
A execução termina quando, num dado estado qi , ao ser lido o símbolo sj , não
existe nenhum quádruplo da forma qi sj a ql .
Exemplo: Seja M uma máquina de Turing cujo alfabeto consiste nos símbolos 0,
1 ( e o símbolo em branco) e os estados possíveis são q1 e q2 . A especificação
de M é:
Início
q1 0 R q1
1 1 1 1 1 1 1 1 1 1
q1 1 0 q2
q2 0 R q2 Fim
q2 1 R q1
0 1 0 1 0 1 0 1 0 1

3.15

3.4 Computabilidade de Turing

Formas de representação da especificação de uma MT

Relativamente ao exemplo anterior, podemos escrever o conjunto de instruções
da máquina de formas distintas e equivalentes:

Lista de quádruplos Tabela Grafo

q1 0 R q1
Sím bo lo lid o 0: R
0: R
q1 1 0 q2 0 1 1: 0
q2 0 R q2 E stad o q1 R q1 0 q2 q1 q2
corrente q2 R q2 R q1
q2 1 R q1 1: R

3.16

8
 3.4 Computabilidade de Turing

Exercício
O que faz a seguinte máquina de Turing?
O alfabeto é {1, B}, onde B é o símbolo “em branco”. A máquina começa a ler o
símbolo mais à esquerda e a expressão é uma lista contínua e finita de 1’s.
Sugestão: Experimente com as expressões 111, 1111, 111111.

q2
1: B B: R

B: 1
q1 q3 q5

B: R 1: B
q4

3.17

3.4 Computabilidade de Turing

Definição
Uma função é Turing-computável se existir um máquina de Turing que a
compute. A classe de todas as funções Turing-computáveis é designada
por T C.

Teorema: R =C=TC
As classes das funções parciais recursivas, computáveis por URM e
Turing-computáveis são equivalentes.

3.18

9
 3.7 Tese de Church

Relembremos a noção intuitiva e informal da classe das

funções efectivamente computáveis: classe de funções cujos valores podem
ser calculador por algoritmos ou procedimentos efectivos.

Tese de Church (ou Church-Turing)

A classe intuitiva e informal das funções efectivamente

computáveis coincide exactamente com a classe C das
funções computáveis por URM.

3.19

3.7 Tese de Church

A Tese de Church não é um teorema susceptível de demonstração matemática.

Tem um estatuto de crença, cuja veracidade é baseada em evidências:

• Diferentes propostas independentes para uma caracterização formal de

computabilidade conduziu à mesma classe de funções, designada por C.
• Mostrou-se que uma vasta coleção de funções efectivamente computáveis
pertencia a C.
• A implementação de um programa URM é um exemplo de um algoritmo.
Então, pela própria definição de C, todas as funções desta classe são
computáveis no sentido informal.
• Nunca ninguém encontrou uma função que fosse computável no sentido
informal e não pertencesse a C.

3.20

10
 3.7 Tese de Church

A Tese de Church é aceite pela grande maioria dos cientistas das mais
diversas áreas, mas é mais um resultado científico do que um resultado
matemático.
Um dia, pode ser negado por uma nova evidência.

Aplicação da Tese de Church

À luz desta evidência é comum usar a Tese de Church para provar que
uma função é computável por URM, através de um algoritmo que a
calcule. Este algoritmo pode ser explicitado através de uma linguagem
relativamente informal, mas muito rigorosa.

A este procedimento chama-se prova pela Tese de Church.

3.21

3.7 Tese de Church

É fundamental ter em consideração o seguinte:

• É ainda necessário provar com rigor que o algoritmo:

– computa a função correcta;
– pára em tempo finito, quando a função está definida;
– pode ser representado por um programa de comprimento finito;

• Quando se usa uma prova pela Tese de Church deve-se estar

preparado para construir (ou provar a existência de) um programa
URM, uma máquina de Turing ou uma função parcial recursiva
equivalente ao algoritmo proposto.

3.22

11
 O paradoxo de Russel

Um juiz condenou um homem por um crime reprovável e pretende que o castigo

seja particularmente severo. O homem é condenado à morte e a sentença será
processada da seguinte forma:
“A sentença será executada até ao próximo Sábado e, na manhã do dia da
execução não saberá de que o dia da morte chegou. Assim, quando o vierem
buscar, será uma surpresa”.
O prisioneiro, quando ouviu a sentença, respondeu: “Bem, estou aliviado, pois
de acordo com a V. sentença, eu não posso ser executado no Sábado”.
“Porquê?” perguntou o juiz. “Porque, se a sentença deve ser executada até
Sábado, e se de facto chegarmos a Sábado, eu saberei que é o dia da minha
morte e não será uma surpresa.”
“Tem razão”, disse o juiz, “não poderá ser executado no Sábado. No entanto,
não percebo porque está aliviado”.

3.23

O paradoxo de Russel (cont.)

“Bem”, disse o prisioneiro, “porque se definitivamente não posso ser executado

no Sábado, pela mesma razão também não posso ser executado na sexta-feira.
Mais ainda, se continuarmos o raciocínio, devo concluir que não posso sequer
ser executado hoje”.
O juiz coçou a cabeça e enviou o prisioneiro de volta para a cela. Na quinta-feira,
foi executado. Ficou muito surpreendido.
Logo, as ordens do juiz foram cumpridas com sucesso.

Seja A um conjunto com a seguinte propriedade: A contém todos os conjuntos

que não são membros de si próprios.

Pergunta: A é membro de si próprio?

3.24

12
 O paradoxo de Russel (cont.)

Como Russel resolveu todos os paradoxos:

Russel redefiniu o conceito de conjunto :

No sentido estrito
Um conjunto tem uma definição que permite a construção de um programa que
determina se uma dada entidade é membro do conjunto em tempo finito.
De acordo com esta definição A não é um conjunto e o paradoxo é eliminado.
No sentido lato
O programa que define as regras de pertença a um conjunto não necessita de
terminar em tempo finito. Apenas necessita de dar uma resposta em tempo finito.
Pode alterar a sua resposta à medida que o programa corre.
Assim, A será membro de si próprio num dado instante e não o será num outro. A
resposta nunca é Sim e Não ao mesmo tempo. Alterna entre as duas.

3.25

Implicações da Tese de Church

Mas, resolvidos os paradoxos, existem ainda problemas insolúveis.

Turing provou a existência de problemas bem definidos, com uma única solução
(que se pode provar que existe), mas que não pode ser calculada por uma
Máquina de Turing.
Church e Turing procuram demonstrar que esta simples máquina pode resolver
qualquer problema que uma máquina é capaz de resolver. Se um problema não
pode ser resolvido por uma máquina de Turing, também não pode ser resolvido
por nenhuma outra máquina (… nem pelo homem).
Mais ainda,
de acordo com Church e Turing, cabe-nos a nós, humanos, definir um problema,
provar que tem uma única solução, encontrá-la, e ainda provar que nenhuma
máquina de Turing é capaz de o resolver.
Ainda ninguém conseguiu...

3.26

13
 Implicações da Tese de Church

Os dois lados da Tese de Church:

Negativo
Os problemas que não podem ser resolvidos por uma máquina de Turing
também não podem ser resolvidos pelo raciocínio humano. Aceitando esta tese,
existem problemas cujas soluções existem e não podem nunca ser encontradas.

Positivo
Se o homem pode resolver um dado problema, então é possível construir uma
máquina que o resolva também.
A inteligência artificial é uma tentativa de fornecer uma aplicação prática da Tese
de Church.

3.27

14