En Turingmaskin är en teoretisk beräkningsmodell som introducerades av Alan Turing 1936. Den består av ett oändligt långt band uppdelat i celler, ett läs-/skrivhuvud som kan röra sig längs bandet och en kontrollenhet som bestämmer maskinens beteende . Bandet är initialt tomt, och ingången till maskinen tillhandahålls på ett separat inmatningsband. Utdata från beräkningen skrivs på ett utgångsband.
För att beräkna en funktion följer en Turing-maskin en uppsättning instruktioner som kallas ett program. Programmet anger hur maskinen ska bete sig baserat på dess nuvarande tillstånd och den symbol den läser från bandet. Maskinen startar i ett initialt tillstånd och den utför flera gånger följande steg:
1. Läs: Maskinen läser symbolen under läs-/skrivhuvudet.
2. Process: Baserat på det aktuella tillståndet och den avlästa symbolen bestämmer maskinen nästa tillstånd och den symbol som ska skrivas på bandet.
3. Flytta: Maskinen flyttar läs-/skrivhuvudet en cell åt vänster eller höger.
4. Upprepa: Maskinen går tillbaka till steg 1 och fortsätter tills den når ett stoppläge.
Inmatningsbandets roll är att tillhandahålla indata till beräkningen. Inmatningsbandet fylls initialt med ingångssymbolerna, som läses av maskinen under beräkningen. Inmatningsbandet är skrivskyddat, vilket innebär att maskinen inte kan ändra innehållet.
Utdatabandets roll är att lagra utdata från beräkningen. När maskinen bearbetar ingångssymbolerna kan den skriva symboler på utmatningsbandet för att producera önskad utdata. Utmatningsbandet är skrivbart, vilket innebär att maskinen bara kan skriva till det och inte kan läsa dess innehåll.
Turing-maskinens förmåga att beräkna funktioner är baserad på dess förmåga att manipulera symboler på bandet enligt en uppsättning regler. Dessa regler tillåter maskinen att utföra aritmetiska operationer, logiska operationer och andra beräkningar. Genom att följa dessa regler kan en Turing-maskin simulera vilken algoritmisk beräkning som helst.
Tänk till exempel på en Turing-maskin som beräknar summan av två tal. Inmatningsbandet skulle innehålla de två siffrorna, åtskilda av en speciell symbol. Maskinen skulle läsa ingångssymbolerna, utföra additionsoperationen och skriva resultatet på utmatningsbandet.
En Turing-maskin beräknar en funktion genom att följa en uppsättning instruktioner som specificeras av ett program. Inmatningsbandet tillhandahåller insignalen till beräkningen, och utgångsbandet lagrar beräkningens utdata. Maskinen manipulerar symboler på bandet för att utföra beräkningar, vilket gör att den kan simulera alla algoritmiska beräkningar.
Andra senaste frågor och svar ang Beräkningsbara funktioner:
- Vad betyder det att olika varianter av Turing-maskiner är likvärdiga i beräkningskapacitet?
- Förklara förhållandet mellan en beräkningsbar funktion och förekomsten av en Turing-maskin som kan beräkna den.
- Vad är betydelsen av att en Turing-maskin alltid stannar när man beräknar en beräkningsbar funktion?
- Kan en Turing-maskin modifieras för att alltid acceptera en funktion? Förklara varför eller varför inte.
- Vad är en beräkningsbar funktion inom ramen för beräkningskomplexitetsteori och hur definieras den?