Ocena brak

Co to jest maszyna Turinga, do czego służy i jak jest zbudowana?

Autor /Barnim7777 Dodano /29.12.2011

Maszyna Turinga to uniwersalny model obliczeniowy, przeznaczony do efektywnego wykonywania dających się efektywnie wykonać algorytmów.

Maszyna Turinga składa się z:

- skończonego alfabetu symboli

- skończonego zbioru stanów

- nieskończonej taśmy podzielonej na komórki

(każda komórka może zawierać jeden symbol)

- ruchomej głowicy czytająco – zapisującej

(głowica porusza się krokowo co jedną komórkę)

- diagramu przejść między stanami

(czasem zwanego po prostu diagramem przejść)

W zależności od rodzaju maszyny Turinga może się ona być:

- z taśmą jednostronną ograniczoną

- z wieloma taśmami i wieloma głowicami

- z taśma dwuwymiarową

- z głowicą bez funkcji zapisu

Podobne prace

Do góry