Od programowania do kafelkowania (i z powrotem)

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

Komputer na moim biurku i jego model

Potrzeba nam ścisłego opisu komputerów. Jak go stworzyć? Można powiedzieć: komputer, to to co stoi na moim biurku. To zdanie dokładnie definiuje komputer. Ale ma jedną wadę. Jaką? Maszyna, która stoi obok mnie, jest bardzo skomplikowana. Ma w sobie tysiące obwodów i układów. Dlatego bardzo trudno czegoś o niej dowieść.

Zbuduj sobie model

Jak działa zwyczajny komputer? Możemy wyobrażać sobie, że komputer składa się programu, procesora i pamięci. Pamięć jest podzielona na komórki - w każdej z nich zapisana jest jakaś liczba. W kolejnych turach procesor wykonuje rozkazy zapisane w programie. Od czasu do czasu pisze do pamięci i z niej czyta.

Ten opis zaczyna się robić coraz prostszy, prawda? Jednak chcemy opisać komputer jeszcze ściślej i jeszcze prościej.

Jak to nieskończona?! Przecież nasze komputery są skończone! My jednak czynimy takie założenie dlatego, że w praktyce komputer ma tak dużo dostępnej pamięci (np. na twardym dysku), że lepiej myśleć, że jest jej nieskończenie wiele.

Maszyna Turinga jest wzorowana na starszych komputerach. Dlatego zamiast procesora będziemy mieli głowicę. A zamiast pamięci - taśmę.

Taśma Maszyny Turinga jest nieskończona (uwaga, to ważne!) i podzielona na komórki. W każdej komórce znajduje się jeden z symboli: $ 0 $, $ 1 $, $ e $ lub $ s $. Symbol $ s $ występuje na taśmie dokładnie raz - na pierwszym jej polu. Symbol $ e $ oznacza pustą komórkę - taką w której jeszcze nic nie zostało zapisane.

Głowica Maszyny Turinga służy do pisania na taśmę i czytania z niej. Głowica ma różne stany. Każdy stan ma swoją nazwę. Zbiór wszystkich stanów głowicy nazywamy $ X $. Każda maszyna ma jeden stan końcowy $ e $.

alternative text Przykładowa Maszyna Turinga. Na taśmie zakodowana jest liczba 45 (binarny zapis liczby 45 i same znaki $ e $). Na początku taśmy jest jedyny znak $ s $. Głowica znajduje się nad siódmą komórką i jest w stanie 5.

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

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com