Math
La macchina di Turing e i castori operosi
Un nastro di carta tra due bobine, una testina di metallo con una lampada di stato e una tabella di regole. Ogni passo si svolge come leggere, scrivere, spostare, nuovo stato; il diario in basso conserva l'intera esecuzione, e una regola modificata mantiene quella vecchia come fantasma. I record sono trovati enumerando tutte le macchine, non citati.
Cosa succede
Una macchina così piccola è una tabella e nient'altro: per ogni stato e simbolo, cosa scrivere, dove spostarsi, quale stato segue - o fermarsi. Sul banco è un apparecchio: un nastro di carta tra due bobine, una testina su rotaie con una lampada che ne mostra lo stato. Ogni passo è recitato in quattro fasi - la testina legge la cella, stampa la nuova cifra, scorre di una cella, la lampada cambia colore - e il foglio in basso tiene il diario: ogni passo dell'esecuzione come mappa di calore con l'asse del tempo. Clicca un passo per fermare lì la macchina. Clicca un gettone della tabella per cambiare una regola: l'esecuzione precedente resta come fantasma di vetro accanto alla nuova, con il passo in cui le due storie si separano. Il castoro operoso chiede quanto a lungo una macchina simile possa girare prima di fermarsi. I record qui non sono citati: tutte le 64 macchine a uno stato, tutte le 20736 a due e 1048576 a tre stati in forma normale sono costruite ed eseguite - tre stati danno al più 21 passi e al più 6 uni, da due macchine diverse. Quattro stati costano 268 milioni di macchine, così quel campione è preso come noto e verificato eseguendolo: 107 passi, 13 uni. Una macchina che raggiunge il limite di 400 passi non si è fermata, e nulla in questa scheda può dire se mai lo farà.
Equazioni del modulo
Equazioni una macchina è una tabella: per ogni (stato, simbolo) dice cosa scrivere, dove muoversi (L oppure R) e quale stato viene dopo - oppure H, arresto il nastro parte tutto a zero ed è illimitato; la finestra della scheda contiene 49 celle, abbastanza per ogni macchina che esegue S(n) - il massimo numero di passi che compie una macchina che si arresta con n stati; Σ(n) - il massimo numero di uni che una di esse lascia sul nastro trovato qui per enumerazione, non citato: n = 1 sono 64 macchine, n = 2 sono 20736, n = 3 sono 16^5 = 1048576 in forma normale (prima mossa 1RB) S(1) = 1, Σ(1) = 1; S(2) = 6, Σ(2) = 4; S(3) = 21, Σ(3) = 6 - e per n = 3 sono due macchine DIVERSE alzare il limite di passi da 25 a 200 non aggiunge nemmeno una macchina che si arresta: ogni macchina a 3-stati che si arresta, si arresta entro il passo 21 n = 4 richiederebbe 16^7 = 268435456 macchine, perciò il suo campione è preso come noto e verificato eseguendolo: 107 passi, 13 uni S(n) cresce più in fretta di qualsiasi funzione calcolabile - ecco perché la tabella qui sopra si ferma a quattro e non a dieci
