Turingmaskin
Wikipedia
En Turingmaskin är en abstrakt mekanism, en teoretisk modell, för att utföra beräkningar, utvecklad av Alan Turing år 1936. Turingmaskinen konstruerades som en enklast möjliga mekanism som var kapabel att utföra icke-triviala beräkningar, och spelar en central roll i teorierna för beräkningsbarhet, beräkningskomplexitet och allmänt inom den matematiska logiken.
En Turingmaskin kan konstrueras för att lösa ett givet problem (en specifik Turingmaskin), men det går också att konstruera en universell Turingmaskin som är kapabel att läsa en kodad beskrivning av en specifik Turingmaskin med dess indata, och sedan utföra denna maskins beräkning.
Church-Turings hypotes säger att varje tänkbar beräkningsprocess kan utföras av en Turingmaskin, d.v.s. det finns ingen principiellt kraftfullare beräkningsmekanism. Denna tes är inte i strikt matematisk mening bevisad, men allmänt accepterad som sann. Argument som talar för tesen är bl.a. att andra försök till teoretiska modeller av beräkningsprocesser, som till exempel Churchs lambdakalkyl, rekursionsteori och Post-maskiner, kan visas vara ekvivalenta med Turingmaskiner. Alla dagens datorer kan också betraktas som Turingmaskiner, d.v.s. de kan simuleras av en sådan.
Teorierna om Turingmaskiner fick stor betydelse för konstruktionerna av de första datorerna till exempel Z3
[redigera] Uppbyggnad
En Turingmaskin består av
- en styrenhet som kan befinna sig i ett ändligt antal tillstånd
- en remsa med ett oändligt antal rutor som kan innehålla en symbol eller vara tom
- ett skriv- och läshuvud som kan röra sig längs remsan och skriva en symbol i eller läsa en symbol från någon av rutorna på remsan
Läs-och skrivhuvudet rör sig längs remsan på order av styrenheten. Maskinen arbetar i diskreta beräkningssteg som styrs av en nästatillståndsfunktion, ett slags program. Denna funktion definierar för varje kombination av tillstånd i styrenheten och symbol i aktuell ruta på remsan, vad nästa beräkningssteg skall vara. Ett beräkningssteg kan vara att flytta sig ett steg åt ena eller andra hållet på remsan och läsa eller skriva en symbol i aktuell ruta. Maskinen startar med ett starttillstånd och en given position på remsan, och avslutar beräkningen när ett sluttillstånd uppnås. Beräkningen kan misslyckas genom att maskinen aldrig uppnår sluttillståndet och fortsätter i all oändlighet.
