Java Programmeringsutfordring: Opprett en enkel Turing Machine - dummies

I matematikeren Alan Turing ble det oppfattet en sviktende enkel type beregningsmaskin kalt en Turing Machine . Turing har faktisk aldri bygget en Turing Machine. I stedet var det en hypotetisk enhet som han concocted til å støtte i undersøkelsen av beregningsbarhet - det vil si om komplekse problemer kan løses ved beregningstrinn og om en maskin kan utvikles som kan løse ethvert beregningsbart problem. (Hvis du er interessert i å vite mer om historien eller anvendelsen av Turing-maskiner, kan du finne mange artikler om dem på Internett. Bruk bare en søkeleverandør til å søke etter "Turing-maskin".)

Operasjonen av en Turing Machine er enkel. Den utgjør bare noen få grunnleggende begreper:

Hjertet i en Turing Machine er et uendelig langt tape som er delt inn i celler på hvilken informasjon som kan skrives.

I praksis kan selvfølgelig ingen fysisk enhet ha et uendelig antall celler. Men i teorien om en Turing Machine er båndet uendelig.
Informasjonen som kan skrives på hver celle, er begrenset til et enkelt symbol, for eksempel en 0 eller en 1. Imidlertid kan informasjon representeres av de kombinerte verdiene til suksessive celler.

For eksempel kan du representere numeriske verdier etter påfølgende forekomster av symbolet 1 etterfulgt av en 0. Således representerer 1110 verdien 3 fordi det er tre 1'er; 111111011110 kan representere verdiene 6 og 4 (seks 1 s etterfulgt av en null, etterfulgt av fire 1s etterfulgt av en annen null).
Turingmaskinen inneholder et lese-skrivehode som alltid er plassert over en (og bare en) av kassens celler.

Dette skrivehodet kan lese symbolet som finnes i cellen. Det kan også slette symbolet og, om ønskelig, skrive et nytt symbol på plass. Cellen over hvilken skrivehodet er plassert, refereres til som nåværende celle eller hovedcelle .
Båndet er motorisert slik at det kan flyttes til venstre eller høyre under les-skrivehodet en celle om gangen.
Maskinen har en tilstand , som er representert ved et symbol som et bokstav i alfabetet.

Som enhver datamaskin kan en Turing Machine programmeres. Et program for en Turing Machine ligner imidlertid ikke på eksternt et Java-program.

I stedet er et Turing Machine-program ganske enkelt et sett med regler som vurderes for å avgjøre hvilke handlinger maskinen skal ta. Hver regel identifiserer en handling som skal tas når den nåværende cellen inneholder et gitt symbol og maskinen er i en gitt tilstand.For eksempel kan en regel diktere hva du skal gjøre hvis den nåværende cellen inneholder en 1 og maskinens tilstand er "a".

Hver regel kan spesifisere noen av tre handlinger:

Slett den nåværende cellen eller skriv en ny verdi til cellen.
Flytt båndet en celle til venstre eller en celle til høyre.
Endre maskinens tilstand til en ny stat.

For eksempel kan en regel angi at hvis den nåværende cellen inneholder en 1 og maskinstatusen er "a", skal turingmaskinen skrive en 0 i gjeldende celle, flytte kassetten en celle til høyre og endre maskinen står til "b. "

I tillegg til et program kan Turing Maskins tape ha en opprinnelig verdi.

Det er det; Det er hele definisjonen av en Turing Machine. Til tross for sin enkelhet kan en Turing Machine beregne alt fra 2 + 2 til banen til en rakett til Mars.

For denne utfordringen må du opprette en veldig enkel Turing Machine. For å forenkle problemet, godta følgende begrensninger på denne versjonen av Turing Machine:

Båndet behøver ikke å være uendelig. Du kan bruke en hvilken som helst Java-funksjon - en matrise, en streng eller en samling - for å representere båndet.

(Merk at selv om båndet ikke må være uendelig, må du enkelt flytte til venstre eller høyre fra den aktuelle cellen. Hvis du velger å bruke en matrise, må du ikke starte med den nåværende cellen ved elementet 0 fordi du ikke kan flytte til venstre derfra.)
En celle kan være tom, eller den kan inneholde noen bokstaver eller tall. En tom celle representeres av et underskriftstegn.
Staten kan være en enkelt alfanumerisk karakter.
Programmet for Turing Machine vil bli lest fra en tekstfil. Denne tekstfilen inneholder en regel per linje. Hver regel inneholder fem tegn, adskilt av mellomrom, som gir detaljene for hver regel, som følger:
- Nåværende celle: Verdien som skal matches for gjeldende celle.
- Nåværende tilstand: Verdien som skal matches for gjeldende maskinstatus.
- Ny celle: Verdien som skal skrives til den nye cellen. _ å slette cellen, * å forlate cellen uendret
- Bevegelse: L eller R for å flytte båndet til venstre eller høyre; H for å stoppe programmet; noen annen karakter for ikke å flytte båndet.
- Ny tilstand: Den nye verdien for maskinens tilstand.
For eksempel sier følgende at når den nåværende cellen er 1 og tilstanden er "a", bør den nåværende cellen settes til 0, båndet flyttet en celle til venstre, og staten skulle settes til " b: "
```
1 a 0 L b
```
- Den første linjen i tekstfilen skal inneholde en streng som representerer de opprinnelige verdiene for båndet.
- Den andre linjen i tekstfilen skal inneholde opprinnelig status.

Følgende figur viser brukergrensesnittet for prøveoppløsningen, men du er fri til å bruke hvilket som helst brukergrensesnitt design du vil ha for dette prosjektet.

Et potensielt Turing Machine-grensesnitt.

Her er noen hensyn til å opprette grensesnittet:

Verdi og nåværende celle: I det minste bør du vise verdien av båndet og markere gjeldende celle.
Verktøy og skjerm: Du bør også gi mulighet til å starte, stoppe eller starte programmet på nytt, og du bør vise resultatene av hvert trinn i programmet.
Programutførelse: Du kan gi brukeren mulighet til å kjøre det lastede programmet fra start til slutt, samt en måte for brukeren å enkelt trede gjennom programmet ved å klikke på en knapp for å utføre hvert trinn av programmet.
Laster programmet : Du bør angi knapper som lar brukeren laste et Turing Machine-program fra en tekstfil, og som lar brukeren tilbakestille maskinen til å kjøre programmet igjen.

Her er et tips for å implementere uendelig tape: Bruk tre strengvariabler for å holde tapeverdiene, en for enkeltkarakteren lagret i gjeldende celle, et sekund for tegnene til venstre for gjeldende celle og en tredje for tegnene til høyre for gjeldende celle. Du kan så enkelt flytte gjeldende celle til venstre eller høyre ved å bruke den riktige kombinasjonen av sammenkoblings- og substringsoperasjoner.

Du finner løsningen på denne utfordringen på nedlastingsfanen i Java All-in-One for Dummies, 4. utgave produktside.

Lykke til!