Wolframs 2-statliga 3-symbol Turing-maskin
| Turingmaskiner |
|---|
| Maskin |
| Varianter |
| Vetenskap |
I sin bok A New Kind of Science beskrev Stephen Wolfram en universell 2-tillstånd 5-symbol Turing-maskin och förmodade att en speciell 2-tillstånd 3-symbol Turing-maskin ( hädanefter (2,3) Turing-maskin ) kan vara universell som väl.
Den 14 maj 2007 tillkännagav Wolfram ett pris på $25 000 som skulle vinnas av den första personen som bevisade eller motbevisade universaliteten hos (2,3) Turing-maskinen. Den 24 oktober 2007 tillkännagavs att priset hade vunnits av Alex Smith, en student i elektronik och databehandling vid University of Birmingham , för hans bevis på att det var universellt. Eftersom beviset gäller en icke-standard Turing-maskinmodell som tillåter oändliga, icke-periodiska initiala konfigurationer, kategoriseras den av vissa som "svag-universell".
Bakgrund
Claude Shannon ställde först uttryckligen frågan om att hitta den minsta möjliga universella Turing-maskinen 1956. Han visade att två symboler var tillräckliga så länge som tillräckligt många tillstånd användes (eller vice versa), och att det alltid var möjligt att byta tillstånd mot symboler.
Följande tabell anger de åtgärder som ska utföras av Turing-maskinen beroende på om dess nuvarande tillstånd är A eller B , och symbolen som för närvarande läses är 0, 1 eller 2. Tabellposterna anger symbolen som ska skrivas ut, riktningen i vilket tejphuvudet ska flytta, och maskinens efterföljande tillstånd.
A B 0 P1, R, B P2,L, A 1 P2,L, A P2,R, B 2 P1,L, A P0,R, A
(2,3) Turing-maskinen:
- Har inget stoppläge;
- Är trivialt relaterad till 23 andra maskiner genom utbyte av tillstånd, symboler och riktningar.
Minsky (1967) hävdade kort att standardmaskiner (2,2) inte kan vara universella och M. Margenstern (2010) gav ett matematiskt bevis baserat på ett resultat av L. Pavlotskaya 1973 (inte publicerat men nämnt i Margenstern-artikeln); sålunda kan det tyckas att (2,3) Turing-maskinen skulle vara den minsta möjliga universella Turing-maskinen (i termer av antal tillstånd gånger antal symboler). Resultaten är dock inte direkt jämförbara, eftersom Minsky bara tar hänsyn till maskiner som explicit stannar, vilket (2,3)-maskinen inte gör. Mer generellt skiljer sig nästan alla formella definitioner av Turing-maskiner i detaljer irrelevanta för deras kraft, men kanske relevanta för vad som kan uttryckas med ett givet antal tillstånd och symboler; det finns ingen enhetlig formell standarddefinition. (2,3) Turing-maskinen kräver också en oändlig icke-repeterande input, vilket återigen gör en direkt jämförelse med tidigare små universella Turing-maskiner problematisk.
Därför, även om det kan vara sant att (2,3)-maskinen i någon mening är den "minsta möjliga universella Turing-maskinen", har detta inte blivit strikt bevisat i klassisk mening, och påståendet är öppet för debatt när det tas i beaktande traditionella definitioner av universalitet och huruvida avslappningen av Turing-maskinens egenskaper som används för bevisningen kan tillåtas i allmänhet och kan till och med föreslå nya sätt att definiera beräkningsuniversalitet mer oberoende av godtyckliga val (som att ha en stoppkonfiguration eller att kräva ett tomt band) .
Tillståndet för huvudet (upp eller ner droppe (A och B respektive)) och färgmönstret (vitt, gult och orange (0,1 respektive 2)) i en given rad beror enbart på innehållet i raden omedelbart ovanför den.
Även om maskinen har ett huvud med bara två tillstånd och en tejp som bara kan hålla tre färger (beroende på bandets initiala innehåll), kan maskinens utdata fortfarande vara godtyckligt komplex.
Bevis på universalitet
Den 24 oktober 2007 tillkännagavs det av Wolfram Research att Alex Smith, en student i elektronik och databehandling vid University of Birmingham (UK), bevisade att (2,3) Turing-maskinen är universell och därmed vann Wolframs pris som beskrivs ovan.
Beviset visade att maskinen är likvärdig med en variant av ett taggsystem som redan är känt för att vara universellt. Smith konstruerade först en sekvens av regelsystem som visar att (2,3) Turing-maskinen är kapabel till godtyckliga ändliga beräkningar. Han använde sedan ett nytt tillvägagångssätt för att utöka den konstruktionen till obegränsade beräkningar. Beviset fortsätter i två steg. Den första delen emulerar den ändliga utvecklingen av alla tvåfärgade cykliska taggsystem. Emuleringen är en sammansättning av en serie emuleringar som involverar de indexerade regelsystemen "system 0" till "system 5". Varje regelsystem emulerar nästa i sekvensen. Smith visade sedan att även om det initiala tillståndet för (2,3) Turing-maskinen inte är repetitivt, är konstruktionen av det initiala tillståndet inte universellt. Därför är (2,3) Turing-maskinen universell.
Wolfram hävdar att Smiths bevis är ytterligare ett bevis för Wolframs allmänna princip om beräkningsekvivalens ( PCE). Den principen säger att om man ser beteende som inte är uppenbart enkelt, kommer beteendet att motsvara en beräkning som på sätt och vis är "maximalt sofistikerad". Smiths bevis har släppt lös en debatt om de exakta driftsvillkoren som en Turing-maskin måste uppfylla för att den ska vara en kandidat för universell maskin.
En universell (2,3) Turingmaskin har tänkbara tillämpningar. Till exempel kan en maskin som är liten och enkel bäddas in eller konstrueras med ett litet antal partiklar eller molekyler. Men "kompilatorn" Smiths algoritm antyder producerar inte kompakt eller effektiv kod, åtminstone för allt annat än de enklaste fallen. Därför tenderar den resulterande koden att vara astronomiskt stor och mycket ineffektiv. Huruvida det finns mer effektiva kodningar som gör att (2,3) Turing-maskinen kan beräkna snabbare är en öppen fråga.
Tvist
Tillkännagivandet att Alex Smiths bevis hade vunnit gjordes utan godkännande av domarkommittén, vilket noterades av Martin Davis , en medlem av kommittén, i ett inlägg till FOM:s e-postlista:
- "Såvitt jag vet har ingen ledamot i kommittén vidarebefordrat giltigheten av detta 40-sidiga bevis. Beslutet att Smiths bevis är korrekt verkar helt och hållet ha gjorts av Wolfram-organisationen. Min uppfattning är att I/O involverar komplexa kodningar."
Vaughan Pratt ifrågasatte därefter riktigheten av detta bevis i ett inlägg till e-postlistan och noterade att liknande tekniker skulle tillåta en linjärt begränsad automat (eller LBA) att vara universell, vilket skulle motsäga ett känt icke-universalitetsresultat på grund av Noam Chomsky . Alex Smith anslöt sig till e-postlistan efter detta meddelande och svarade följande dag och förklarade att en LBA skulle behöva startas om manuellt för att bli universell med samma initiala konfiguration, medan hans konstruktion startar om Turing-maskinen automatiskt utan yttre ingrepp. Diskussioner om beviset fortsatte under en tid mellan Alex Smith, Vaughan Pratt och andra.
Offentliggörande
Smiths bevis publicerades slutligen i Wolframs tidskrift Complex Systems 2020.
Se även
- Turing fullständighet — förmågan att simulera vilken Turing-maskin som helst
- Regel 110 — en Turing komplett elementär cellulär automat
Bibliografi
- Wolfram, S (2002) En ny typ av vetenskap . Wolfram Media.
- Wolfram Research, Inc., "Pris tillkännagavs för att fastställa gränserna för Turing Machine Computation". Formellt meddelande att Alex Smith har vunnit priset.
- —, Wolfram 2,3 Turing Machine Research Prize. Inbjudan till tävlande.
Historisk läsning
- Marvin Minsky (1967) Beräkning: ändliga och oändliga maskiner . Prentice Hall.
- Turing, A (1937) "On Computable Numbers with an Application to the Entscheidungsproblem ," Proceedings of the London Mathematical Society Series 2, 42 : 230-265.
- — (1938) "On Computable Numbers, with an Application to the Entscheidungsproblem . A Correction," Proceedings of the London Mathematical Society Series 2, 43 : 544-546.
externa länkar
- " Studenten tar mattepriset " Naturen . Publicerad online 24 oktober 2007.
- " College Kid bevisar att Wolframs Turing-maskin är den enklaste universella datorn," Wired Science . Publicerad online 24 oktober 2007.
- " Enklaste 'universella dator' vinner student $25 000, " New Scientist . Publicerad online 24 oktober 2007.
- " Wolfram-priset och Universal Computation: It's Your Problem Now," Dr. Dobb's Journal . Publicerad online 22 oktober 2007.
- Minkel, JR, " A New Kind of Science Authors Pays Brainy Undergrad $25.000 for Identifying Simplest Computer, " Scientific American , 25 oktober 2007.
- Från diskussionstrådar om Foundations of Mathematics: