Dlaczego taśma nie wchodzi w zakres definicji maszyny Turinga?

Zastanawiałem się, dlaczego taśma / taśmy nie są częścią formalnej definicji maszyny Turinga. Rozważmy na przykład formalną definicję maszyny Turinga na stronie Wikipedii . Definicja, po Hopcroft i Ullman, obejmuje: skończony zestaw stanów , alfabet taśmy Γ , pusty symbol b ∈ Γ , stan początkowy q 0 ∈ Q , zestaw stanów końcowych F ⊆ Q i przejście funkcja δ : ( Q ∖ F ) × Γ → Q × Γ $Q$ $\Gamma$$b \in \Gamma$$q_0\in Q$$F\subseteq Q$ . Żaden z nich nie jest samą taśmą.$\delta:(Q\backslash F)\times \Gamma\rightarrow Q\times\Gamma\times\{L,R\}$

Maszynę Turinga zawsze uważa się za działającą na taśmie, a funkcję przejścia interpretuje się jako poruszanie głową, zamianę symbolu i zmianę stanu. Dlaczego więc taśma jest pominięta w matematycznej definicji maszyny Turinga?

Z tego, co widzę, formalna definicja sama w sobie nie wydaje się sugerować, że Maszyna Turinga działa tak, jak jest często opisywana nieformalnie (z głową poruszającą się na taśmie). A może to?

Aby formalnie zdefiniować wystąpienie maszyny Turinga (a nie ogólną koncepcję), nie trzeba wyraźnie wymieniać samej taśmy ani jej zawartości. Aby wskazać konfigurację tego konkretnego komputera lub wykonywane przez niego obliczenia , to wtedy potrzebujesz jakiegoś zapisu w celu opisania zawartości taśmy.

Jest to nieco szary obszar, ale powiedziałbym, że definicja dzieli model od instancji . Jeśli chcesz mieć prosty pomysł, pomyśl o sprzęcie vs oprogramowaniu.

Modelu jest sprzętowe: jest jedna głowica. Jest jedna taśma. Taśma jest nieskończona po jednej stronie i zawiera puste miejsca (oprócz danych wejściowych). Głowa może poruszać się o jeden krok na raz.

Instancja jest oprogramowanie: nakazy wejściowe co taśma posiada co na początku, funkcja stanu / przejście opowiada, jak porusza się głowa i jak maszyna „dzieła”. Stany końcowe nadają sens sukcesowi / porażce.

Oba parametry można konfigurować --- oba można zmienić. Istnieją alternatywne modele z dwiema taśmami, dwiema głowicami, taśmami dwustronnymi, niepustą taśmą itp. Ale kiedy naprawisz model, musisz ustalić inne parametry „konfigurowalne”, takie jak liczba możliwych stanów i funkcja przejścia .

$P$$M$$pattern$

Tutaj już dobre odpowiedzi, ale staram się zrobić zwięzłe.

Definicje nie powinny być nadmierne ani pełne.

Rzeczywiście, definicja maszyny Turinga również definiuje abstrakcję taśmy. Q0 - jest początkiem taśmy. Alfabet jest zawartością taśmy. A δ: (Q ∖ F) × Γ → Q × Γ × {L, R} stwierdza, że ​​taśma ma lewą i prawą oraz nieskończoność w obu kierunkach.

Zatem taśma, głowa, przesuwa tylko przyjazne dla człowieka reprezentacje modelu, są już w modelu matematycznym , ale same nie są formalnym modelem.

Les zapewnia zwięzłą i poprawną odpowiedź: definicje matematyczne są tak zwięzłe, jak to możliwe, a wyraźne włączenie nieskończonej taśmy do definicji maszyny Turinga uczyniłoby jej definicję znacznie mniej zwięzłą, więc nie robimy tego.

To nie odpowiada na pytanie: dlaczego ? Jak definicja może wykluczyć nieskończoną taśmę, kiedy jej potrzebujemy?

Odpowiedź: my nie. W pewnym sensie maszyny Turinga tak naprawdę nie wymagają nieskończonych taśm, a ich definicja to wyjaśnia.

Z definicji ruch maszyny Turinga przenosi maszynę z jednej konfiguracji do drugiej; konfiguracja zawiera skończony ciąg, który uważamy za skończony fragment zapisanej taśmy. Każdy ruch albo przesuwa głowicę taśmy o jedną pozycję, albo zastępuje symbol pod głowicą taśmy. Jednak - i jest to niezbędne do jego działania:

• $b$
• możemy to robić nieskończenie często .

$n$$n$

Jednym ze sposobów na sformułowanie tego jest powiedzenie: maszyna działa na nieskończonej taśmie, całkowicie wypełnionej pustkami, z wyjątkiem skończonego fragmentu, na którym znajduje się jej głowa. Tak mówi większość wyjaśnień.

Innym sposobem na sformułowanie tego jest powiedzenie: maszyna działa na skończonej taśmie, przedłużonej pustymi przestrzeniami, gdy głowa zsunie się z taśmy na obu końcach.

Są to oba ważne sposoby konceptualizacji sposobu działania maszyny: w obu przypadkach, jeśli faktycznie posiadasz taką maszynę, poprawnie implementuje maszynę Turinga.

Jeśli wszystko, co Cię interesuje, to uczenie uczniów, jak działają maszyny Turinga, prawdopodobnie nie ma znaczenia, którą koncepcję wybierzesz.

Myślę jednak, że pierwsza konceptualizacja jest błędem z dwóch powodów:

• To jest nierealne . Nie możemy zbudować maszyny z nieskończoną taśmą. My może zbudować maszynę o skończonej taśmy przedłużony na życzenie.
• Jest to sprzeczne z intuicją. Nie uważamy, aby maszyny wykonujące zadania arbitralnie często zawierały nieskończoną ilość zasobów. Na przykład nie uważamy, że kserokopiarka zawiera nieskończoną ilość papieru do kopiowania. Maszyny Turinga modelują działanie komputerów. Modelują, co by się stało, gdybyśmy zastąpili komputer (który w chwili jego wynalezienia była kobietą wykonującą obliczenia na papierze) maszyną zdolną do wykonywania dowolnych programowalnych obliczeń. Nie uważamy, że ta kobieta zawiera nieskończoną ilość papieru. Zakładamy raczej, że otrzyma tyle papieru, ile potrzebuje, i uważamy, że zaniechanie tego jest wadą środowiska, zamiast twierdzić, że taka kobieta nie może istnieć. Dlaczego nie zrobić tego samego dla maszyny?
• Zachęca do mylących wniosków. Dużo to widziałem. Na przykład:
  • Ludzie mówią, że maszyny Turinga nie da się zbudować, podczas gdy maszyny stanów skończonych mogą. Cóż, nie możemy budować dowolnych dużych maszyn o skończonym stanie, tak jak nie możemy dostarczyć dowolnych ilości taśmy do maszyny Turinga.
  • Ludzie mówią, że maszyny Turinga nie modelują poprawnie komputerów, podczas gdy maszyny stanów skończonych tak robią. Służy to do ważnego punktu: jeśli wszystko, co nas interesuje, to używanie maszyny do decydowania o językach wejściowych, to komputer działający tylko na (stałej) pamięci wewnętrznej może w pełni zaimplementować dowolną maszynę skończoną do pewnego rozmiaru, podczas gdy nie może w pełni wdrożyć większości maszyn Turinga, ponieważ zabraknie pamięci wewnętrznej dla wielu z nich. Jest to jednak często uogólnione, mówiąc: komputery są maszynami skończonymi, co wprowadza w błąd:
    • Nie maluje realistycznego obrazu większości programów komputerowych. Rzeczywiście, programowanie przepływu danych faktycznie opiera się na maszynach skończonych, ale tradycyjne programowanie imperatywne nie jest; wykorzystuje programy, które są znacznie bliższe instancjom maszyny Turinga.
    • W praktyce komputery współpracują również z zewnętrznymi źródłami danych wejściowych, wyjściowych i pamięci, które nie mają ustalonego rozmiaru.
    • Maszyny Turinga nie powinny przede wszystkim modelować komputerów; modelują dowolne obliczenia.

Podsumowując: pomysł maszyn Turinga wykorzystujących lub posiadających nieskończoną taśmę służy podkreśleniu ważnego punktu technicznego, ale niekoniecznie jest to najbardziej intuicyjny sposób myślenia o maszynach Turinga i zachęca do pewnych niepoprawnych wniosków. Używaj ostrożnie.