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 × Γ × . Żaden z nich nie jest samą taśmą.
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?
źródło
Odpowiedzi:
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.
źródło
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 .
źródło
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.
źródło
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:
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:
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.
źródło