Czy maszyna Turinga bez możliwości pisania na pustych komórkach jest mniej wydajna niż standardowy Turing?

Czy maszyna Turinga bez możliwości pisania na pustych komórkach jest mniej wydajna niż standardowy Turing?

Myślę, że odpowiedź brzmi tak, ale nie jestem w stanie znaleźć obliczeń, które mogłaby wykonać standardowa maszyna Turinga, ale ta maszyna nie.

Jakieś pomysły?

Innymi słowy: „ Czy komputer z ograniczoną pamięcią byłby mniej wydajny niż komputer z nieograniczoną pamięcią ?”?

Nat

Odpowiedzi:

Typ maszyny Turinga, którą opisujesz, jest automatem z ograniczeniem liniowym (może pisać tylko na częściach taśmy zawierających dane wejściowe). LBA są akceptantami dla języków kontekstowych, więc aby znaleźć konkretny przykład problemu, którego nie można rozwiązać za pomocą tego ograniczenia, ale który można rozwiązać ogólnie za pomocą maszyny Turinga, wystarczy język, który można rozstrzygać, ale nie jest on kontekstowy wrażliwy.

Przykład podany na Wikipedii to:

Przykładem języka rekurencyjnego, który nie jest wrażliwy na kontekst, jest każdy język rekurencyjny, którego decyzja jest trudnym problemem EXPSPACE, powiedzmy, zestaw par równoważnych wyrażeń regularnych z potęgowaniem.

Aby uzyskać więcej przykładów, zobacz Czy istnieje przykład języka rekurencyjnego, który nie jest wrażliwy na kontekst?

rokoko
źródło

Maszyna Turinga, która nie potrafi pisać na pustych polach, jest w przypadku kosmicznej wersji twierdzenia o przyspieszeniu liniowym automatem ograniczonym liniowo. Dlatego żaden problem decyzyjny poza nie może być przez niego rozstrzygnięty. Takie problemy istnieją w twierdzeniu o hierarchii przestrzeni. $\textsf{DSPACE}(O(n))$

szybkie sortowanie
źródło

Czy nie możesz podać na końcu taśmy wystarczająco długiego sufiksu specjalnych symboli, które mogą być użyte jako puste miejsca?

gen

@gen Nie ogólnie. W najbardziej ogólnym przypadku pamiętaj, że znajomość tak długiego sufiksu sprawi, że problem zatrzymania będzie rozstrzygalny. W związku z tym obliczenie wystarczająco długiego prefiksu może być nierozstrzygalne, więc założenie, że taki sufiks jest nieuzasadniony, jest nierozsądne.

chi

Czy należałoby zinterpretować tę odpowiedź jako: „ Maszyny Turinga z ograniczoną pamięcią nie będą miały wystarczającej ilości pamięci, aby uruchomić dowolny dowolny program, ponieważ niektóre programy mogą wymagać więcej pamięci niż mają. ”?

Nat

@Nat: Wyraziłbym to jako „ilość pamięci, której może potrzebować program, jest zasadniczo niepoznawalna do momentu uruchomienia programu”. Co ciekawe (wielki paradoks matematyczny), dla każdej liczby całkowitej triplet X, Y, Z istnieje górna granica liczby komórek taśm wymaganych dla programów, które zakończą się i które zawierają co najwyżej stany X, na taśmach, które mogą pomieścić co najwyżej Y typów symboli i są inicjalizowane za pomocą symboli Z na taśmie, ale żadna taka górna granica nie jest możliwa do udowodnienia, z wyjątkiem trywialnych wartości X, Y i Z.

supercat