Castoro occupato
Un castoro impegnato è, nella teoria computazionale , una macchina di Turing che raggiunge la massima "attività operativa" (come il numero di passi compiuti o il numero di simboli scritti prima che si fermi) tra tutte le macchine di Turing di una certa lunghezza. Questi devono soddisfare determinate specifiche e devono interrompersi dopo essere stati eseguiti su nastro vuoto.
Una funzione del castoro occupato quantifica questa attività massima per un n- stato macchina di Turing ; questo tipo di funzione non può essere calcolato . Infatti, dopo un certo punto, una funzione del castoro indaffarato cresce più velocemente di qualsiasi funzione calcolabile. Determinare il castoro occupato per un insieme di macchine di Turing con n stati dati è un problema algoritmicamente insolubile; in pratica, non possiamo nemmeno sperare di risolverlo per un numero n superiore a 10.
Il concetto, introdotto nel 1962 dal matematico ungherese Tibor Radó , è uno dei primi esempi conosciuti di una funzione non calcolabile .
Nome
Il termine " castoro impegnato" è la traduzione letterale dell'espressione inglese " castoro impegnato ", che denota colloquialmente una persona industriosa e laboriosa. Il termine (e il concetto) fu introdotto nel 1962 da Tibor Radó con il nome di " gioco di castori impegnato " nel suo articolo del 1962 " Sulle funzioni non calcolabili ".
Definizione
Il occupato n- Stato gioco di castoro , introdotto da Tibor Rado, utilizza una classe di macchine di Turing , ogni membro che soddisfi le seguenti specifiche:
- La macchina ha n stati più uno speciale stato di arresto, dove n è un numero intero positivo; uno degli n stati è definito come lo stato iniziale. Sono tipicamente denominati 1, 2,…, n , 1 è lo stato iniziale o A , B , C ,…, A è lo stato iniziale.
- Utilizza un singolo nastro, che si estende all'infinito a destra ea sinistra.
- L'alfabeto della barra multifunzione è {0, 1}, dove 0 viene utilizzato come simbolo vuoto.
- La funzione di transizione della macchina tiene conto di due input:
- lo stato attuale;
- il simbolo nella cella del nastro in fase di lettura;
e restituisce tre uscite:
- il simbolo da sovrascrivere su quello della cella corrente (possibilmente lo stesso);
- la direzione del movimento, a destra oa sinistra (ovvero l'azione di spostare il nastro di un'unità a sinistra oa destra della cella corrente);
- lo stato in cui collocare la macchina (possibilmente lo stato di arresto).
La macchina si avvia su una qualsiasi cella di un nastro completamente vuoto (cioè contenente solo 0); procede quindi per iterazione della sua funzione di transizione fino a raggiungere lo stato di arresto. Se, e solo se la macchina si ferma, il numero di 1 allora presente sul nastro viene chiamato punteggio della macchina.
Il gioco del castoro indaffarato consiste nel trovare, per un dato numero n , la macchina di Turing con il punteggio massimo. Questo è il castoro impegnato con n stati.
Funzione del castoro indaffarato Σ
Definizione
La funzione del castoro indaffarato Σ: N → N è definita in modo tale che Σ ( n ) è il punteggio massimo tra tutte le macchine di Turing a 2 simboli e stati n che soddisfano le specifiche indicate nel paragrafo precedente, quando iniziano su un nastro Vergine.
Σ è una funzione ben definita: per ogni n esiste un numero finito di macchine di Turing con n stati definiti in questo modo, fino ad un isomorfismo , e quindi un numero finito di possibili tempi di esecuzione.
Il punteggio di una macchina di Turing M essendo denotato σ ( M ), qualsiasi macchina di Turing con 2 simboli en stati per i quali σ ( M ) = Σ ( n ) è chiamato un castoro occupato. Per n dato, il castoro indaffarato non è unico: ce ne sono almeno due; se M è un castoro indaffarato, è sufficiente cambiare la direzione di movimento del nastro durante una transizione allo stato di stop per ottenere un altro castoro indaffarato.
Incalcolabilità
Nel suo articolo del 1962, Tibor Radó dimostra che se f : N → N è una funzione calcolabile , allora Σ ( n )> f ( n ) per ogni n sufficientemente grande. Σ non è quindi una funzione calcolabile.
Ciò implica che è indecidibile da un algoritmo generale determinare se una macchina di Turing arbitraria è un castoro occupato: un tale algoritmo non può esistere poiché la sua esistenza consentirebbe di calcolare Σ, il che è impossibile.
Sebbene Σ sia una funzione incalcolabile, è possibile determinarne il valore per piccoli valori di n . Possiamo dimostrare senza problemi che Σ (0) = 0, Σ (1) = 1 e Σ (2) = 4, e con maggiore difficoltà di Σ (3) = 6 e Σ (4) = 13. Σ ( n ) non è noto per n > 4, sebbene siano stati stabiliti limiti inferiori .
Nel 2016, Yedidia e Aaronson hanno dimostrato che una macchina di Turing di 7.918 stati poteva enumerare l'insieme di prove deducibili nell'assiomatico ZFC , fermandosi se si trovava una contraddizione. In applicazione del secondo teorema di incompletezza di Gödel , Σ (7 918) è incalcolabile (usando solo gli assiomi di ZFC). Questo limite superiore alla calcolabilità di Σ è stato successivamente abbassato al 1919, costruendo una macchina simile per l'assiomatico ZF.
Numero massimo di passaggi
Oltre alla funzione Σ, Tibor Rado illustra la funzione del numero massimo di fasi S . Per una macchina di Turing M dell'insieme E n delle macchine di Turing a 2 simboli, n- macchine di Turing definite sopra, s ( M ) è il numero di spostamenti del nastro che M esegue prima di fermarsi. S ( n ) è quindi il numero massimo di spostamenti per E n : S : n ↦ max { s ( M ) | M ∈ E n }. Poiché queste macchine di Turing spostano il nastro ad ogni transizione o "passo" (incluso in una transizione allo stato di arresto), questo numero massimo di turni è anche il numero massimo di passaggi.
Tibor Radó ha mostrato che S non è calcolabile per la stessa ragione per cui Σ non lo è: cresce più velocemente di qualsiasi funzione calcolabile. Nota che per ogni n , S ( n ) ≥ Σ ( n ), poiché è necessario uno spostamento per scrivere un 1 sul nastro. S quindi cresce almeno alla stessa velocità di Σ, che sta già crescendo più velocemente di qualsiasi funzione calcolabile.
Le seguenti disuguaglianze sono valide per tutti gli n ≥ 1:
- S ( n ) ≥ Σ ( n )
- S ( n ) ≤ (2 n -1) .Σ (3 n +3)
- S ( n ) <Σ (3 n +6)
- Esiste una costante c tale che, per ogni n ≥ 2,
Esempi
1 stato
Se la macchina contiene un solo stato ( A ), il castoro occupato corrisponde alla seguente tabella di transizione:
| stato | Simbolo | |
|---|---|---|
| 0 | 1 | |
| A |
|
Non usato |
Da un nastro bianco, questa macchina legge prima il simbolo 0 : scrive quindi il simbolo 1 , sposta il nastro a destra e si ferma. Otteniamo così S (1) = 1 e Σ (1) = 1.
Il risultato sarebbe lo stesso se il nastro fosse spostato a sinistra anziché a destra. Se la macchina rimanesse nello stato A dopo aver spostato il nastro, riprenderebbe lo stesso processo e non si fermerebbe mai. In ogni caso, il valore della tabella di transizione per il simbolo 1 è irrilevante, una macchina del genere non può mai atterrare su una cella contenente questo simbolo.
2 stati
Per una macchina a due stati ( A e B ), il castoro occupato corrisponde alla seguente tabella di transizione:
| stato | Simbolo | |
|---|---|---|
| 0 | 1 | |
| A |
|
|
| B |
|
|
Questa macchina si ferma dopo 6 passi, con 4 1 scritto sul nastro: S (2) = 6 e Σ (2) = 4.
La tabella seguente fornisce i dettagli delle sue operazioni, iniziando con un nastro vuoto e uno stato iniziale A :
| Non | Stato iniziale |
Leggere il simbolo |
Simbolo scritto |
Mutevole | Stato successivo |
Nastro |
|---|---|---|---|---|---|---|
| 1 | A | 0 | 1 | Giusto | B | … 0 0 0 1 0 0 0… |
| 2 | B | 0 | 1 | Sinistra | A | … 0 0 0 1 1 0 0… |
| 3 | A | 1 | 1 | Sinistra | B | … 0 0 0 1 1 0 0… |
| 4 | B | 0 | 1 | Sinistra | A | … 0 0 1 1 1 0 0… |
| 5 | A | 0 | 1 | Giusto | B | … 0 1 1 1 1 0 0… |
| 6 | B | 1 | 1 | Giusto | FERMARE | … 0 1 1 1 1 0 0… |
La colonna "Ribbon" fornisce lo stato della barra multifunzione dopo un'operazione; il carattere appena scritto è in grassetto, quello su cui si trova la testina di lettura della macchina è sottolineato.
Il senso di marcia durante l'ultima operazione non ha importanza, la macchina si ferma comunque.
Se invertissimo tutte le direzioni nella tabella di transizione (“destra” invece di “sinistra” e viceversa), otterremmo anche un castoro indaffarato, la macchina si comporta esattamente come quella sopra descritta.
Questa macchina molto semplice è già descritta da Tibor Radó nel suo articolo iniziale del 1962.
3 stati
Per una macchina a tre stati ( A , B e C ), il castoro occupato che produce più 1 corrisponde alla seguente tabella di transizione:
| stato | Simbolo | |
|---|---|---|
| 0 | 1 | |
| A |
|
|
| B |
|
|
| VS |
|
|
Questa macchina si ferma dopo 14 passaggi con 6 1 sul nastro.
A differenza del caso con 2 stati, questa macchina non è quella che si ferma dopo il maggior numero di passaggi. Ce n'è un altro che è il castoro indaffarato che produce il maggior numero di passaggi, ma che produce meno di 1 :
| stato | Simbolo | |
|---|---|---|
| 0 | 1 | |
| A |
|
|
| B |
|
|
| VS |
|
|
Questa macchina si ferma dopo 21 passaggi con 5 1 sul nastro.
Otteniamo così S (3) = 21 e Σ (3) = 6, ma per due distinte macchine di Turing. Questo risultato è stato descritto da Tibor Radó già nel 1962.
4 stati
Per una macchina a quattro stati, il castoro occupato corrisponde alla seguente tabella di transizione:
| stato | Simbolo | |
|---|---|---|
| 0 | 1 | |
| A |
|
|
| B |
|
|
| VS |
|
|
| D |
|
|
Questa macchina si ferma dopo 107 passaggi con 13 1 sul nastro. Questi non sono consecutivi, lo stato finale del nastro è il seguente: ... 0 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 ...
5 stati
Da 5 stati, i castori impegnati non sono noti. Per 5 stati, la macchina più attiva è la seguente:
| stato | Simbolo | |
|---|---|---|
| 0 | 1 | |
| A |
|
|
| B |
|
|
| VS |
|
|
| D |
|
|
| E |
|
|
Questa macchina produce 4.098 1 in 47.176.870 passi. Gli 1 non sono consecutivi: 8 191 0 sono intervallati. Scoperta nel 1989, non si sa se sia il vivace castoro di questa classe di macchine di Turing: nel 2003, c'erano 43 macchine di questo tipo la cui possibile esecuzione perpetua non era stata provata.
6 stati
Per 6 stati, la macchina più attiva è la seguente:
| stato | Simbolo | |
|---|---|---|
| 0 | 1 | |
| A |
|
|
| B |
|
|
| VS |
|
|
| D |
|
|
| E |
|
|
| F |
|
|
Questa macchina produce circa 3,515 × 10 18 267 1 in circa 7,412 × 10 36 534 passi. È stato scoperto nel giugno 2010.
Generalizzazione
È possibile generalizzare il problema a macchine di Turing comprendenti n stati em simboli, portando alle seguenti funzioni generalizzate:
- Σ ( n , m ): il numero massimo di simboli diverso da 0 scritti da una macchina con n stati em simboli;
- S ( n , m ): il numero massimo di passi compiuti da una macchina con n stati em simboli.
Con 2 stati e 3 simboli, il castoro occupato è la seguente macchina, che si ferma dopo 38 passi, il suo nastro comprende 9 simboli "2" (e 1 "1"):
Con 3 stati e 3 simboli, la macchina più attiva nota si ferma dopo 119 112 334 170 342 540 passi, il suo nastro contiene 374 676 383 copie dello stesso simbolo. Non è noto se questo sia il castoro indaffarato per questa combinazione di stati e simboli.
Valori noti
I valori di Σ ( n ) e S ( n ) sono noti solo per n <5. Per tutti gli altri, nella migliore delle ipotesi si conoscono solo i limiti inferiori .
Nel 1964, Milton Green costruì una serie di torni che dimostrano che per k ≥ 2:
dove è la notazione delle frecce di Knuth e A è la funzione di Ackermann .
In tal modo :
(dove l'ultimo termine è una torre di 3 27 = 7625 597 484 987 esponenti), e:
dove g 1 è l'enorme valore iniziale della sequenza che definisce il numero di Graham .
Le tabelle seguenti elencano i valori esatti e i limiti inferiori di S ( n , m ) e Σ ( n , m ) per n ed m ≤ 6. Il “? Sono più grandi del massimo delle voci alla loro sinistra o sopra: non si trovano nelle pubblicazioni di ricerca o sono state sovrascritte da macchine più piccole.
| 2 stati | 3 stati | 4 stati | 5 stati | 6 stati | |
|---|---|---|---|---|---|
| 2 simboli | 6 | 21 | 107 | ≥ 47176 870 | ≥ 7,4 × 10 36.534 |
| 3 simboli | 38 | ≥ 119 112334 170342 540 | ≥ 1,0 × 10 14.072 | ? | ? |
| 4 simboli | ≥ 3932 964 | ≥ 5,2 × 10 13.036 | ? | ? | ? |
| 5 simboli | ≥ 1,9 × 10.704 | ? | ? | ? | ? |
| 6 simboli | ≥ 2,4 × 10 9 866 | ? | ? | ? | ? |
| 2 stati | 3 stati | 4 stati | 5 stati | 6 stati | |
|---|---|---|---|---|---|
| 2 simboli | 4 | 6 | 13 | ≥ 4098 | ≥ 3,5 × 10 18 267 |
| 3 simboli | 9 | ≥ 374 676 383 | ≥ 1,3 × 10 7.036 | ? | ? |
| 4 simboli | ≥ 2.050 | ≥ 3,7 × 10 6.518 | ? | ? | ? |
| 5 simboli | ≥ 1,7 × 10352 | ? | ? | ? | ? |
| 6 simboli | ≥ 1,9 × 10 4.933 | ? | ? | ? | ? |
Riferimenti
- (it) Tibor Rado , “ sulle funzioni non computabile ” , Campana Systems Technology Journal , vol. 41, n ° 3,Maggio 1962, p. 877-884 ( leggi in linea )
- Infatti, un argomento più semplice (alla base della dimostrazione di Radó) è che se questa domanda fosse decidibile, sarebbe facile risolvere il problema dell'arresto .
- Seguendo A028444 di OEIS
- L'ottimesimo numero di Busy Beaver sfugge alla teoria degli insiemi ZF: nuovo articolo di Adam Yedidia e me
- enumeratori a prova di metamath e altre cose
- (en) Pascal Michel, “ indagine storica di Busy Beavers ” ,Giugno 2012
- (a) Heiner Marxen, " Busy Beaver a due stati (di T.Rado) " ,6 luglio 2010
- (in) Heiner Marxen, " Busy Beaver a 3 stati (la maggior parte) (di T.Rado) " ,6 luglio 2010
- (a) Heiner Marxen, " Busy Beaver a 3 stati (la maggior parte dei passaggi) (di T.Rado) " ,6 luglio 2010
- (a) Heiner Marxen, " Busy Beaver a 4 stati (di A.Brady) " ,6 luglio 2010
- (a) Heiner Marxen, " TM # 1 a 5 stati da MaBu-List " ,6 luglio 2010
- (in) Georgi Georgiev (Skelet), " Busy Beaver nonregular machinery for class TM (5) " ,16 maggio 2003
- (en) Heiner Marxen, " 6 simbolo a 2 stati #b (Pavel Kropitz) " ,6 luglio 2010
- (in) Heiner Marxen, " 2-state 3-symbol Attualmente migliore (di Brady / Michel) " ,6 luglio 2010
- (in) Heiner Marxen, " 3-state 3-symbol #b (TJ & S. Ligocki) " ,6 luglio 2010
- (in) Milton W. Green , " Un limite inferiore è la funzione Sigma di Rado per le macchine di Turing binarie " , Atti del 1964 del quinto simposio annuale sulla teoria della commutazione di circuito e sul design logico ,1964, p. 91-94 ( DOI 10.1109 / SWCT.1964.3 )
- (a) Marxen Heiner, " Busy Beaver " ,7 novembre 2011
Vedi anche
Bibliografo
- Lin, Shen e Radó, Tibor (1965), Computer Studies of Turing Machine Problems , Journal of the Association for Computing Machinery, vol. 12, n. 2 (aprile 1965), p. 196-212 . Ciò include la tesi di Lin, che ha dimostrato che dimostrando che tutte le macchine a tre stati e due simboli non si fermano mai se non si fermano dopo 21 passaggi.
- Brady, Allen H. (1983), La determinazione del valore della funzione non calcolabile di Rado Sigma (k) per macchine di Turing a quattro stati, Matematica del calcolo, vol. 40, n o 162 (aprile 1983), p. 647-665 . Una dimostrazione di = 13
Articoli Correlati
link esterno
- (it) Busy Beaver ( MathWorld )
- (en) Busy Beaver - Risultati attualmente noti (Heiner Marxen)
- (en) Indagine storica su Busy Beavers (Pascal Michel)