Come potresti "risolvere" il problema fermante se, ipoteticamente, i numeri di castoro occupato erano "piccoli"?

Question

Ho letto che se BB (N) non è diventato più veloce di tutte le sequenze calcolabili di numeri interi, è possibile risolvere il problema di fermezza e contraddire il teorema di Turing.

Sto cercando di capire come potresti farlo specificamente.Una possibilità ovvia è quella di costruire una macchina di Turing di stato N che cerca una soluzione a un problema indecidabile, quindi semplicemente attenderlo a passare le transizioni BB (N).Questo dovrebbe essere fattibile poiché BB (N), in questo scenario, è piccolo, e superando che dimostrerebbe che la macchina andava per sempre.

Ma questa non è una risposta soddisfacente perché sicuramente la decidibilità non riguarda quanto sia fattibile una procedura in pratica, ma se è decidabile in teoria - cosa succede se i computer erano abbastanza potenti da poter essere in grado di implementare questo nel nostro universo attuale doveBB (N) è molto grande?Non dovremmo semplicemente supporre che la macchina sia invece indipendente dalla teoria del numero?

Answer 1

Per seguire la strategia You delinea, dobbiamo essere fiduciosi a priori che abbiamo un limite superiore su $ BB (n) $ . Più Snappily, se $ f $ è qualsiasi funzione con $ f (n) \ ge bb (n) $ , quindi da $ f $ Possiamo calcolare il problema di arresto: data una $ N $ -State Machine , eseguilo per $ f (n) $ -Many passi.

Dal momento che il problema di interruzione non è computabile, ciò significa che nessuna tale class class="math-contenitore"> $ f $ è computabile; Questo è un fenomeno "globale". No particolare valore di $ BB $ è troppo grande da utilizzare, ma piuttosto il tasso di crescita di $ BB (N) $ Ci impedisce di avere un'intera sequenza dei limiti superiori, uno per ogni $ N $ . Come analogia di basso livello:

.

Non c'è funzione polinomiale che è sempre superiore a $ exp (n)= 2 ^ n $ . Naturalmente, questo non è perché i singoli valori di $ exp $ sono troppo grandi, ma piuttosto a causa del comportamento generale della funzione su tutti gli input .

Answer 2

.

Ma questa non è una risposta soddisfacente perché sicuramente la decidibilità non riguarda quanto sia fattibile una procedura in pratica, ma se è decidabile in teoria - cosa succede se i computer erano abbastanza potenti da poter essere in grado di implementare questo nel nostro universo attuale doveBB (N) è molto grande?

Il problema non è così tanto che BB (N) è molto grande, il problema è che non è calcolato.La tua presunta procedura decisionale non funzionerebbe perché non saprebbe se abbiamo superato le transizioni BB (N) o meno.