Optaget Beaver Turing Maskinen

Original: http://grail.cba.csuohio.edu/~somos/bb.html

Denne historie starter omkring 1960. Tibor Rado, professor ved Ohio State University, tanken om en simpel, ikke-beregnelig funktion udover standard standse problem for Turing-maskiner. Givet et fast endeligt antal symboler og stater, udvælge de Turing-maskine programmer, som i sidste ende standse når systemet drives med et tomt bånd. Blandt disse programmer finder det maksimale antal ikke-tomme symboler tilbage på båndet, når de stopper. Alternativt, find det maksimale antal tidsskridt før standse. Denne funktion er veldefineret, men hurtigt bliver un-beregnelige for endnu et lille antal stater og symboler.
Han offentliggjorde en artikel om det i 1962, men gik videre end blot at skrive om en teoretisk resultat. Med sin elev Shen Lin, de rent faktisk tackles de to symbol, tre statslige problem. Undersøgelsen resulterede i en afhandling til Lin i 1963 og en artikel i JACM i 1965. Efter den første byge af artikler har der været adskillige andre, hvori resultater. Den mest populære er nok den August 1984 Scientific American Computer Recreations kolonne ved Dewdney. Der er en PostScript handout af Jeffrey Shallit om problemet.

Travle Beaver artikler

Om ikke-beregnelige funktioner, Tibor Rado, The Bell System Technical Journal, vol. XLI, nr. 3, maj 1962, s. 877-884.
Dette er den oprindelige artikel, der forklarer problemet. Dette er en teoretisk artikel og giver kun et enkelt eksempel på en tre tilstandsmaskine.
Shen Lin og Tibor Rado. Computer undersøgelser af Turing-maskine problemer. Journal of the ACM, 12 (2): 196-212, april 1965.
Denne artikel faktisk beskriver processen, der fører til løsningen af ​​de tre statslige problemet. Mange detaljer i maskinen indkodning af Turing-maskiner. Har en liste over fyrre maskiner, der krævede menneskelig analyse. Dette er baseret på Shen Lin s afhandling resultater.
Bestemmelsen af ​​værdien af ​​Rado s Noncomputable Funktion Sigma (k) til Fire-statslige Turing-maskiner af Allan H. Brady, Matematik af Computation, vol. 40, nr. 162, apr 1983 s. 647-665.
Denne artikel indeholder en beskrivelse af proces, der fører til en løsning af de fire statslige problemet. Det refererer til hans 1964 afhandling. Har flere eksempler til at illustrere den form for opførsel maskinerne kan udstille.
Komplekset Behavior af Simple Machines ved Rona Machlin og Quentin F. Stout, Physica vol. 42D, 1990, pp. 85-98.
Denne artikel er en uafhængig løsning af de fire statslige problemet. Giver en god beskrivelse af træ-normale metode. Har eksempler på maskiner, herunder nogle fem statslige kandidater ved Juergen Buntrock og Heiner Marxen. Det abstrakte er på nettet. Denne mængde af Physica D viste sig som en bog “Emergent Computation” redigeret af Stephanie Forrest udgivet af MIT Press og er baseret på 1989 Los Alamos konference om Emergent Computation den.
Computer Recreations ved A.K. Dewdney, Scientific American, apr 1985, s. 30.
Denne artikel giver Ühing fem statslige udfordrer og nævner mikroprocessoren hjulpet søgeprocessen. Hans interesse blev udløst ved at læse August 1984 Dewdney artiklen. Den nuværende rekord for seks stater er 95,524,079 varemærker i 8,690,333,381,690,952 skridt fra Heiner Marxen efter et papir i PostScript af Jeffrey Shallit.

Turing Maskinen oplysninger

For en hurtig introduktion til Turing-maskiner kan du besøge Turing World websted på Stanford. Heiner Marxen har en god webside om Optaget Beavers og hans egne kandidater.

Comments are closed.