Dlaczego pusty symbol nie jest uważany za część alfabetu wejściowego maszyny Turinga?

12

Definicje maszyn Turinga zawsze wyrażają jasno, że pusty symbol nie jest częścią alfabetu wejściowego.

Zastanawiam się, co poszło nie tak, kiedy byłoby uczynić go częścią alfabetu wejściowego, ponieważ skutecznie pusty symbol już wydaje się być częścią wejścia.

Aby wyjaśnić, że „wydaje się” w ostatnim zdaniu, rozważ następujące kwestie.

W ustawieniach domyślnych po prawej stronie wejścia pojawia się nieskończona liczba pustych symboli. Gdy głowica taśmy przesuwa się nad pierwszym pustym symbolem, obliczenia można po prostu kontynuować, ponieważ nie musi to być stan akceptacji ani odrzucenia.

Załóżmy teraz, że obliczenia zapisałyby następnie symbole z alfabetu wejściowego po prawej stronie tego pierwszego pustego symbolu, a następnie powróciły do ​​pozycji skrajnie lewej i jednocześnie powróciły do ​​stanu początkowego. Wtedy zaczynałby się od nowa z inną taśmą. W efekcie zaczyna się teraz od innego wejścia, gdzie po prawej stronie pustego pola znajdują się symbole wejściowe, których wcześniej nie było. Wydaje się, że dane wejściowe skutecznie zawierają pusty symbol. Dalsze zachowanie maszyny może być teraz inne: po ponownym napotkaniu pustego miejsca napotka teraz różne symbole po prawej stronie.

Zakładając, że ten scenariusz jest rzeczywiście możliwy, dlaczego nie wziąłbyś pod uwagę pustego symbolu za część alfabetu wejściowego i dlaczego nie pozwoliłbyś na włączenie go jako części „początkowego” wprowadzania?

Być może jest to tylko sposób na zdefiniowanie danych wejściowych tak, aby nie zawsze były nieskończone?

Zamieszanie
źródło
Gdy byłem w klasie, zaprojektowałem maszyny Turinga, które wykorzystywały dopuszczenie β (lokalnego pustego symbolu) na wejściu jako separatorów pól.
Joshua

Odpowiedzi:

23

Głównym powodem jest to, że pozwala maszynie wykryć koniec danych wejściowych: jest to (znak przed) pierwszym pustym miejscem. Jeśli zezwolisz na spacje na wejściu, urządzenie nigdy nie będzie wiedzieć, czy może znaleźć więcej danych wejściowych, skanując dalej w prawo. Oczywiście możesz to rozwiązać, mając specjalny znak „koniec wejścia”, ale musisz nalegać, aby nie pojawiało się to na wejściu, więc po prostu przesunąłeś problem o jeden poziom głębiej.

Ułatwia także określenie warunków początkowych: wejście jest niepustą sekcją początkowej taśmy, która musi być skończona i ciągła. A jeśli chcesz, aby pusty znak był częścią wpisywanego alfabetu, zawsze możesz dodać dodatkowy znak (nazwać go „spacją” lub czymś innym) i pozwolić maszynie zachowywać się tak, jak chcesz, gdy ją zobaczy.

David Richerby
źródło
2
Ach, oczywiście, bez możliwości ustalenia końca początkowego wkładu, niektóre obliczenia byłyby niemożliwe. Ale poza tym w tym symbolu nie ma nic specjalnego. I myślę, że kwestią ekonomii terminologicznej jest używanie pustego symbolu, ponieważ i tak potrzebujesz go w swoim alfabecie. Myślę, że byłoby to dla mnie bardziej oczywiste, gdy początkowo zdefiniowano je wyraźnym symbolem końca wejścia i uwagą, że nie było to absolutnie konieczne i często pomijane.
Zamieszanie
1
Istnieją proste kodowania wejściowe, które nie wymagają dodatkowego symbolu. Na przykład można symulować czteroznakowy alfabet, biorąc pod uwagę pary znaków 00, 01, 10 i 11, a następnie (na przykład) wyznaczyć dekodowanie . Ale znacznie upraszcza sprawy, pozwalając trzeciej postaci, a to nie powoduje prawdziwych wad. {00}0,{11}1,{10,01}b
Yonatan N,
2
Widząc, że maszyna Turinga potrzebuje reguł, które rządzą tym, co robi, jeśli czyta puste miejsce, i może mieć regułę, która nakazuje jej pisać puste miejsce, czy to nie znaczy, że puste miejsce jest rzeczywiście częścią jego alfabetu? Nie rozumiem, dlaczego dane wejściowe nie mogą zawierać spacji. Co powiesz na kodowanie elementów wejściowych przy użyciu niepustych znaków i pojedynczego spacji jako separatora? Następnie wiele kolejnych pustych miejsc wskazuje koniec danych wejściowych.
Rosie F
3
@YonatanN Pewnie. To „proste”, ale posiadanie pustego symbolu jest prostsze.
David Richerby
3
@RosieF Puste miejsce jest częścią alfabetu taśmy; alfabet wejściowy jest jego podzbiorem. I, oczywiście, możesz skonfigurować konwencje określające, w jaki sposób dane wejściowe mogą zawierać spacje w określonych okolicznościach (tak jak zrobiłeś), ale to tylko komplikuje definicje. Bardziej złożone definicje oznaczają, że trudniej jest dowieść pewnych rzeczy na temat maszyn Turinga. A ponieważ maszyny Turinga są naprawdę używane tylko do sprawdzania rzeczy (jeśli chcesz zaprojektować prawdziwy komputer, to nie będzie TM), to nie jest dobry kompromis.
David Richerby
6

Możesz zdefiniować pusty symbol, który będzie częścią alfabetu. Problem polega na tym, że jeśli maszyna Turinga z wejściem b010010b (gdzie b oznacza puste ) nigdy nie czyta obok drugiego b, to maszyna będzie zachowywać się dokładnie tak samo na wszystkich wejściach zaczynających się od b010010b.

Te maszyny Turinga nazywane są przedrostkami Turinga i są bardzo przydatne do udowodnienia niektórych twierdzeń o złożoności Kołmogorowa.

Peter Shor
źródło
5

Bardzo krótka odpowiedź: alfabet taśmy to zestaw symboli, które mogą pojawić się na taśmie, i zawiera pusty symbol. Alfabet wejściowy jest zbiorem symboli, które mogą pojawić się w pierwszym wejściu , i to nie obejmuje pusty symbol. Głównym alfabetem, na którym troszczy się maszyna, jest alfabet na taśmie: na przykład nadal wymaga reguł, co robić, gdy widzi puste miejsce.

To rozróżnienie jest ważne, jak powiedzieli inni, aby maszyna wiedziała, gdzie kończy się wprowadzanie danych. Jest to ten sam powód, dla którego nie można (pożytecznie) umieścić znaku zero na środku ciągu w C: znak zero jest zarezerwowany, aby oznaczać „ostatni niezerowy znak przed końcem danych, więc kiedy to zobaczysz, skończysz ". Jeśli musisz spodziewać się zerowych znaków na środku ciągu, pisanie strlenstaje się o wiele trudniejsze.

Draconis
źródło