Ocena brak

Co to jest automat skończony i jak jest zbudowany?

Autor /Barnim7777 Dodano /29.12.2011

Automat skończony to zdegenerowana maszyna Turinga. Posiada (tak jak pełna maszyna Turinga) taśmę (pełniącą rolę pamięci) podzieloną na części (pseudo-komórki) i głowicę wędrującą po zadanej taśmie. Różnice polegają na tym, że taśma jest jednostronnie ograniczona, głowica może poruszać się tylko i wyłącznie w prawą stronę i nie ma możliwości zapisu (zapis jest zbędny bo z ograniczenia ruchu w jedną stronę wynika, że i tak maszyna ta nie mogłaby powrócić do miejsca, w którym coś zapisała).

Sterowanie automatem odbywa się w ten sam sposób co pełną maszyną Turinga, czyli za pomocą diagramu przejść międzystanowych zapisanego na taśmie. Diagram ten jest jednak również zdegenerowany do jedynie dwóch elementów:

Automat skończony wykorzystywany jest przede wszystkim w problemach decyzyjnych.

Podobne prace

Do góry