(Falso?) Prova de computabilidade de uma função?

19

Considere , uma função que retorna 1 se n zeros aparecerem consecutivamente em π . Agora alguém me deu uma prova de que f ( n ) é computável:f(n)nπf(n)

Ou para todo n, aparece em π , ou existe am r 0 m aparece em π e 0 m + 1 não. Para a primeira possibilidade f ( n ) : = 1 ; Para o segundo f ( n ) : = 1 iff n m , 0 caso contrário.0nπ0mπ0m+1f(n):=1f(n):=1nm

O autor afirma que isso prova a computabilidade de , pois existe um algoritmo para calculá-lo.f(n)

Esta prova está correta?

Mike B.
fonte
2
Você pode usar o látex nas suas perguntas para torná-las mais legíveis.
Dave Clarke
7
O argumento está correto, mas não construtivo. A pessoa não está dando a você uma MT, ela está lhe dando duas e diz que uma delas está computando a função que você deseja, mas não sabe qual.
Kaveh
11
Sua versão é computável. No entanto, eu interpretei errado e acidentalmente encontrei uma versão que acredito ser incontestável. A única mudança: em vez de exatamente n zeros, pergunte se π possui no máximo n zeros. Se isso realmente acontecer, acredito que você não pode confirmá-lo, já que π possui um número infinito de dígitos e parece (não?) Que nenhum padrão volte a aparecer.
chazisop
Corrigi uma página da Wikipedia uma vez que cometeu um erro relacionado, afirmando que a existência da constante de Chaitin provava a existência de "números inteiros incontestáveis".
Geoffrey Irving
esses tipos de perguntas tendem a estar em "linguagens triviais". mas observe como geralmente uma pequena reformulação, por exemplo, onde o idioma é que m é um local (ou o primeiro) da sequência de 0 k ou -1, se não houver essa sequência, pode ser indecidível. veja também como pode ser decidido que π possui alguma sequência de dígitos? / Ciência da computaçãof(n,k)=mm0kπ
vzn

Respostas:

23

Pense dessa maneira, Mike: Essa prova está "se ramificando" em vários casos possíveis, um dos quais precisa ser verdadeiro (usando a lei do meio excluído que, para toda proposição , p é verdadeira ou ¬ p é verdadeira). Mas no final de cada uma dessas ramificações, você sempre consegue provar que a função f é computável. Portanto, não importa qual dos casos realmente ocorra na vida real, f deve ser computável. (No entanto, o motivo exato pelo qual f é computável será diferente, dependendo da ramificação.)pp¬pff f

Ryan Williams
fonte
16

Isso está correto. É o mesmo que se segue: defina para ser a função constante x 0 se Deus existir e x 1 se Deus não existir. A função resultante é uma função constante, portanto computável. O que você talvez não consiga fazer é atribuir essa função, mas a função em si é computável.f(x)x0x1

Aqui, uma das duas possibilidades é verdadeira: existe um , ou não existe. A função é a função constante x 1 ou uma função de limite simples, definida com m .mx1m

Michaël Cadilhac
fonte
4
Eu iria substituir "se Deus existe" com . :)PNP
Kaveh
Ok, desculpe pelo mal-entendido, não estou tendo problemas com a não-construtividade da prova. O problema que tenho é que nós (ou pelo menos eu) não sabemos se é computável ou não. Por que não é necessário provar isso? m
Mike B.
5
Realmente não faz sentido falar se um número inteiro é computável ou não. Qualquer que seja o valor m, existe uma máquina de Turing que a produz. É difícil encontrá-lo, é claro, mas isso não é tão diferente da situação geral: encontrar algoritmos é difícil, o que mantém muitos de nós empregados.
Aaron Roth
Eu ainda não entendi. Que máquina de Turing poderia produzir esse m? Não apenas teria que mostrar que aparece em π , mais do que isso teria que verificar se 0 m + 1 não - e esse é o problema da IMO. 0mπ0m+1
Mike B.
É dessa maneira construtiva que você está falando. Se eu lhe der uma máquina que produz esse , não é necessário convencê-lo de que esse é o m certo , pois é a máquina para produzir esse m (bem, pelo menos uma máquina). É o mesmo que o exemplo de Deus (que BTW vem da Sipser): se a máquina der 0 , não será necessário convencê-lo de que Deus não existe. É apenas o caso. mmm0
Michaël Cadilhac
14

Penso - e espero - que todo estudante de ciência da computação seja confrontado com esse problema que parece um paradoxo. É um exemplo muito bom para a diferença de computável no sentido do TCS e computável no sentido prático.

Meus pensamentos naquela época eram: "Sim, se eu soubesse a resposta, obviamente seria computável. Mas como descobrir?" O truque é livrar-se da ilusão de que você precisa descobrir se tem essa propriedade ou não. Porque isso, obviamente (leia-se: imho), não pode ser feito por uma máquina de Turing (desde que não tenhamos mais conhecimento do que temos sobre π ).ππ

fMTM:fM=f

A idéia básica da prova é: eu lhe dou uma classe infinita de funções, todas elas computáveis ​​(para mostrar; trivial aqui). Eu provo então que a função que você está procurando está nessa classe (para mostrar; distinção entre maiúsculas e minúsculas aqui). qed

Rafael
fonte
9

Sim, está certo, é computável. O problema é que sua função realmente não está produzindo a solução para uma família infinita de problemas, como é a função (digamos) de uma solução que computa uma solução para o problema de parada - portanto, não há problema com a computação. Em vez disso, você está representando na forma de função algum fato matemático único com representação finita - um número inteiro ou o fato de que f é a função constantemente 1

Ω

Encontrar o algoritmo correto, é claro, pode ser um problema difícil. Mas encontrar algoritmos corretos geralmente é difícil!

Aaron Roth
fonte
3

postar um pouco antigo, mas queria postar outra resposta.

Esta é uma prova não construtiva (ou argumento) de computabilidade. Simplesmente diz que a função deve existir em algum sentido, pois eu posso representá-la (ou indexá-la mais corretamente), no conjunto (ou universo) de funções computáveis. No entanto, ele não constrói a própria máquina (isto é, o algoritmo), nem o índice (assumindo uma enumeração eficaz de máquinas computáveis). A frase em inglês " obrigado por nada " parece, nesses casos, mais apropriada, como a seguinte:

-- Look, I proved there is water somewhere! 

Now you can be happy, while dying from thirst!

As pessoas na história da matemática discutiram bastante sobre a validade real (ou faixa de validade) e o significado de tais argumentos. O resultado final é que o mesmo tipo de argumento reaparece nos teoremas da incompletude de Goedel e se volta contra essa "suposição do universo fechado" .

Se você não gosta tanto desses argumentos, não te culpo.

Nikos M.
fonte