Como é possível decidir se

Foi-nos dado o seguinte exercício.

Deixei

$\qquad \displaystyle f(n) = \begin{cases} 1 & 0^n \text{ occurs in the decimal representation of } \pi \\ 0 & \text{else}\end{cases}$

Prove que é computável.$f$

Como isso é possível? Até onde eu sei, não sabemos se contém todas as seqüências de dígitos (ou quais) e um algoritmo certamente não pode decidir que alguma sequência não está ocorrendo. Portanto, acho que f não é computável, porque o problema subjacente é apenas semi-decidível.$\pi$$f$

Existem apenas duas possibilidades a considerar.

• $n$$0^n$$\pi$

• $N$$0^N$$\pi$$N$

  Zeros-in-pi(n):
   if (n > N) then return 0 else return 1
  

$N$$n$$\pi$

Observe a diferença sutil com o seguinte esboço de prova proposto por gallais :

1. Pegue uma máquina de Turing aleatória e uma entrada aleatória.
2. Ou a computação continuará para sempre ou parará em algum momento e há uma função computável (constante) descrevendo cada um desses comportamentos.
3. ???
4. Lucro!

Alex ten Brink explica:

observe o que o teorema de Halting afirma: ele diz que não existe um programa único que possa decidir se um determinado programa é interrompido. Você pode facilmente criar dois programas, de modo que um deles calcule se um determinado programa pára: o primeiro sempre diz 'pára', o segundo 'não pára' - um programa sempre está certo, mas não podemos calcular qual deles deles é!

sepp2k acrescenta:

No caso do exemplo de Alex, nenhum dos algoritmos retornará o resultado correto para todas as entradas. No caso desta pergunta, um deles será. Você pode afirmar que o problema é decidível porque você sabe que existe um algoritmo que produz o resultado certo para todas as entradas. Não importa se você sabe qual é esse algoritmo. 10

Apenas postando uma pequena elaboração da resposta de JeffE.

Sabemos que existem duas funções / casos que podem calcular a função f (n):

1. Uma função que sempre retorna true (para todos os n, existe n número de 0s consecutivos)
2. Uma função que retornará true se n for menor que um número inteiro N, em que N é definido como o comprimento máximo de 0s consecutivos existentes no número irracional fornecido (caso contrário, retorna false).

Uma e apenas uma dessas funções podem estar corretas. Não sabemos qual, mas sabemos com certeza que existe uma resposta. A computabilidade requer que exista uma função que possa determinar a resposta em uma quantidade finita de etapas.

O número de etapas no caso 1 é trivialmente vinculado apenas ao retorno 1.

$N$$T_N(n)$$n < N$$N$$N$$T_N(n)$$n < N$

Embora possa não ser possível escolher entre os dois casos (embora um pareça mais provável que outro), sabemos que exatamente um deles deve estar correto.

Como observação lateral: nossa solução supõe que, embora não possamos determinar qual função provocará um valor correto, a essência da computabilidade não depende da construtibilidade da prova. Existência pura é suficiente.

A etapa 5 da tentativa de prova a seguir é injustificada e, de fato, errada - um contra-exemplo pode ser encontrado aqui . (obrigado, Yuval; parecia a parte mais esboçada do esboço). Deixei a resposta aqui, pois acho que o erro é instrutivo.

Primeiro: o par de respostas de JeffE é suficiente; f é computável de qualquer maneira.

$\pi$
$\pi$
$\pi$

$\pi$
$\pi$