Jaki jest związek między maszynami Turinga ze skończoną taśmą a automatami skończonymi?

Wydaje mi się, że pamiętam z klasy licencjackiej, że dla Maszyny Turinga ze skończoną taśmą zawsze będą istniały odpowiednie Automaty Skończone, ale nie udało mi się znaleźć tego potwierdzonego nigdzie w Internecie. Czy tak jest w rzeczywistości, czy źle pamiętam?

To zależy od tego, co rozumiesz przez „skończoną taśmę”. Jeśli związałeś długość taśmy jakąś funkcją wejścia, to nie - możesz rozpoznać nieregularne języki. Weźmy na przykład LBA .

Ale jeśli masz na myśli ograniczoną taśmę, tam gdzie taśma ma$k$ komórki dla niektórych ustalonych $k$, a następnie tak - rzeczywiście otrzymujesz model równoważny DFA.

Aby to udowodnić, zastanów się, jakie informacje potrzebujesz, aby określić przyszłość serii TM: potrzebujesz zawartości taśmy, lokalizacji głowy i stanu. Jeśli taśma ma stałą liczbę komórek, a alfabet jest stały, to masz stałą liczbę konfiguracji, które możesz zakodować jako stany skończonego automatu.