Diferenças entre edições de "Problema da parada"

127 bytes removidos ,  21h35min de 7 de dezembro de 2011
m
(Desfeita a edição 27894036 de Salebot)
 
==Esboço da Prova==
A prova mostra que não há uma [[função parcial]] [[função computável|computável]] que decide se um programa arbitrário ''i'' pára com uma entrada arbitrária ‘’x’’''x'', isto é, a seguinte função ‘’h’’''h'' não é computável:
:<math>h(i,x) =
\begin{cases}
<div style="margin-right: 1em;">
<small>
Possíveis valores para uma função parcial computável ‘’f’’''f'' organizada em uma tabela bidimensional. As células laranjas são a diagonal. Os valores de ‘’f’’''f''(‘’i’’''i'', ‘’i’’''i'') e ‘’g’’''g''(‘’i’’''i'') são demonstrados no fundo. ‘’U’’''U'' indica que a função ‘’g’’''g'' é indefinida para um valor de entrada em particular.</small></div>
</div>
 
Neste caso, o ‘’programa''programa i’’i'' se refere ao programa ‘’i’’''i'' em uma [[enumeração]] de todos os programas de um modelo [[Turing-completa|Turing completo]] fixo de computação.
A prova segue estabelecendo que total função parcial computável com dois argumentos se diferencia da função necessária ‘’h’’''h''. Com esta finalidade, dada qualquer função parcial computável binária ‘’f’’''f'', a seguinte [[função parcial]] ‘’g’’''g'' também é computável por um certo programa ‘’e’’''e'':
:<math>g(i) =
\begin{cases}
É seguida a definição de ''g'' que exatamente um dos dois casos deve ser verdadeiro:
* ''g''(''e'') = ''f''(''e'', ''e'') = 0. Neste caso ''h''(''e'',''e'') = 1, porque o programa ''e'' pára com a entrada ''e''.
* ''g''(''e'') é indefinido e ''f''(''e'',''e'') ? 0. Neste caso ''h''(''e'',''e'') = 0, porque o programa ''e'' não pára com a entrada ''e''.
Em qualquer caso, ''f'' não pode ser a mesma função que ''h'', porque ''f'' foi uma função parcial computável ''arbitrária'' com dois argumentos, todas estas funções devem divergir de ''h''.
 
Esta prova é análoga ao [[Argumento de diagonalização de Cantor]]. O indivíduo deve visualizar um array bidimensional com uma coluna e uma linha para cada número natual, como indicado na tabela acima. O valor de ''f''(''i'',''j'') é colocado na coluna ''i'', linha ''j''. Porque assumimos que ''f'' deve ser uma função parcial computável, qualquer elemento do array pode ser calculado usando ''f''. A construção da função ''g'' pode ser visualizada utilizando a diagonal principal deste array. Se o array tem um 0 na posição (''i'',''i''), então ''g''(''i'') é 0. Caso contrário ''g''(''i'') é indefinido. A contradição vem do fato que existe uma coluna ''e'' do array correspondendo ao ''g''. Se ''f'' fosse a função de parada ''h'', haveria um 1 na posição (''e'',''e'') se e somente se ''g''(''e'') for definido, mas ''g'' é construído de forma que se e somente se há um 0 na posição (''e'',''e'').
 
 
== Histórico do problema da parada ==
9

edições