Hva er en Turing Machine i informatikk?

Turing maskinen ble først beskrevet i 1937 av Alan Mathison Turing, en engelsk matematiker og pioner innen informatikk. En Turing maskin er ikke en maskin i tradisjonell forstand; det er ikke en mekanisk anordning som er ment å være faktisk konstruert. I stedet er det et begrepsmessig eller matematisk maskin.

Alan Turing

Alan Mathison Turing ble født i Paddington, London, i 1912. Han studerte matematikk ved Cambridge University, hvor han senere lært, før han flyttet til Princeton University i 1936. Han kom tilbake til England i 1938 og under andre verdenskrig jobbet for regjeringen koden og Cypher School ved Bletchley Park i Storbritannia, hvor han lede teamet som er ansvarlig for å knekke tyske Enigma-koden. Han jobbet for National Physical Laboratory og Manchester University etter krigen og ble valgt som medlem av Royal Society i 1951. Etter en dom for homofili i 1952, forpliktet Turing selvmord i 1954 på 41.

Abstract datamaskin~~POS=TRUNC

En Turing maskin er i virkeligheten en enkel abstrakt datamaskin. hver av hvilke det kan visualiseres som å ha en uendelig lang, 1-D bånd delt inn i celler, inneholder en 0 eller en 1. Den har også en lese-skrivehode som kan bevege seg frem og tilbake langs båndet for å få tilgang til innholdet hver celle. Tapen kan betraktes som minnet om Turing maskin - men er selvfølgelig uendelig - og lese-skrive-hodet som minnet bussen.

Filosofi

Alan Turing beskrev Turing maskin i et forsøk på å svare på en av de grunnleggende spørsmålene i filosofi informatikk, nemlig hva det betyr for en oppgave å være Computable. Intuitivt, er en oppgave Computable hvis det kan deles opp i et sett med instruksjoner - ellers kjent som en "algoritme" - som kan være utført av en maskin av noe slag for å fullføre oppgaven. Imidlertid kan forskjellige maskiner være i stand til å utføre forskjellige instruksjoner og fullføre forskjellige oppgaver, slik at det finnes et uendelig antall turingmaskin.

Universal Turing Machine

Men Turing forestilt hver algoritme, for hver enkelt oppgave, skrevet ut som et sett med instruksjoner i en standard form. Hvis standardskjema for hver oppgave leveres til en enkelt Turing maskin, kan maskinen bli gjort for å tolke instruksjonene og utføre dem på samme måte som bestemte turingmaskin og er i stand til å fullføre alle mulige oppgaver. Dette er det som kalles en "universell Turing maskin."