Od programowania do kafelkowania (i z powrotem)

16.10.2009 - Krzysztof Dryś
TrudnośćTrudnośćTrudność

Po co jest stan końcowy? Odpowiada on zakończeniu obliczeń w normalnym programie. Jeżeli Maszyna Turinga przejdzie w stan $ e $, przestaje obliczać (głowica przestaje się poruszać).

Jak działa Maszyna Turinga?

Praca maszyny Turinga jest podzielona na tury. Na początku każdej tury głowica czyta symbol nad którym się znajduje. Następnie, na podstawie swojego aktualnego stanu i przeczytanego właśnie symbolu podejmuje trzy decyzje:

  • Jaki symbol napisać na swoim aktualnym miejscu?
  • W jaki stan przejść?
  • i w którą stronę pojechać

Maszyna Turinga musi stosować się do paru zakazów. Między innymi nie wolno jej napisać (ani zamazać!) symbolu $ s $. Gdy przeczyta symbol $ s $ nie wolno jej pójść w lewo. Te reguły wynikają ze zdroworozsądkowego przekonania, że niedobrze by było, gdyby głowica wypadła z taśmy.

alternative text

I jeszcze na koniec ostatnie już definicje. Stan taśmy Maszyna Turinga na początku obliczeń nazywamy wejściem. Stan taśmy Maszyna Turinga na koniec obliczeń (po przejściu w stan końcowy) nazywamy wyjściem. Na początku obliczeń głowica znajduje się nad symbolem $ s $.

Skojarzenia z wejściem i wyjściem programu są nieprzypadkowe! Mówimy, że wejściem Maszyny Turinga jest liczba $ w $, jeżeli na początku obliczeń na taśmie znajdują się kolejno: symbol $ s $, binarny zapis liczby $ l $ i nieskończony ciąg symboli $ e $.

4.6
Twoja ocena: Brak Ocena: 4.6 (5 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com