Skończone

Czytaj Dalej

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

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ę...

Czy automat skończony może służyć do przedstawiania algorytmów obliczeniowych?

Automat skończony nie może być stosowany do wykonywania obliczeń, bo nie potrafi liczyć. Wynika to z jego ograniczeń konstrukcyjnych – porusza się on tylko w jedną stronę (zatem nie może powracać do miejsc w których już była) i nie posiada funkcji zapisu (bo i tak nie mogłaby powrócić do zapisanych...