Czy dane wejściowe do maszyny Turinga mogą mieć nieskończoną długość?

Biorąc pod uwagę tylko alfabet , ciągi, które można podać jako dane wejściowe do maszyn Turinga, pochodzą ze zbioru Σ ∗ . Ale czy ma sens, aby dane wejściowe były nieskończonym ciągiem binarnym? Na przykład, jeśli maszyna Turinga akceptuje wszystkie ciągi zaczynające się od 0, to czy ciąg binarny nieskończonych zer również należy do języka akceptowanego przez maszynę Turinga?$\Sigma = \{0,1\}$$\Sigma^{*}$

Nie ma problemu z uruchomieniem maszyny Turinga na taśmie zainicjowanej nieskończonym łańcuchem, chociaż zwykle nie jest to brane pod uwagę. Nadal jednak potrzebujemy, aby maszyna zakończyła się w określonym czasie. Istnieją również pojęcia obliczeń w nieskończoności, które mogą być tutaj odpowiednie.

To jedna z cech maszyn Turinga typu 2 . Są one wykorzystywane między innymi do analizy obliczalności funkcji między liczbami rzeczywistymi. Co ciekawe, są one wykorzystywane do analizy obliczalności operatorów, takich jak integracja.

Fajny fakt: Dokładna integracja numeryczna jest obliczalna.

Aby odpowiedzieć na pytanie „czy to ma sens”, może to być nawet przydatne, jeśli weźmie się pod uwagę maszyny Turinga, które działają w ograniczonym czasie.

W szczególności jest to bardzo przydatny sposób myślenia o maszynach Turinga bez prefiksów . Są to maszyny, których zestaw zatrzymanych danych wejściowych nie zawiera prefiksu; to znaczy brak danych wejściowych powodujących zatrzymanie maszyny jest prefiksem innego. Są one równoważne mocą ze zwykłymi maszynami Turinga, ale tylko wtedy, gdy pozwolimy maszynie Turinga decydować o własnych wejściach zatrzymania: tj. użytkownik nie ma pojęcia, na jakich wejściach maszyna się zatrzyma (i jest to właściwość nierozstrzygalna).

Jednym ze sposobów, aby to zobaczyć, jest zwykła maszyna Turinga z jednokierunkową nieskończoną taśmą wejściową z głowicą taśmy, która nie może się cofnąć. Użytkownik wypełnia taśmę bitami i uruchamia maszynę. Jest to z definicji maszyna Turinga bez prefiksu. Jeśli maszyna zatrzymuje się, musi odczytać tylko skończoną liczbę bitów, a żaden prefiks tej części taśmy nie może być programem, w przeciwnym razie maszyna by się tam zatrzymała.

Jest to dobry sposób na omówienie obliczalnych rozkładów prawdopodobieństwa: użytkownik wypełnia taśmę losowymi bitami (źródłem losowości maszyny), a maszyna wyrzuca losowy ciąg bitów. Zbiór wszystkich takich maszyn Turinga odpowiada zestawowi rozkładów obliczalnych (w szczególności niższych pół-obliczalnych semimeasures).

Zaletą nieskończonego wejścia jest to, że nie musimy określać, co robi maszyna, jeśli damy jej prefiks programu zatrzymującego, tj. maszyna próbuje odczytać poza końcem wprowadzonego przez nas wejścia.

Nawet jeśli nie masz takiej taśmy, możesz zatrudnić inną maszynę Turinga do jej wyprodukowania.

Maszyna Turinga ma dostęp do pustej, ale nieskończonej taśmy danych (lub niektóre źródła mówią: „maszyna ma tylko wbudowaną fabrycznie małą taśmę”). Może więc zainicjować go za pomocą programowalnego wzorca danych, a następnie taśmę można wykorzystać jako dane wejściowe innej maszyny Turinga.

Oczywiście, jeśli twoja treść jest taka, że ​​nie można zdefiniować algorytmu, jak ją wytworzyć, taka treść nie może zostać utworzona przez maszynę Turinga.

W niektórych przypadkach można rozważyć nieskończony wkład i zredukować go do działania „standardowej” maszyny Turinga. Rozważmy na przykład nieskończenie powtarzający się skończony wzór określony na wejściu. Można utworzyć maszynę Turinga, która śledzi, ile tego nieskończonego wzoru zostało zmodyfikowane przez bieżące działania głowicy taśmy przy użyciu skończonej ilości pamięci / pamięci taśmy. Innymi słowy, „równoważnie symuluje” wzór na taśmie o nieskończonym rozmiarze.

Innym przypadkiem, w którym rozważano „nieskończony wkład”, jest analiza równoważności / kompletności automatów Turinga . w złożonym dowodzie Cook wprowadził koncepcję, którą niektórzy określają jako „słabą równoważność Turinga”, przekształcając operacje reguły CA 110 w operacje maszyny Turinga, które rozpoczynają się na początkowej taśmie nieskończonej, ale z (powtarzającymi się) wzorcami o skończonych rozmiarach.

W językach formalnych ciąg znaków jest z definicji skończoną sekwencją symboli. Klasyczna maszyna Turinga ma nieskończoną taśmę ze skończonym łańcuchem wejściowym. W związku z tym, chociaż nie ma ograniczeń co do czasu, jak długo wejście może być, nie może być nieskończone.

To powiedziawszy, istnieje wiele alternatywnych maszyn, które działają podobnie do TM, ale z nieskończonymi sekwencjami wejściowymi.

To, czy sensowne jest wprowadzenie danych o nieskończonej długości, zależy od celu. Ściśle w kontekście Maszyn Turinga nie ma sensu (ponieważ nie jest to możliwe), ale w kontekście Maszyn podobnych do Turinga ma sens i ma wiele zastosowań.