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

19

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

Ou para todo n, aparece em , ou existe am r aparece em e não. Para a primeira possibilidade ; Para o segundo iff , 0 caso contrário. $0^n$ $\pi$ $0^m$ $\pi$ $0^{m+1}$ $f(n) := 1$ $f(n) := 1$ $n \leq m$

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

Esta prova está correta?

computability 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

é um local (ou o primeiro) da sequência de

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ção

f (n, k) = m

$f(n, k) = m$

m

$m$

0^{k}

$0^k$

π

$\pi$

vzn

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 , é verdadeira ou é verdadeira). Mas no final de cada uma dessas ramificações, você sempre consegue provar que a função é computável. Portanto, não importa qual dos casos realmente ocorra na vida real, deve ser computável. (No entanto, o motivo exato pelo qual é computável será diferente, dependendo da ramificação.) $p$ $p$ $\neg p$ $f$ $f$ $f$

Ryan Williams
fonte

16

Isso está correto. É o mesmo que se segue: defina para ser a função constante se Deus existir e 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)$ $x \mapsto 0$ $x \mapsto 1$

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

Michaël Cadilhac
fonte

4

Eu iria substituir "se Deus existe" com

. :)

P \neq N P

$P \neq NP$

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

$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

não - e esse é o problema da IMO.

0^{m}

$0^m$

π

$\pi$

0^{m + 1}

$0^{m+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

certo , pois é a máquina para produzir esse

(bem, pelo menos uma máquina). É o mesmo que o exemplo de Deus (que BTW vem da Sipser): se a máquina der

, não será necessário convencê-lo de que Deus não existe. É apenas o caso.

m

$m$

m

$m$

m

$m$

0

$0$

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 ). $\pi$ $\pi$

$f$ $\exists M \in TM : f_M = 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

$\Omega$

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

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

Respostas: