Número descritivo

Origem: Wikipédia, a enciclopédia livre.

Descritores são números que surgem na teoria das máquinas de Turing. Eles são muito semelhantes aos números de Gödel, e também são ocasionalmente chamado "números de Gödel" na literatura. Dada alguma máquina de Turing universal, cada máquina de Turing pode, dada a sua codificação naquela máquina, ser atribuída à um número. Este é o número de descrição da máquina. Estes números desempenham um papel-chave na prova de Alan Turing sobre a indecidibilidade do problema da parada, e também são muito úteis no raciocínio sobre máquinas de Turing .

Um exemplo de descritor[editar | editar código-fonte]

Digamos que temos uma máquina de Turing M com os estados q1, ... qR, com um alfabeto de fita com símbolos s1, ... sm, com o simbolo branco indicado por s0, e transições dando o estado atual, símbolo atual, e as ações realizadas (que poderia ser a de substituir o símbolo atual da fita e mover a cabeça da fita à esquerda ou à direita, ou talvez não movê-lo de jeito nenhum), e o próximo estado. Sob a definição da máquina original universal descrita por Alan Turing, esta máquina seria codificada como entrada para a máquina universal como se segue:

  1. O estado qi é codificada pela letra "D" seguido da letra 'A' repetida i vezes (uma codificação unária)
  2. O símbolo de fita sj é codificada pela letra "D" seguido da letra 'C' repetida j vezes
  3. As transições são codificados, dando-se o Estado, o símbolo de entrada, o símbolo para escrever na fita, a direção para mover (expresso pelas letras 'L', 'R', ou 'N', respectivamente: esquerda, direita, ou sem movimento), e o próximo estado , com estados e símbolos codificados como acima.

As entradas de UTM, assim, consistem nas transições separados por ponto e vírgula, dessa forma seu alfabeto de entrada consiste dos sete símbolos, 'D', 'A', 'C', 'L', 'R', 'N' e ';' . Por exemplo, para uma máquina de Turing muito simples que alterna de impressão 0 e 1 na sua fita para sempre:

  1. Estado: q1 símbolo de entrada: branco, ação: escrever 1, mova para a direita, próximo estado: q2
  2. Estado: q2, símbolo de entrada: branco, ação: escrever 0,mova para a direita, próximo estado: q1

Sendo o simbolo branco s0, '0 'ser s1 e '1' ser s2, a máquina seria codificado pelo UTM como: DADDCCRDAA; DAADDCRDA; Mas depois, se nós substituíssemos cada um dos sete símbolos 'A' por 1, 'C' por 2, 'D' de 3, 'L' por 4, 'R' por 5, 'N' por 6, e '; 'por 7, nós teríamos uma codificação da máquina de Turing como um número natural: este é o número de descrição(descritor) da máquina de Turing em relação à máquina universal de Turing. A máquina de Turing simples descrita acima teria, assim, o número 313322531173113325317 como descritor. Há um processo análogo para qualquer outro tipo de máquina de Turing universal. Geralmente não é necessário realmente computar um número de descrição(descritor) desta maneira: o ponto é que cada número natural pode ser interpretado como um código para, no máximo, uma máquina de Turing, embora muitos números naturais não podem ser um código para um máquina de Turing (ou dito de outra maneira, eles representam máquinas Turing que não possuem estados). O fato de que tal número sempre existe para alguma máquina de Turing é que é o mais importante no geral.

Aplicação em provas de indecidibilidade[editar | editar código-fonte]

Descritores desempenham um papel fundamental em muitas provas de indecidibilidade, tais como a prova de que o problema da parada é indecidível. Em primeiro lugar, a existência desta correspondência direta entre números naturais e máquinas de Turing mostra que o conjunto de todas as máquinas de Turing é enumerável, e desde que o conjunto de todas as funções parciais é incontável infinito, deve com certeza existir muitas funções que não podem ser calculadas por máquinas de Turing.

Ao fazer uso de uma técnica semelhante ao argumento diagonal de Cantor, é possível exibir tal função incomputavél, por exemplo, o problema da parada em particular, é indecidível. Primeiro, vamos denotar por U (e, x) a ação da máquina de Turing universal dado um número descritor "e" e um input(uma entrada) x, retornando 0 se "e" não é o número de descrição de uma máquina de Turing válida. Agora, supondo que houvesse algum algoritmo capaz de resolver o problema da parada, ou seja, uma máquina de Turing TEST (e) que, dado o número de descrição de alguma máquina de Turing iria retornar 1 se a máquina de Turing pára em cada entrada(input), ou 0 se houver alguma(s) entrada(s) que faria com que computasse para sempre. Ao combinar as saídas destas máquinas, deve ser possível construir uma outra máquina δ (k), que retorna U (k, k) + 1 se TEST(k) é 1 e 0 se TEST(k) é 0. A partir desta definição δ é definido para cada entrada e deve, naturalmente, ser totalmente recursiva. Como δ é construída a partir do que temos assumido como máquinas de Turing, então ele também deve ter um número de descrição, chamamo-lo de "e". Assim, podemos alimentar o número de descrição "e" para o UTM novamente, e por definição δ(k) = U(e, k), de modo δ(e) = U(e, e). Mas desde que a TEST(e) é 1, pela nossa outra definição, δ(e)=U(e, e)+ 1, levando a uma contradição. Assim, TEST(e) não pode existir, e desta forma temos resolvido o problema da parada como indecidível.

Ver também[editar | editar código-fonte]

Referências[editar | editar código-fonte]