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?
turing-machines
finite-automata
Jesse Berlin
źródło
źródło
Odpowiedzi:
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 mak 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.
źródło