Java Programmeringsutmaning: Skapa en enkel Turing Machine - dummies

Matematikern Alan Turing tänkte på en bedrägligt enkel typ av beräkningsmaskin kallad en Turing Machine . Turing har aldrig byggt upp en Turing Machine. I stället var det en hypotetisk enhet som han concocted för att stödja i undersökningen av beräkningsförmåga - det vill säga om komplexa problem kan lösas av beräkningssteg och om en maskin kan utformas som kan lösa alla beräkningsbara problem. (Om du är intresserad av att veta mer om historia eller tillämpning av Turing-maskiner kan du hitta många artiklar om dem på Internet. Använd bara en sökleverantör för att söka efter "Turing-maskin".)

Funktionen hos en Turing Machine är enkel. Det förkroppsligar bara några grundläggande begrepp:

Hjärtat i en Turing Machine är ett oändligt långt band som är uppdelat i celler på vilken information som kan skrivas.

I själva verket kan ingen fysisk enhet naturligtvis ha ett oändligt antal celler. Men i teorin om en Turing Machine är tejpen oändlig.
Informationen som kan skrivas på varje cell är begränsad till en enda symbol, t.ex. en 0 eller en 1. Emellertid kan information representeras av de kombinerade värdena på successiva celler.

Du kan till exempel representera numeriska värden genom successiva förekomster av symbolen 1 följt av en 0. Således representerar 1110 värdet 3 eftersom det finns tre 1: 111111011110 kan representera värdena 6 och 4 (sex 1 s följt av en noll följt av fyra 1 följt av en annan noll).
Turingmaskinen innehåller ett läs-skrivhuvud som alltid är placerat över en (och endast en) av bandens celler.

Detta lässkrivhuvud kan läsa symbolen som finns i cellen. Det kan också radera symbolen och, om så önskas, skriva en ny symbol i sin plats. Den cell över vilken läs- och skrivhuvuden är placerad kallas den aktuella cellen eller huvudcellen .
Tejpen är motoriserad så att den kan flyttas åt vänster eller höger under lässkrivhuvudet en cell åt gången.
Maskinen har en -stat , som representeras av en symbol som ett bokstav i alfabetet.

Som en dator kan en Turing Machine programmeras. Ett program för en Turing Machine liknar emellertid inte på något sätt ett Java-program.

Istället är ett Turing Machine-program helt enkelt en uppsättning regler som utvärderas för att bestämma vilka åtgärder maskinen ska ta. Varje regel identifierar en åtgärd som ska vidtas när den aktuella cellen innehåller en given symbol och maskinen är i ett givet tillstånd.Till exempel kan en regel diktera vad man ska göra om den aktuella cellen innehåller en 1 och maskinens tillstånd är "a".

Varje regel kan ange någon av tre åtgärder:

Radera den aktuella cellen eller skriv ett nytt värde till cellen.
Flytta tejpen en cell till vänster eller en cell till höger.
Ändra maskinens tillstånd till ett nytt tillstånd.

Exempelvis kan en regel ange att om den aktuella cellen innehåller en 1 och maskinstatusen är "a", ska Turing Machine skriva en 0 i den aktuella cellen, flytta tejpen en cell till höger och ändra Maskinen anger att "b. "

Förutom ett program kan Turing Machine-tejpen ha ett initialt värde.

Det är det; Det är hela definitionen av en Turing Machine. Trots sin enkelhet kan en Turing Machine beräkna allt från 2 + 2 till banan i en raket till Mars.

För denna utmaning måste du skapa en mycket enkel Turing Machine. För att förenkla problemet, acceptera följande begränsningar i denna version av Turing Machine:

Tejpen behöver inte vara oändlig. Du kan använda vilken Java-funktion som helst - en array, en sträng eller en samling - för att representera bandet.

(Observera att även om tejpen inte behöver vara oändlig måste du enkelt kunna flytta till vänster eller höger från den aktuella cellen. Om du väljer att använda en array, börja inte med den aktuella cellen vid elementet 0 eftersom du inte kommer att kunna flytta vänster därifrån.)
En cell kan vara tom eller den kan innehålla alla bokstäver eller siffror. En tom cell representeras av en underskriftstecken.
Staten kan vara en enda alfanumerisk karaktär.
Programmet för Turing Machine kommer att läsas från en textfil. Denna textfil innehåller en regel per rad. Varje regel innehåller fem tecken, åtskilda av mellanslag, som anger detaljerna för varje regel, enligt följande:
- Aktuell cell: Värdet som ska matchas för den aktuella cellen.
- Aktuellt tillstånd: Värdet som ska matchas för aktuellt maskinläge.
- Ny cell: Värdet att skriva till den nya cellen. _ radera cellen, * för att lämna cellen oförändrad
- Rörelse: L eller R för att flytta bandet åt vänster eller höger; H för att stoppa programmet någon annan karaktär för att inte flytta bandet.
- Nytt tillstånd: Det nya värdet för maskinens tillstånd.
Följande exempel säger att när den nuvarande cellen är 1 och staten är "a", bör den aktuella cellen sättas till 0, tejpen flyttas en cell till vänster och staten ska ställas in på " b: "
```
1 a 0 L b
```
- Den första raden i textfilen ska innehålla en sträng som representerar de ursprungliga värdena för tejpen.
- Den andra raden i textfilen ska innehålla den ursprungliga statusen.

Följande bild visar användargränssnittet för provlösningen, men du är fri att använda vilken användargränssnittdesign du vill ha för projektet.

Ett potentiellt Turing Machine-gränssnitt.

Här följer några överväganden för att skapa gränssnittet:

Värde och aktuell cell: Du borde visa värdet på tejpen och markera den aktuella cellen.
Verktyg och display: Du bör också kunna starta, stoppa eller starta om programmets exekvering, och du ska visa resultaten av varje steg i programmet.
Programkörning: Du kan ge användaren möjlighet att köra det laddade programmet från början till slut, samt ett sätt för användaren att enkelt steg genom programmet genom att klicka på en knapp för att utföra varje steg av programmet.
Laddar programmet : Du bör tillhandahålla knappar som låter användaren ladda ett Turing Machine-program från en textfil och som låter användaren återställa maskinen för att köra programmet igen.

Här är ett tips för att implementera det oändliga tejpen: Använd tre strängvariabler för att hålla tejpvärdena, en för den enstaka tecknen som är lagrad i den aktuella cellen, en sekund för tecknen till vänster om den aktuella cellen och en tredje för tecknen till höger om den aktuella cellen. Du kan sedan enkelt flytta den aktuella cellen till vänster eller höger genom att använda den rätta kombinationen av konkatenering och substring.

Du kan hitta lösningen på den här utmaningen på fliken Downloads i Java All-in-One for Dummies, 4: e utgåva produktsida.

Lycka till!