Turingmaskin
Fra Wikipedia, den frie encyklopedi
En turingmaskin er en tenkt, formelt beskrevet maskin som utfører ordre etter en helt bestemt oppskrift eller en tabell. Maskinen er en idealisert og formell beskrivelse av en datamaskin, og hvilke beregninger eller oppgaver en datamaskin kan utføre. Maskinen er idealisert i den forstand at den har uendelig stor lagringsplass (hukommelse), og den gjør aldri feil på grunn av sine fysiske mekanismer. Det var Alan Turing som først beskrev en slik maskin i sin avhandling On Computable Numbers i 1936.
En turingmaskin består av et lese/skrive-hode som kan lese/skrive tegn fra/til ruter på en papirstrimmel. Maskinen har mange, men et endelig antall tilstander som beskriver hva som skal gjøres når et bestemt tegn leses. For hvert tegn som leses, gjøres to ting: maskinen skriver eventuelt et nytt tegn til strimmelen, og endrer tilstanden. Maskinen har en start-tilstand og en slutt-tilstand. «Resultatet» av beregningene står til slutt på strimmelen.
Alan Turing brukte en formell beskrivelse av en slik maskin for å bevise setninger innen matematikken. Siden har interessen rundt hans abstrakte maskiner (de ble først senere kalt turingmaskiner) vokst i forbindelse med fremveksten av datamaskiner, og hva datamaskiner egentlig kan utføre av beregninger. Det ser ut til at ingen maskin kan være «kraftigere» enn en turingmaskin i den forstand at den kan utføre andre oppgaver som turingmaskinen ikke klarer.
