Dlaczego używamy maszyn Turinga z pojedynczą taśmą ze względu na złożoność czasu?

Jak wiadomo, istnieje wiele anomolii w maszynach Turinga z pojedynczą taśmą, gdy czas jest $o(n^2)$ : symulacja wielopasmowa TM, symulacja większego alfabetu taśmy za pomocą tylko $\{0,1,b\}$ , konstruowania czasu, nieszczelności twierdzenia o hierarchii czasu, ...

Również wyniki, takie jak $\mathsf{DTime}(o(n\lg n)=\mathsf{Reg}$ , i bardzo specyficzne dla modelu dolne granice czasu dla prostych problemów (które nie przekładają się nawet na dolne granice superlinearne na dwóch taśmach TM) . $O(n^2)$

Dla złożoności przestrzeni używamy modelu, w którym mamy oddzielną taśmę wejściową tylko do odczytu, która jest bardziej naturalna i solidna.

Model TM z wieloma taśmami (lub co najmniej 2 działającymi taśmami) byłby znacznie bardziej wytrzymały i nie doprowadziłby do anomalii takich jak te wymienione powyżej. Kiedyś zapytałem wybitnego teoretyka złożoności, który udowodnił wyniki symulacji we wczesnych latach teorii złożoności, czy zna jakieś ulepszenia jednego z tych starych wyników, a odpowiedź brzmiała, że nie sądzi, że „pytania dotyczące jednego modelu taśmy są takie: ważny".

Jeśli zmienimy standardowy model złożoności czasowej na dwie taśmy TM, rozsądne wyniki w teorii złożoności nie zmienią się i unikniemy tych anomalii spowodowanych przez konkretny model. Więc moje pytanie brzmi:

czy jest jakiś powód, dla którego złożoność czasu jest nadal definiowana w odniesieniu do TM pojedynczych taśm? (inne niż przyczyny historyczne)

cc.complexity-theory turing-machines Kaveh
źródło

Nigdy nie widziałem złożoności czasu zdefiniowanej przez TM pojedynczych taśm.

$\:$ Widziałem tylko solidne klasy złożoności czasowej zdefiniowane przez TM pojedynczych taśm.

$\;\;$

@ Ricky, miałem na myśli, że złożoność czasowa problemu jest zdefiniowana w kategoriach złożoności czasowej pojedynczych taśm TM, które mogą go rozwiązać.

Kaveh

i mam na myśli, że nigdy tego nie widziałem.

$\:$ Zawsze widziałem przynajmniej przypadkowy dostęp.

$\;\;$

ale czy to naprawdę zwykła definicja? w podręcznikach widziałem: 1) zdefiniowanie maszyny Turinga z pojedynczą taśmą (ponieważ jest prostsza); 2) pokaż, jak rozszerzyć na inne warianty, w szczególności na wiele taśm i dostęp losowy; 3) wykazać, że wszystkie z nich mogą się symulować przy maksymalnie spowolnieniu wielomianowym; 4) szybko zapominają o modelu w przeważającej części, przynajmniej dopóki nie będziemy potrzebować bardziej subtelnych rzeczy, takich jak maszyny wyroczni i ograniczenia przestrzeni logicznej; więc, podobnie jak @RickyDemer, kwestionowałbym twierdzenie, że tak naprawdę jest to zwykła definicja.

Sasho Nikolov

Nie mam na to odpowiedzi, ale chcę tylko skierować tę pracę do ciebie autorstwa Yamakami ( springerlink.com/content/u844854721p83870 ). W tym artykule omówiono, co się stanie, gdy dodasz porady do małej maszyny (tj. W czasie liniowym jedna-taśma TM). Udowadnia kilka separacji klas, ale robi to za pomocą tych TM z jedną taśmą. Te rozdzielenia nie działałyby, gdybyś miał inny rodzaj TM. Myślę, że to dobry przykład, w którym możesz udowodnić fajne rzeczy za pomocą jednej taśmy i prawdopodobnie nie można tego zrobić za pomocą innego modelu. Morał brzmi: „jedna kaseta ma znaczenie, gdy masz do czynienia z rzeczami subtelnymi”.

Marcos Villagra,

Odpowiedzi:

Inne odpowiedzi wyglądają bardzo ładnie. Chciałbym podzielić się komentarzem Russella Impagliazza wygłoszonym wiele lat temu w wykładzie, który utknął ze mną do tej pory.

Myślę, że Turing mógł preferować pojedynczą taśmę TM ze względu na fizyczną wiarygodność.

Wskazałem Russellowi na ten wątek kilka dni temu, ale ponieważ nie ma go tutaj, chciałbym poznać jego komentarz i postaram się go zinterpretować.

W przypadku pojedynczej taśmy TM, zakładając taśmę o nieskończonej długości (proszę się ze mną trzymać), możesz zbudować TM, która potrzebuje tylko ograniczonej ilości energii na iterację. Wyobraź sobie taśmę jako długi pręt, a głowa, która zawiera całą logikę TM, po prostu porusza się wzdłuż tego pręta. (Myślę o tym jak o uroczym małym sprzęcie z przekładnią, wykorzystującym bardzo prymitywną technologię. Pręt może mieć wycięcia, które pomogą mu w tym, a zawartość komórki taśmy może być tylko blokiem przesuwanym prostopadle do osi pręta.)

Z drugiej strony, jak to zrobić dla taśmy TM? Jeśli masz $k$ $k$ z powyższych urządzeń muszą przekazać swój status odczytu potencjalnie bardzo odległym innym głowom, które pobierają nieograniczoną ilość energii (powiedzmy, że używasz drutów, które koniecznie wyciekają ciepło), a ponadto nie jest natychmiastowe, co komplikuje mechanizm. Jeśli zamiast tego trzymasz głowy razem i przenosisz taśmy pod nimi, zużyjesz wystarczającą ilość energii, aby przenieść taśmy o nieskończonej długości. W obu przypadkach nie widzę, jak uzyskać energię ograniczoną. Sztuczki, takie jak zmniejszanie przyrostów taśmy (w celu uzyskania skończonej długości), zakładają nieskończenie podzielny wszechświat i naruszają takie rzeczy, jak stała Plancka i zasada holograficzna. Nawet ignorując je, mechanizmy w głowie muszą być arbitralnie precyzyjne, co ponownie powoduje problemy energetyczne i jest niezwykle skomplikowane.

Oczywiście pierwszy schemat ma problemy: konstrukcja nieskończonej taśmy z nieskończenie wieloma wycięciami, nieskończenie wiele słońc do zasilania kolektorów słonecznych na ruchomej głowie, nieskończony zapas środków czyszczących i konserwacyjnych itp. Może jakiś poważny przełom w mechanice kwantowej może niech -tape głowice komunikować się dobrze, ale teraz wyglądają jak skomplikowany jest nasz ustrojstwo. W każdym razie uważam, że komentarz Russella jest bardzo, bardzo interesujący. $k$

matus
źródło

Myślałem, że Turing próbuje wyodrębnić pojęcie „obliczeń”, a nie abstrakcję modelu urządzenia fizycznego. w takim przypadku maszyna Turinga z pojedynczą taśmą doskonale oddaje filozoficzną intuicję, że obliczenia obejmują lokalny dostęp do dużej (nieskończonej) pamięci

Sasho Nikolov

Spodziewałem się teoretycznych powodów (nierealności modeli), ale uważam tę odpowiedź za bardzo interesującą, więc ją akceptuję. Dzięki jeszcze raz.

Kaveh

Utrzymanie głowic taśmy na miejscu wydaje się, że możemy uczynić całkowitą energię logiczną lub, miejmy nadzieję, nie gorszą niż quasilinearną w czasie, projektując formę konstrukcji Hennie-Stearns. Wyobrażam sobie taśmy zwinięte w coraz większe pętle, gdy rozciągają się w obu kierunkach ... Lub bardziej wyobraźni, na szpulach taśm, 100 taśm na szpulę, 100 szpul na stojaku, 100 stojaków na magazyn i dalej na. Oczywiście dla ograniczonej energii na iterację potrzebujemy całkowitej energii liniowej w czasie. Ale quasilinear jest lepszy niż naiwny kwadratowy, więc pomyślałem, że o tym wspomnę.

Dan Brumleve,

$f(n)$

Istnieje wyraźny pedagogiczny powód, dla którego Sipser to robi, a mianowicie kurs płynie w ten sposób, ponieważ:

Powinieneś wprowadzić maszynę z pojedynczą taśmą przed maszyną z wieloma taśmami, w przeciwnym razie pogłębi krzywą uczenia się.
$\cdot$ $\cdot$
Idealnie powinieneś porównać maszynę z wieloma taśmami z maszyną z pojedynczą taśmą w momencie wprowadzenia maszyny z wieloma taśmami, w przeciwnym razie przedłużająca się ignorancja doprowadzi do dodatkowego zamieszania.
Można pominąć wprowadzenie analogicznych klas TIME dla maszyn z wieloma taśmami, co upraszcza ogólną notację.

Nie ma powodu, aby spierać się o czystość pojęciową, kiedy pedagogika tak jasno dyktuje najłatwiejszą drogę, a każdy student informatyki musi przejść ten podstawowy kurs, w tym wszyscy ci, którzy wciąż nie rozumieją dowodów.

Jeff Burdges
źródło

Nie, IIRC, moje pierwsze spotkanie z bazami TM to Hopcroft i pierwsza edycja Ullmana. Ale powód, dla którego zadaję to pytanie, jest właściwie związany z ładnym podręcznikiem Sipsera, uczyłem teorii złożoności opartej na Sipserze i czułem, że byłoby prostsze i czystsze (bez utraty istotnych materiałów) dla mnie i studentów, gdyby było oparte na wielu taśmy TM. Wszystkie te drobne szczegóły techniczne dotyczące ograniczonego dostępu do pojedynczych taśm TM byłyby unikane, a ja mogłem przedstawić bardziej interesujący materiał w ograniczonym czasie, jaki miałem. Sipser nie chce używać tezy Church-Turinga,

Kaveh

więc pomyślałem, że rozluźnienie tej części też może być w porządku. W części twierdzenia o hierarchii czasu wspomina, że dodatkowy współczynnik logarytmiczny nie jest wymagany, jeśli mamy wiele taśm i byłoby dość ciasno. To spowodowało, że zapytałem, czy jest jakiś niehistoryczny powód korzystania z pojedynczych taśm TM dla złożoności czasu. Nie jest to najgorsze niż użycie oddzielnej taśmy tylko do odczytu dla złożoności przestrzeni (i znowu dzieje się tak głównie dlatego, że pojedyncza taśma TM nie uchwyca intuicji na temat klas złożoności małych przestrzeni).

Kaveh

Nie rozumiem, jak można by rozumieć subliniowe granice przestrzeni bez oddzielnej taśmy wejściowej.

$\;$

Tak, zakładam, że SPACJA jest wykonywana inaczej, częściowo dlatego, że będziesz wykonywać podliniowe granice, czego prawdopodobnie nie zrobisz przez CZAS. Argumentowałbym za zapisaniem TIME lub zrobieniem tego, co Sipser robi dla SPACE, jeśli chcesz to zrobić w ten sposób, z pewnością chciałbym porozmawiać o TIME lub TIME_1 lub cokolwiek innego przed urządzeniami obsługującymi wiele taśm.

Jeff Burdges,

Co ciekawe, Sipser mówi jedynie „maszynę Turinga” podczas definiowania PRZESTRZENI (f (n)), ale później zmienia definicję podczas omawiania funkcji podliniowych f, przypisując ćwiczenie równoważności superlinii f. Nauczyłem już tego materiału od Sipsera. Wtedy nie myślałem o tym zbyt wiele, ale teraz jestem z tego powodu zadowolony.

Jeff Burdges

Oryginalną maszynę Turinga opisano za pomocą pojedynczej taśmy:

www.cs.ox.ac.uk/activities/ieg/e-library/sources/tp2-ie.pdf

Tak więc, jak podajesz w swoim pytaniu, dzieje się tak głównie z przyczyn historycznych. Ponadto zawsze istnieje tendencja do zadawania pytań o najprostszy model, który może coś zrobić ...

Ponieważ ten temat jest zwykle nauczany bardzo formalnie, technicznie łatwiej jest opisać pojedynczą maszynę taśmową niż obróbkę dwóch taśm.

Zobacz też:

http://www.cs.utah.edu/~draperg/cartoons/2005/turing.html

Sariel Har-Peled
źródło