Od programowania do kafelkowania (i z powrotem)

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

Od Maszyny Turinga do kafelków

No nareszcie - zbudowaliśmy opis komputera. Czas spożytkować nasz trud i użyć tego opisu do pokazania czegoś naprawdę ciekawego.

Zobaczymy jak za pomocą kafelków zasymulować Maszynę Turinga. Tak właśnie! Zobaczymy jak można przeprowadzać obliczenia na kafelkach łazienkowych. Jak to możliwe? Idea będzie następująca: Kolejne rzędy kafelków będą oznaczać stan taśmy Maszyny Turinga w kolejnych krokach.

Najpierw popatrzmy na kafelki. Każdy kafelek będzie odpowiadał jednemu polu na taśmie i będzie zawierał dwie informacje:

  • O symbolu, który jest zapisany na tym polu,
  • O tym, czy nad polem jest głowica. Jeżeli tak, to zawiera również informację o tym w jakim ta głowica jest stanie.
Odmiennie potraktujemy tylko pole nad którym znajduje się głowica w stanie końcowym. Takiemu polu będzie odpowiadał kafelek w kolorze młodej śliwki.

Przełóżmy to na język kafelków. Na każdym kafelku jest wzorek. Składa się on z dwóch elementów. Dolna połowa mówi jaki symbol jest zapisany na polu, któremu odpowiada kafelek. Jeżeli nad polem nie ma głowicy, to górne pole jest puste. Jeżeli nad polem jest głowica, to na górnym polu znajduje się numer tego stanu.

alternative text Na obrazkach widać przykładowe kafelki. Ich znaczenie to:
  • Pole, na którym jest zapisany jest symbol $ 1 $. Nad polem jest głowica, która znajduje się w stanie 5.
  • Pole, na którym jest zapisany jest symbol $ e $. Nad polem nie ma głowicy.
  • Pole, na którym jest zapisany jest symbol $ 2 $. Nad polem nie ma głowicy.
  • Pole, na którym jest zapisany jest symbol $ 1 $. Nad polem jest głowica, która znajduje się w stanie 10.

Informacje o tym, co robi (tzn. jak się przemieszcza i co pisze) głowica w kolejnych stanach będziemy kodowali za pomocą dozwolonych kwadratów. Wreszcie początkowy stan maszyny będzie zakodowany jako kompozycja, której zażyczył sobie artysta na górny rząd kafelków.

alternative text Przykład zakodowania reguł pewnej Maszyny Turinga jako dozwolonych kafelków. W kolejnych wierszach widzimy następujące reguły:
  • Jeżeli na polu nie było głowicy i nie przyszła ona z boku, to pole się nie zmieni,
  • Jeżeli będziesz w stanie 10 nad polem, na którym jest zapisane $ e $, to pisz $ 1 $, przejdź w stan 24 idź w lewo
  • Jeżeli będziesz w stanie 1 nad polem, na którym jest zapisane $ s $, to nie nie pisz, przejdź w stan 3 idź w prawo
  • Jeżeli będziesz w stanie 3 nad polem, na którym jest zapisane 1, to pisz $ 0 $, przejdź w stan 2 i idź w prawo
  • Pojawienie się głowicy w prawym kafelku z pary (głowica ruszyła się w lewo).
alternative Przykład trzech kolejnych stanów Maszyny Turinga zakodowanych za pomocą kafelków.
Oto istota całego dowodu -- ścianę da się wykafelkować wtedy i wtedy, gdy Maszyna Turinga się zatrzymuje!

Pozostaje pokazać dwie rzeczy:

  • Jeżeli zakodowana Maszyna Turinga zatrzymuje się, gdy jej wejściem jest liczba $ l $, to według podanych zasad da się wykafelkować ścianę,
  • Jeżeli według podanych zasad da się wykafelkować ścianę, to zakodowana Maszyna Turinga zatrzymuje się, gdy jej wejściem jest liczba $ l $.

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

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com