Castor ocupat
Un castor ocupat este, în teoria computației , o mașină Turing care realizează „activitate operațională” maximă (cum ar fi numărul de pași parcurși sau numărul de simboluri scrise înainte de oprire) dintre toate mașinile Turing cu o anumită lungime. Acestea trebuie să îndeplinească anumite specificații și trebuie să se oprească după ce sunt rulate pe bandă goală.
O funcție a castorului ocupat cuantifică această activitate maximă pentru o mașină Turing cu stare n ; acest tip de funcție nu poate fi calculat . De fapt, după un anumit punct, o funcție a castorului ocupat crește mai repede decât orice funcție calculabilă. Determinarea castorului ocupat pentru un set de mașini Turing cu n stări date este o problemă insolubilă algoritmic; în practică, nici nu putem spera să o rezolvăm pentru un număr n peste 10.
Conceptul, introdus în 1962 de matematicianul maghiar Tibor Radó , este unul dintre primele exemple cunoscute ale unei funcții necalculabile .
Numele de familie
Termenul „ castor ocupat” este traducerea literală a expresiei englezești „ ocupat castor ”, denumind în mod colocvial o persoană harnică și harnică. Termenul (și conceptul) a fost introdus în 1962 de Tibor Radó sub denumirea de „ joc de castor ocupat ” în articolul său din 1962 „ Despre funcțiile necomputabile ”.
Definiție
Jocul de castor n- state ocupat , introdus de Tibor Radó, folosește o clasă de mașini Turing , fiecare membru îndeplinind următoarele specificații:
- Mașina are n stări plus o stare specială de oprire, unde n este un număr întreg pozitiv; una dintre n stări este definită ca starea de pornire. Acestea sunt denumite în mod tipic 1, 2,…, n , 1 fiind starea inițială sau A , B , C ,…, A fiind starea inițială.
- Folosește o singură panglică, care se întinde la nesfârșit la dreapta și la stânga.
- Alfabetul panglicii este {0, 1}, cu 0 care servește ca simbol necompletat.
- Funcția de tranziție a mașinii ia în considerare două intrări:
- starea actuală;
- citirea simbolului din celula panglicii;
și returnează trei ieșiri:
- simbolul de scris peste cel al celulei curente (posibil același);
- direcția de mișcare, spre dreapta sau spre stânga (adică acțiunea de a muta panglica cu o unitate spre stânga sau spre dreapta celulei actuale);
- starea în care să setați mașina (eventual starea de oprire).
Mașina pornește pe orice celulă a unei panglici complet goale (adică conține doar 0); apoi continuă prin iterația funcției sale de tranziție până când ajunge în cele din urmă la starea de oprire. Dacă și numai dacă mașina se oprește, numărul de 1 prezent pe bandă se numește scor mașină.
Jocul castorului ocupat constă în găsirea, pentru un număr dat n , a mașinii Turing cu scorul maxim. Acesta este castorul ocupat cu n stări.
Funcția castorului ocupat Σ
Definiție
Funcția castorului ocupat Σ: N → N este definită astfel încât Σ ( n ) este scorul maxim dintre toate mașinile Turing cu 2 n- stări , care îndeplinesc specificațiile enunțate în paragraful anterior, când pornesc pe o panglică Virgin.
Σ este o funcție bine definită: pentru fiecare n , există un număr finit de mașini Turing de stare n definite în acest fel, până la un izomorfism și, prin urmare, un număr finit de timpi de execuție posibili.
Scorul unei mașini Turing M fiind notat σ ( M ), orice mașină Turing cu 2 simboluri și n stări pentru care σ ( M ) = Σ ( n ) se numește castor ocupat. Pentru n dat, castorul ocupat nu este unic: sunt cel puțin doi; dacă M este un castor ocupat, este suficient să schimbați direcția de mișcare a panglicii în timpul unei tranziții la starea de oprire pentru a obține un alt castor ocupat.
Incomensurabilitate
În articolul său din 1962, Tibor Radó demonstrează că dacă f : N → N este o funcție calculabilă , atunci Σ ( n )> f ( n ) pentru orice n suficient de mare. Prin urmare, Σ nu este o funcție calculabilă.
Acest lucru implică faptul că este indecidabil de un algoritm general să se determine dacă o mașină Turing arbitrară este un castor ocupat: un astfel de algoritm nu poate exista deoarece existența sa ar permite calcularea lui Σ, ceea ce este imposibil.
Deși Σ este o funcție incalculabilă, este posibil să se determine valoarea acesteia pentru valori mici de n . Putem arăta fără probleme că Σ (0) = 0, Σ (1) = 1 și Σ (2) = 4 și cu mai multe dificultăți decât Σ (3) = 6 și Σ (4) = 13. Σ ( n ) nu este cunoscut pentru n > 4, deși sunt stabilite limite inferioare .
În 2016, Yedidia și Aaronson au dovedit că o mașină Turing cu 7.918 stări ar putea enumera setul de dovezi deductibile în axiomaticul ZFC , oprindu-se dacă s-a găsit o contradicție. Prin aplicarea celei de- a doua teoreme a incompletitudinii lui Gödel , Σ (7 918) este incalculabil (folosind doar axiomele ZFC). Această limită superioară a calculabilității lui Σ a fost ulterior redusă la 1919, prin construirea unei mașini similare pentru axiomaticul ZF.
Numărul maxim de pași
În plus față de funcția Σ, Tibor Rado a introdus funcția numărul maxim de etape S . Pentru o mașină Turing M din setul E n al simbolului 2, mașinile Turing de stare n definite mai sus, s ( M ) este numărul de schimbări de panglică pe care M le efectuează înainte de oprire. S ( n ) este apoi numărul maxim de schimburi pentru E n : S : n ↦ max { s ( M ) | M ∈ E n }. Deoarece aceste mașini Turing schimbă panglica la fiecare tranziție sau „pas” (inclusiv într-o tranziție la starea de oprire), acest număr maxim de schimbări este, de asemenea, numărul maxim de pași.
Tibor Radó a arătat că S nu este calculabil din același motiv pentru care Σ nu este: crește mai repede decât orice funcție calculabilă. El observă că pentru toate n , S ( n ) ≥ Σ ( n ), deoarece este necesară o schimbare pentru a scrie un 1 pe bandă. Prin urmare, S crește cel puțin la fel de repede ca Σ, care crește deja mai repede decât orice funcție calculabilă.
Următoarele inegalități sunt valabile pentru toate n ≥ 1:
- S ( n ) ≥ Σ ( n )
- S ( n ) ≤ (2 n -1) .Σ (3 n +3)
- S ( n ) <Σ (3 n +6)
- Există o constantă c astfel încât, pentru toate n ≥ 2,
Exemple
1 stat
Dacă aparatul conține o singură stare ( A ), castorul ocupat corespunde următoarei tabele de tranziție:
| stat | Simbol | |
|---|---|---|
| 0 | 1 | |
| LA |
|
Nefolosit |
Dintr-o panglică goală, această mașină citește mai întâi simbolul 0 : prin urmare, scrie simbolul 1 , mută panglica spre dreapta și se oprește. Prin urmare, obținem S (1) = 1 și Σ (1) = 1.
Rezultatul ar fi același dacă panglica ar fi fost mutată mai degrabă spre stânga decât spre dreapta. Dacă mașina a rămas în starea A după ce a mutat panglica, ar începe din nou același proces și nu se va opri niciodată. În orice caz, valoarea tabelului de tranziție pentru simbolul 1 este irelevantă, o astfel de mașină nu poate ateriza niciodată pe o celulă care conține acest simbol.
2 state
Pentru o mașină cu două stări ( A și B ), castorul ocupat corespunde următoarei tabele de tranziție:
| stat | Simbol | |
|---|---|---|
| 0 | 1 | |
| LA |
|
|
| B |
|
|
Această mașină se oprește după 6 pași, cu 4 1 scris pe bandă: S (2) = 6 și Σ (2) = 4.
Următorul tabel oferă detaliile operațiunilor sale, începând cu o bandă goală și o stare inițială A :
| Nu | Starea inițială |
Citiți simbolul |
Simbol scris |
Schimbare | Următoarea stare |
Panglică |
|---|---|---|---|---|---|---|
| 1 | LA | 0 | 1 | Dreapta | B | … 0 0 0 1 0 0 0… |
| 2 | B | 0 | 1 | Stânga | LA | … 0 0 0 1 1 0 0… |
| 3 | LA | 1 | 1 | Stânga | B | … 0 0 0 1 1 0 0… |
| 4 | B | 0 | 1 | Stânga | LA | … 0 0 1 1 1 0 0… |
| 5 | LA | 0 | 1 | Dreapta | B | … 0 1 1 1 1 0 0… |
| 6 | B | 1 | 1 | Dreapta | STOP | … 0 1 1 1 1 0 0… |
Coloana „Panglică” oferă starea panglicii după o operație; caracterul care tocmai a fost scris este cu caractere aldine, cel pe care se află capul de citire al aparatului este subliniat.
Direcția de deplasare în timpul ultimei operații nu contează, mașina oprindu-se oricum.
Dacă am inversa toate direcțiile din tabelul de tranziție („dreapta” în loc de „stânga” și invers), am obține și un castor ocupat, mașina comportându-se exact ca cea descrisă mai sus.
Această mașină foarte simplă a fost deja descrisă de Tibor Radó în articolul său inițial din 1962.
3 state
Pentru o mașină cu trei stări ( A , B și C ), producând cele mai castor ocupat 1 corespunde cu următorul tabel de tranziție:
| stat | Simbol | |
|---|---|---|
| 0 | 1 | |
| LA |
|
|
| B |
|
|
| VS |
|
|
Această mașină se oprește după 14 pași cu 6 1 pe bandă.
Spre deosebire de cazul cu 2 stări, această mașină nu este cea care se oprește după cel mai mare număr de pași. Există un altul, care este castorul ocupat care produce cei mai mulți pași, dar care produce mai puțin de 1 :
| stat | Simbol | |
|---|---|---|
| 0 | 1 | |
| LA |
|
|
| B |
|
|
| VS |
|
|
Această mașină se oprește după 21 de pași cu 5 1 pe bandă.
Astfel, obținem S (3) = 21 și Σ (3) = 6, dar pentru două mașini Turing distincte. Acest rezultat a fost descris de Tibor Radó încă din 1962.
4 state
Pentru o mașină cu patru stări, castorul ocupat corespunde următorului tabel de tranziție:
| stat | Simbol | |
|---|---|---|
| 0 | 1 | |
| LA |
|
|
| B |
|
|
| VS |
|
|
| D |
|
|
Această mașină se oprește după 107 pași cu 13 1 pe bandă. Acestea nu sunt consecutive, starea finală a panglicii fiind următoarea: ... 0 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 ...
5 state
Din 5 state, castorii ocupați nu sunt cunoscuți. Pentru 5 stări, cea mai activă mașină este după cum urmează:
| stat | Simbol | |
|---|---|---|
| 0 | 1 | |
| LA |
|
|
| B |
|
|
| VS |
|
|
| D |
|
|
| E |
|
|
Această mașină produce 4.098 1 în 47.176.870 pași. Cele 1 nu sunt consecutive: 8 191 0 sunt intercalate. Descoperită în 1989, nu se știe dacă este castorul plin de viață pentru această clasă de mașini Turing: în 2003, existau 43 de astfel de mașini, a căror posibilă execuție perpetuă nu a fost dovedită.
6 state
Pentru 6 stări, cea mai activă mașină este după cum urmează:
| stat | Simbol | |
|---|---|---|
| 0 | 1 | |
| LA |
|
|
| B |
|
|
| VS |
|
|
| D |
|
|
| E |
|
|
| F |
|
|
Această mașină produce aproximativ 3.515 × 10 18 267 1 în aproximativ 7.412 × 10 36 534 pași. A fost descoperit în iunie 2010.
Generalizare
Este posibil să generalizăm problema la mașinile Turing care conțin n stări și m simboluri, ducând la următoarele funcții generalizate:
- Σ ( n , m ): numărul maxim de simboluri altele decât 0 scrise de o mașină cu n stări și m simboluri;
- S ( n , m ): numărul maxim de pași parcurși de o mașină cu n stări și m simboluri.
Cu 2 stări și 3 simboluri, castorul ocupat este următoarea mașină, care se oprește după 38 de pași, panglica sa cuprinzând 9 simboluri "2" (și 1 "1"):
Cu 3 stări și 3 simboluri, cea mai activă mașină cunoscută se oprește după 119 112 334 170 342 540 pași, panglica ei conținând 374 676 383 copii ale aceluiași simbol. Nu se știe dacă acesta este castorul ocupat pentru această combinație de stări și simboluri.
Valori cunoscute
Valorile lui Σ ( n ) și S ( n ) sunt cunoscute numai pentru n <5. Pentru toate celelalte sunt cunoscute, în cel mai bun caz, doar limite inferioare .
În 1964, Milton Green a construit un set de mașini de strunjit care arată că pentru k ≥ 2:
unde este notația săgeților lui Knuth și A este funcția Ackermann .
Asa de :
(unde ultimul termen este un turn de 3 27 = 7 625 597 484 987 exponenți) și:
unde g 1 este valoarea de pornire uriașă a secvenței care definește numărul Graham .
Următoarele tabele listează valorile exacte și limitele inferioare ale lui S ( n , m ) și Σ ( n , m ) pentru n și m ≤ 6. „? Sunt mai mari decât numărul maxim de intrări din stânga sau de deasupra lor: nu apar în publicațiile de cercetare sau au fost suprascrise de mașini mai mici.
| 2 state | 3 state | 4 state | 5 state | 6 state | |
|---|---|---|---|---|---|
| 2 simboluri | 6 | 21 | 107 | ≥ 47 176 870 | ≥ 7,4 × 10 36,534 |
| 3 simboluri | 38 | ≥ 119 112 334 170 342 540 | ≥ 1,0 × 10 14,072 | ? | ? |
| 4 simboluri | ≥ 3 932 964 | ≥ 5,2 × 10 13.036 | ? | ? | ? |
| 5 simboluri | ≥ 1,9 × 10,704 | ? | ? | ? | ? |
| 6 simboluri | ≥ 2,4 × 10 9 866 | ? | ? | ? | ? |
| 2 state | 3 state | 4 state | 5 state | 6 state | |
|---|---|---|---|---|---|
| 2 simboluri | 4 | 6 | 13 | ≥ 4098 | ≥ 3,5 × 10 18 267 |
| 3 simboluri | 9 | ≥ 374 676 383 | ≥ 1,3 × 10 7,036 | ? | ? |
| 4 simboluri | ≥ 2.050 | ≥ 3,7 × 10 6.518 | ? | ? | ? |
| 5 simboluri | ≥ 1,7 × 10 352 | ? | ? | ? | ? |
| 6 simboluri | ≥ 1,9 × 10 4.933 | ? | ? | ? | ? |
Referințe
- (ro) Tibor Radó , „ Despre funcții necomputabile ” , Bell Systems Technology Journal , vol. 41, nr . 3,Mai 1962, p. 877-884 ( citește online )
- De fapt, un argument mai simplu (la baza dovezii lui Radó) este că, dacă această întrebare ar putea fi decisă, ar fi ușor să rezolve problema opririi .
- După A028444 din OEIS
- Cel de-al 8000-lea număr de Castor Ocupat evită teoria seturilor ZF: lucrare nouă de Adam Yedidia și de mine
- enumeratoare de dovezi metamath și alte lucruri
- (en) Pascal Michel, „ Studiu istoric al castorilor ocupați ” ,Iunie 2012
- (în) Heiner Marxen, „ Castor ocupat în două state (de T.Rado) ” ,6 iulie 2010
- (în) Heiner Marxen, „ 3-state Busy Beaver (majoritatea) (de T.Rado) ” ,6 iulie 2010
- (în) Heiner Marxen, „ 3-state Busy Beaver (majoritatea pașilor) (de T.Rado) ” ,6 iulie 2010
- (în) Heiner Marxen, „ 4-state Busy Beaver (de A.Brady) ” ,6 iulie 2010
- (în) Heiner Marxen, „ 5-state TM # 1 din MaBu-List ” ,6 iulie 2010
- (în) Georgi Georgiev (Skelet), " Mașini neregulate ocupate de castor pentru clasa TM (5) " ,16 mai 2003
- (ro) Heiner Marxen, „ 6 2-state symbol #b (Pavel Kropitz) ” ,6 iulie 2010
- (în) Heiner Marxen, „ 2-state 3-symbol În prezent cel mai bun (de Brady / Michel) ” ,6 iulie 2010
- (în) Heiner Marxen, „ 3-state 3-symbol #b (TJ & S. Ligocki) ” ,6 iulie 2010
- (în) Milton W. Green , „ O limită inferioară este funcția Sigma a lui Rado pentru mașinile binare de Turing ” , 1964 Lucrările celui de-al cincilea simpozion anual privind teoria comutării circuitelor și proiectarea logică ,1964, p. 91-94 ( DOI 10.1109 / SWCT.1964.3 )
- (în) Marxen Heiner, " Busy Beaver " ,7 noiembrie 2011
Vezi și tu
Bibliograf
- Lin, Shen și Radó, Tibor (1965), Computer Studies of Turing Machine Problems , Journal of the Association for Computing Machinery, Vol. 12, nr. 2 (aprilie 1965), p. 196-212 . Aceasta include teza lui Lin, care a arătat că prin demonstrarea faptului că toate mașinile cu trei stări și cele cu două simboluri nu se opresc niciodată dacă nu se opresc după 21 de pași.
- Brady, Allen H. (1983), Determinarea valorii funcției necomputabile Rado Sigma (k) pentru patru stări Mașini Turing, Matematica calculului, vol. 40, n o 162 (aprilie 1983), p. 647-665 . O dovadă de = 13
Articole similare
linkuri externe
- (ro) Busy Beaver ( MathWorld )
- (ro) Castor ocupat - Rezultate cunoscute în prezent (Heiner Marxen)
- (ro) Studiu istoric al castorilor ocupați (Pascal Michel)