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

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?

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.

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.

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.