Maszyna Turinga 2

Przykład 2:

Rozważmy teraz drugi przykład — dodawanie liczb całkowitych w systemie dziesiętnym.

Umówmy sie. że jeżeli maszyna Turinga zatrzyma się dlatego, że doszła do stanu końcowego, to na taśmie wyjściowej pojawi się jakiś napis ujęty w dwa znaki, np. cudzysłów. Jeśli w chwili zatrzymania nie pojawią się na taśmie wyjściowej dwa takie znaki oznaczać to będzie, że maszyna nie osiągnęła stanu końcowego, np. weszła do nieskończonej pętli.

Mamy dwie liczby 736 i 63519 oddzielone znakiem * (separator) zapisane na taśmie roboczej, poza nimi znaki puste #

liczby X i Y ######## 736 - 63519#

Maszyna odnajduje znak * i przesuwając się o jedną klatkę w lewo (przesuwa taśmę w prawo) dochodzi do najbardziej prawej cyfry liczby X, wymazuje ją i zapamiętuje w swoim "stanie". W ty celu musi mieć możliwość osiągania 10 stanów od cyfra 0 do cyfra 9. Następnie przechodzi do skrajnej prawej cyfry liczby Y, wymazuje ją, po czym przechodzi do stanu, w którym pamiętana jest suma obu cyfr oraz ewentualne przeniesienie. Te informacje zależą od cyfry bieżącej i pamiętanej i można je zakodować w stanach od suma o do suma 9 i od suma ^co do suma ^C9- Maszyna przesuwa się teraz na lewo od pozostałej części liczby X i po zapisaniu " jako ogranicznika na lewo od niego zapisuje pierwszą od prawej (czyli ostatnią) cyfrę sumy:

######5 " 73 #*6351 ##

Następnie powtarza kroki z uwzględnieniem przeniesienia i zapisuje sumę na lewo od poprzedniej:

#####55 "7 ##*635 ### '

####255 "###-63####

Jeśli cyfry jednej z liczb skończą się wcześniej, to po dodaniu ewentualnego przeniesienia:

###4255 "###-6#####

resztę przepisuje się po lewej stronie dotychczasowego wyniku:

##64255 "###-######

Na końcu zapisuje się drugi symbol" na lewym skraju wyniku i maszyna staje.

Możemy zatem traktować maszynę Turinga jako komputer z jednym określonym programem.

Sprzęt składa się z głowicy, taśmy, mechanizmu sterującego zmianą stanów, czytaniem, pisaniem, mazaniem i ruchem taśmy. Oprogramowaniem jest lista rozkazów. Komputer jest cały czas ten sam fsprzeti. ale oprogramoyyanie może sie zmieniać!! Maszyna może wykonywać różne algorytmy: obliczania, przeszukiwania czy rozwiązywania procesów decyzyjnych.