Czy każda funkcja która jest obliczalna w czasie t na maszynie Turinga z pojedynczą taśmą, używając alfabetu wielkości k = O ( 1 ), może być obliczona w czasie O ( t ) na single-taśma maszyna Turinga za pomocą alfabetu wielkości 3 (powiedzmy, 0 , 1 , i puste)?
(Z poniższych komentarzy OP). Uwaga: dane wejściowe są zapisywane przy użyciu , ale maszyna Turinga z alfabetem wielkości k może nadpisać symbole wejściowe symbolami z większego alfabetu. Nie widzę, jak zakodować symbole w większym alfabecie w mniejszym alfabecie bez konieczności przesuwania danych wejściowych, co kosztowałoby czas n 2 .
Odpowiedzi:
... nie możesz zbudować go bezpośrednio z TM4, ale TM3 istnieje.
(1) Hennie, obliczenia maszyny Turinga na jednej taśmie, off-line (1965)
(2) Kobayashi, O strukturze niedeterministycznej hierarchii czasowej maszyny Turinga na jednej taśmie (1985)
źródło
źródło