A forgalmas hód a számítási elméletben egy olyan Turing-gép, amely maximális "operatív tevékenységet" (például a megtett lépések számát vagy a leállítás előtt leírt szimbólumok számát) ér el az összes bizonyos hosszúságú Turing-gép között. Ezeknek meg kell felelniük bizonyos előírásoknak, és le kell állniuk, miután üres szalagon futtatták őket.
Az elfoglalt hód egyik funkciója számszerűsíti ezt a maximális aktivitást egy n állapotú Turing-gépnél ; az ilyen típusú függvény nem számolható . Valójában egy bizonyos pont után az elfoglalt hód funkciója gyorsabban növekszik, mint bármelyik kiszámítható funkció. N foglalt állapotú Turing-gépek halmazának elfoglalt hódjának meghatározása algoritmikusan oldhatatlan probléma; a gyakorlatban nem is reménykedhetünk abban, hogy 10- nél nagyobb számra n megoldjuk .
A Radó Tibor magyar matematikus által 1962-ben bevezetett koncepció az egyik legkorábbi ismert példa a nem kiszámítható függvényre .
A " elfoglalt hód " kifejezés az " elfoglalt hód " angol kifejezés szó szerinti fordítása , köznyelven szorgalmas és szorgalmas embert jelöl. A kifejezést (és fogalmat) Radó Tibor 1962-ben „ elfoglalt hódjáték ” néven vezette be az 1962- es „ A nem számolható funkciókról ” című cikkében .
A forgalmas n- állapotú hódjáték , amelyet Radó Tibor vezetett be, egy olyan Turing- géposztályt használ, amelynek minden tagja megfelel az alábbi előírásoknak:
és három kimenetet ad vissza:
A gép egy teljesen üres szalag bármely celláján indul (vagyis csak 0-kat tartalmaz); ezután átmeneti függvényének iterációjával folytatja, míg végül eléri a stop állapotot. Ha és csak akkor, ha a gép leáll, a szalagon lévő 1-ek számát gépi pontszámnak nevezzük .
Az elfoglalt hód játéka abból áll, hogy egy adott n számhoz megtalálja a maximális pontszámmal rendelkező Turing-gépet. Ez a forgalmas hód , n állapottal.
Az elfoglalt hód funkciója N : N → N úgy van meghatározva, hogy Σ ( n ) legyen a maximális pontszám az előző bekezdésben megadott specifikációknak megfelelő 2-jelű, n állapotú Turing-gépek között , amikor szalagra indulnak. Szűz.
A Σ egy jól definiált függvény: mindegyik n -hez létezik véges számú Turing-gép, amelynek n állapota van így definiálva, egy izomorfizmusig , és ezért véges számú lehetséges végrehajtási idő.
Egy M Turing-gép pontszámát σ ( M ) -nek jelöljük , bármely olyan Turing-gépet, amelynek 2 szimbóluma és n állapota van, és amelyekre σ ( M ) = Σ ( n ) foglalt hódnak hívják. A N adott, a forgalmas Beaver nem egyedi: van legalább kettő; ha M elfoglalt hód, akkor elegendő a szalag mozgásirányának megváltoztatása a leállítási állapotba való átmenet során egy másik elfoglalt hód megszerzéséhez.
Az ő 1962 cikk, Tibor Radó azt bizonyítja, hogy, ha az f : N → N egy számolható függvény , majd Σ ( n )> f ( n ) bármilyen elegendően nagy n . A Σ tehát nem kiszámítható függvény.
Ez azt jelenti, hogy eldönthetetlen egy általános algoritmust annak eldöntésére, hogy egy tetszőleges Turing-gép egy forgalmas hód: egy ilyen algoritmus nem létezhet fennállása óta lehetővé tenné Σ kell számítani, ami lehetetlen.
Bár a Σ kiszámíthatatlan függvény, meg lehet határozni annak értékét kis n értékekre . Probléma nélkül megmutathatjuk, hogy Σ (0) = 0, Σ (1) = 1 és Σ (2) = 4, és nehezebben, mint Σ (3) = 6 és Σ (4) = 13. Σ ( n ) n > 4 esetén nem ismert , bár alacsonyabb határok vannak kialakítva.
2016-ban Yedidia és Aaronson bebizonyította, hogy egy 7918 államból álló Turing-gép felsorolhatja a levonható bizonyítékok halmazát a ZFC axiomatikájában , megállítva, ha ellentmondást találnak. Kérelmével Gödel második nemteljességi tétel , Σ (7 918) kiszámíthatatlan (kizárólag a axiómái ZFC). A Σ kiszámíthatóságának ezt a felső határát később 1919-re csökkentették egy hasonló gép megépítésével a ZF axiomatikus számára.
Rado Tibor a Σ függvény mellett bevezette az S lépések maximális számának funkcióját . A 2 szimbólumú, n állapotú, fent definiált n- állapotú Turing-gépek E n halmazának M Turing -gépénél s ( M ) az a szalagváltás száma, amelyet M végez leállítás előtt. S ( n ) ekkor az E n maximális eltolódások száma : S : n ↦ max { s ( M ) | M ∈ E n }. Mivel ezek a Turing-gépek minden átmenetnél vagy "lépésnél" eltolják a szalagot (beleértve a stop állapotba való átmenetet is), ez a váltások maximális száma egyben a lépések maximális száma is.
Radó Tibor megmutatta, hogy S nem ugyanazon okból számítható, mint a Σ: gyorsabban növekszik, mint bármelyik kiszámítható függvény. Észreveszi, hogy minden n esetén S ( n ) ≥ Σ ( n ), mivel eltolásra van szükség ahhoz, hogy 1-et írjon a szalagra. Az S ezért legalább olyan gyorsan növekszik, mint a Σ, ami már gyorsabban növekszik, mint bármelyik kiszámítható függvény.
A következő egyenlőtlenségek érvényesek minden n ≥ 1 esetén:
Ha a gép csak egy állapotot ( A ) tartalmaz, akkor az elfoglalt hód megfelel az alábbi átmeneti táblának:
állapot | Szimbólum | |
---|---|---|
0 | 1 | |
NÁL NÉL |
|
Nem használt |
Egy üres szalagról ez a gép először kiolvassa a 0 szimbólumot : ezért írja az 1 szimbólumot , jobbra mozgatja a szalagot és leáll. Így S (1) = 1 és Σ (1) = 1 értéket kapunk.
Az eredmény ugyanaz lenne, ha a szalagot jobbra és balra mozgatnánk. Ha a gép a szalag mozgatása után A állapotban marad , akkor ugyanazt a folyamatot kezdi újra, és soha nem áll le. Mindenesetre az 1. szimbólum átmeneti táblázatának értéke nem releváns, egy ilyen gép soha nem tud landolni egy ezt a szimbólumot tartalmazó cellán.
Kétállapotú gép ( A és B ) esetében a foglalt hód megfelel az alábbi átmeneti táblának:
állapot | Szimbólum | |
---|---|---|
0 | 1 | |
NÁL NÉL |
|
|
B |
|
|
Ez a gép 6 lépés után leáll , a szalagra 4 1 van írva: S (2) = 6 és Σ (2) = 4.
A következő táblázat a részleteket a műveletek, kezdve egy üres kazettát, és egy kezdeti állapotban A :
Nem | Kiinduló állapot |
Olvassa el a szimbólumot |
Írásbeli szimbólum |
Váltás | Következő állapot |
Szalag |
---|---|---|---|---|---|---|
1 | NÁL NÉL | 0 | 1 | Jobb | B | … 0 0 0 1 0 0 0… |
2 | B | 0 | 1 | Bal | NÁL NÉL | … 0 0 0 1 1 0 0… |
3 | NÁL NÉL | 1 | 1 | Bal | B | … 0 0 0 1 1 0 0… |
4 | B | 0 | 1 | Bal | NÁL NÉL | … 0 0 1 1 1 0 0… |
5. | NÁL NÉL | 0 | 1 | Jobb | B | … 0 1 1 1 1 0 0… |
6. | B | 1 | 1 | Jobb | ÁLLJON MEG | … 0 1 1 1 1 0 0… |
A „Szalag” oszlop megadja a szalag állapotát egy művelet után; a most írt karakter vastag betűvel van aláhúzva, amelyen a gép olvasó feje található.
Az utolsó művelet során a menetirány nem számít, a gép úgyis leáll.
Ha megfordítanánk az átmeneti táblázat összes irányát („jobb” helyett „bal” és fordítva), akkor is elfoglalt hódot kapnánk, a gép pontosan úgy viselkedne, mint a fent leírt.
Ezt a nagyon egyszerű gépet már Radó Tibor leírta az 1962-es kezdeti cikkében.
Egy három-állapotú gép ( A , B és C ), a forgalmas Beaver termelő a leginkább 1 megfelel az alábbi átmenet táblázat:
állapot | Szimbólum | |
---|---|---|
0 | 1 | |
NÁL NÉL |
|
|
B |
|
|
VS |
|
|
Ez a gép 14 lépés után leáll és 6 1 van a szalagon.
Ellentétben a két állapot esetével, ez a gép nem áll le a legtöbb lépés után. Van egy másik, az elfoglalt hód, amely a legtöbb lépést produkálja, de kevesebb, mint 1 :
állapot | Szimbólum | |
---|---|---|
0 | 1 | |
NÁL NÉL |
|
|
B |
|
|
VS |
|
|
Ez a gép 21 lépés után leáll, 5 1 a szalagon.
Ezért S (3) = 21 és Σ (3) = 6 értéket kapunk, de két különálló Turing-gép esetében. Ezt az eredményt Radó Tibor írta le már 1962-ben.
Négyállapotú gép esetén az elfoglalt hód a következő átmeneti táblázatnak felel meg:
állapot | Szimbólum | |
---|---|---|
0 | 1 | |
NÁL NÉL |
|
|
B |
|
|
VS |
|
|
D |
|
|
Ez a gép 107 lépés után leáll és 13 1 van a szalagon. Ezek nem egymást követik, a szalag végállapota a következő: ... 0 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 ...
5 államból a forgalmas hódok nem ismertek. 5 állapot esetén a legaktívabb gép a következő:
állapot | Szimbólum | |
---|---|---|
0 | 1 | |
NÁL NÉL |
|
|
B |
|
|
VS |
|
|
D |
|
|
E |
|
|
Ez a gép 4 098 1 -et állít elő 47 176 870 lépésben. Az 1-ek nem egymást követik: 8 191 0 van közbeiktatva. 1989-ben fedezték fel, nem tudni, hogy a turingi gép ezen osztályának nyüzsgő hódja-e: 2003-ban 43 ilyen gép volt, amelyek lehetséges örökös végrehajtása nem bizonyított.
6 állapot esetén a legaktívabb gép a következő:
állapot | Szimbólum | |
---|---|---|
0 | 1 | |
NÁL NÉL |
|
|
B |
|
|
VS |
|
|
D |
|
|
E |
|
|
F |
|
|
Ez a gép körülbelül 3,515 × 10 18 267 1- et állít elő , körülbelül 7,412 × 10 36 534 lépésben. 2010 júniusában fedezték fel.
Lehetséges általánosítani a problémát N állapotot és m szimbólumot tartalmazó Turing-gépekre , amelyek a következő általános funkciókhoz vezetnek:
2 állapot és 3 szimbólum mellett az elfoglalt hód a következő gép, amely 38 lépés után leáll, szalagja 9 "2" (és 1 "1") szimbólumot tartalmaz:
Három állapottal és 3 szimbólummal az ismert legaktívabb gép 119 112 334 170 342 540 lépés után leáll, szalagja 374 676 383 másolatot tartalmaz ugyanabból a szimbólumból. Nem ismert, hogy ez az állapotok és szimbólumok kombinációjának elfoglalt hódja-e.
A Σ ( n ) és az S ( n ) értékei csak n <5 esetén ismertek, az összes többi esetben legjobb esetben csak alacsonyabb határok ismertek .
1964-ben Milton Green épített egy sor esztergagépet, amely azt mutatja, hogy k ≥ 2 esetén:
hol van Knuth nyilainak jelölése és A az Ackermann-függvény .
Így :
(ahol az utolsó kifejezés 3 27 = 7 625 597 484 987 kitevőből álló torony ), és:
ahol g 1 a Graham-számot meghatározó szekvencia hatalmas kezdőértéke .
Az alábbi táblázatok felsorolják az S ( n , m ) és Σ ( n , m ) pontos értékeit és alsó határait n és m ≤ 6 esetén. A „? Nagyobbak, mint a balra vagy fölé kerülő bejegyzések maximuma: a kutatási publikációkban nem fordulnak elő, vagy kisebb gépek felülírják őket.
2 állam | 3 állam | 4 állam | 5 állam | 6 állam | |
---|---|---|---|---|---|
2 szimbólum | 6. | 21 | 107. | ≥ 47 176 870 | ≥ 7,4 × 10 36 534 |
3 szimbólum | 38 | ≥ 119 112 334 170 342 540 | ≥ 1,0 × 10 14 072 | ? | ? |
4 szimbólum | ≥ 3 932 964 | ≥ 5,2 × 10 13 036 | ? | ? | ? |
5 szimbólum | ≥ 1,9 × 10 704 | ? | ? | ? | ? |
6 szimbólum | ≥ 2,4 × 10 9 866 | ? | ? | ? | ? |
2 állam | 3 állam | 4 állam | 5 állam | 6 állam | |
---|---|---|---|---|---|
2 szimbólum | 4 | 6. | 13. | ≥ 4098 | ≥ 3,5 × 10 18 267 |
3 szimbólum | 9. | ≥ 374 676 383 | ≥ 1,3 × 10 7036 | ? | ? |
4 szimbólum | ≥ 2,050 | ≥ 3,7 × 10 6518 | ? | ? | ? |
5 szimbólum | ≥ 1,7 × 10 352 | ? | ? | ? | ? |
6 szimbólum | ≥ 1,9 × 10 4933 | ? | ? | ? | ? |