Turingmaskin

Under julen skrev jag en liten Turingmaskin och ett program till den som implementerar addition av två 7 bitars binära tal på den. Med hjälp av den kod som finns i additionen finns allt som behövs för att också implementera subtraktion, multiplikation och division samt modulo, men det lämnar jag till något annat tillfälle.

Koden finns här för den som är intresserad. Själva Turingmaskinen består av mindre än 100 rader kod och är implementerad i python. Maskinen har ett register som börjar på noll och kan gå till minus oändligheten och till plus oändligheten. Den har också ett läs/skrivhuvud samt en kortläsare som kan läsa in programkod. Korten innehåller sex rader och ger instruktioner för vad maskinen ska göra om den läser en nolla i registret respektive vad den ska göra om den läser en etta. Möjliga handlingar är att skriva en nolla eller en etta. I kortet finns också instruktioner till vilket som är nästa kort beroende på om den läste en etta eller en nolla.
Själva additionen görs ganska enkelt och är implementerad i 88 kort. Algoritmen ser ut som följer:

Först går den till den negativa sidan av registret och fyller i ettor motsvarande det första talet som ska adderas till det andra, sedan går det till den positiva sidan av registret och fyller i den andra talet. Det första talet lagrar alltså sina bitar binärt i registerposition -1 till -8 (det riskerar förstås att bli overflow om alla bitar används på båda sidor) medan det andra talet finns på register position 1 till 8. Därefter rör sig läshuvudet tillbaka till position noll och räknar ned talet på den negativa sidan med ett. Nedräkningen görs genom att om läshuvudet ser en etta så skriver den en nolla och går tillbaka till position noll, om den tvärt om ser en nolla så går den till nästa bit och upprepar samma sak. Om den inte sett någon etta när den kollat hela vägen bort till position -8 så är talet noll och det har då blivit overflow vilket vi kommer utnyttja senare för att avsluta vår algoritm. När den räknat ned talet på den negativa sidan så adderar den ett till talet på den positiva sidan. Det sker på samma sätt som nedräkning, fast tvärt om. Om läshuvudet ser en etta så skriver den en nolla och fortsätter bort i registret, om den ser en nolla så skriver den en etta och går tillbaka till position noll. Sedan fortsätter läshuvudet på detta sätt att räkna ned på ena sidan och räkna upp på den andra tills alla bitar är slut på den negativa sidan och läshuvudet har läst förbi talet där. Då avslutas algoritmen och hela det adderade talet finns i registret på position 1 till 8 på den positiva sidan, så läshuvudet läser helt enkelt ut svaret som stå där.

Det är lätt att först att addera 1 till ett tal lika många gånger som värdet på ett annat tal är det samma som att addera dessa två tal, 2 + 2 är det samma som 1 + 1 + 2. Om man i stället skulle ha dragit ifrån en för varje så skulle man på det sättet ha implementerat subtraktion, 2 -2 är det samma som 2 -1 -1. Genom att ha en andra räknare på den negativa sidan så skulle man kunnat ha implementerat multiplikation, 4 * 4 är det samma som 1 + 1 + 1 + 1 + 1 + 1 + 1 +1 + 1 + 1 + 1 + 1 + 4. Detta skulle också ha möjliggjort division, eftersom division bara skulle innebära att räkna hur många gånger man behöver addera ett tal (nämnaren) till sig själv innan man uppnått den efterfrågade summan (täljaren).

Leave a Comment

E-postadressen publiceras inte. Obligatoriska fält är märkta *

*

Switch to our mobile site

Page optimized by WP Minify WordPress Plugin