Non calcolabilità di una funzione basata sulla funzione Busy Beaver

Jan 12 2021

Permettere $\log _b^ac$denotare un iterata base-$b$funzione logaritmo. Per esempio,$$\log _2^3({2^{65536}}) = {\log _2}({\log _2}({\log _2}({2^{65536}}))) = 4.$$

Scegli un modello arbitrario M delle macchine di Turing, supponendo che una macchina funzioni con l'alfabeto a due simboli:$0$ come il simbolo vuoto e $1$come simbolo non vuoto. Chiameremo tali macchine "M-macchine".

Permettere $f(n)$ denotano il numero massimo di simboli non vuoti che possono verificarsi sul nastro quando una particolare macchina M si ferma, assumendo che tutte le macchine inizino con l'input vuoto e la tabella delle istruzioni contenga al massimo $n$ stati operativi.

Quindi la funzione $F(n)$ è definito come segue: $${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.$$ dove $x_n$ è il numero naturale più piccolo tale che $$\log _{{f}(n) + 2}^{x_n}({f}(n + 1) + 3) < 2.$$

Domanda: è la funzione $F(n)$ non numerabile per qualsiasi modello M (ovvero, non esiste una macchina M che possa calcolare l'estensione $F(n)$funzione, non importa quale M scegliamo)? Se sì (o no), è possibile dimostrarlo?

MODIFICA
Supponiamo di scegliere un modello descritto nella sezione "Il gioco" dell'articolo di Wikipedia "Busy Beaver" . È$F$inconfutabile da tali macchine? Sono anche interessato a come dimostrarlo.

Risposte

3 Arno Jan 13 2021 at 10:53

Il logaritmo annidato non fa molto qui. È una funzione calcolabile con un inverso calcolabile, e quindi le funzioni$n \mapsto x_n$ e $f$ non sono solo equivalenti di Turing, ma sono correlati tramite ridimensionamento computabile.

In quanto tale, la risposta a questa domanda si applica anche qui.

Certamente potremmo impostare le nostre macchine di Turing in modo che non scrivano mai un numero totale di simboli non vuoti che rientrano in un intervallo tale da rendere $x_n$dispari. Avremmo bisogno di fare alcuni calcoli laterali per capire gli intervalli accettabili, ma data la dimensione degli intervalli mi aspetto che i simboli di cui abbiamo bisogno per determinare l'intervallo successivo che possiamo usare alla fine non ci porteranno fuori dall'intervallo.

D'altra parte, per una configurazione naturale non vedo motivo per cui $F$sarebbe mai calcolabile. Ma in realtà per provare questo per una particolare configurazione richiederebbe pensare molto di più ai dettagli di un particolare modello di macchina di Turing di quanto vorrei fare.