Incomputabilidade de uma função baseada na função Busy Beaver

Jan 12 2021

Deixar $\log _b^ac$denotam uma base iterada$b$função logaritmo. Por exemplo,$$\log _2^3({2^{65536}}) = {\log _2}({\log _2}({\log _2}({2^{65536}}))) = 4.$$

Escolha um modelo arbitrário M de máquinas de Turing, supondo que uma máquina opere com o alfabeto de dois símbolos:$0$ como o símbolo em branco e $1$como o símbolo não vazio. Chamaremos essas máquinas de “máquinas-M”.

Deixar $f(n)$ denotam o número máximo de símbolos não em branco que podem ocorrer na fita quando uma máquina M particular para, assumindo que todas as máquinas começam com a entrada em branco e a tabela de instruções contém no máximo $n$ estados operacionais.

Então a função $F(n)$ é definido da seguinte forma: $${F}(n) = \left\{ \begin{array}{l} 0\quad {\text{if}}\;{x_n}\;{\text{is even}}{\text{,}}\\ 1\quad {\text{if}}\;{x_n}\;{\text{is odd}}{\text{,}} \end{array} \right.$$ Onde $x_n$ é o menor número natural tal que $$\log _{{f}(n) + 2}^{x_n}({f}(n + 1) + 3) < 2.$$

Pergunta: é a função $F(n)$ incomputável para qualquer modelo M (ou seja, não existe uma máquina M que pode calcular o $F(n)$função, não importa qual M escolhermos)? Se sim (ou não), é possível comprovar isso?

EDITAR
Suponha que escolhemos um modelo descrito na seção "O jogo" no artigo "Busy Beaver" da Wikipedia . É$F$incomputável por essas máquinas? Também estou interessado em como provar isso.

Respostas

3 Arno Jan 13 2021 at 10:53

O logaritmo aninhado não faz muito aqui. É uma função computável com um inverso computável e, portanto, as funções$n \mapsto x_n$ e $f$ não são apenas equivalentes a Turing, mas relacionados por meio de redimensionamento computável.

Como tal, a resposta a esta pergunta se aplica aqui também.

Certamente poderíamos configurar nossas máquinas de Turing de forma que nunca escrevessem um número total de símbolos não vazios caindo em uma faixa que faria $x_n$chance. Precisaríamos fazer alguns cálculos paralelos para descobrir intervalos aceitáveis, mas dado o tamanho dos intervalos, espero que os símbolos de que precisamos para determinar o próximo intervalo que podemos usar eventualmente não nos tirem do intervalo.

Por outro lado, para uma configuração natural, não vejo razão para $F$jamais seria computável. Mas realmente provar isso para uma configuração específica exigiria pensar muito mais sobre os detalhes de um modelo de máquina de Turing específico do que eu gostaria.