Czy maszyny Turinga zakładają kiedyś coś nieskończonego?

W poprzednim pytaniu Czym dokładnie jest algorytm? , Zapytałem, czy posiadanie „algorytmu”, który zwraca wartość funkcji opartej na tablicy wstępnie obliczonych wartości, jest algorytmem.

Jedną z odpowiedzi, która zwróciła moją uwagę, była ta:

Przykład silni wchodzi w inny model obliczeń, zwany obliczeniami nierównomiernymi. Maszyna Turinga jest przykładem jednolitego modelu obliczeniowego: ma pojedynczy, skończony opis i działa na dane wejściowe o dowolnie dużych rozmiarach. Innymi słowy, istnieje baza TM, która rozwiązuje problem dla wszystkich rozmiarów wejściowych.

Teraz możemy zamiast tego rozważyć obliczenia w następujący sposób: Dla każdego rozmiaru wejściowego istnieje TM (lub inne urządzenie obliczeniowe), które rozwiązuje problem. To jest zupełnie inne pytanie. Zauważ, że pojedyncza baza TM nie może przechowywać silni każdej pojedynczej liczby całkowitej, ponieważ baza TM ma skończony opis. Możemy jednak stworzyć TM (lub program w C), który przechowuje silnie wszystkich liczb poniżej 1000. Następnie możemy stworzyć program, który przechowuje silnie wszystkich liczb od 1000 do 10000. I tak dalej.

Czy rzeczywiście każda TM nie zakłada jakiegoś sposobu radzenia sobie z nieskończonością? To znaczy, nawet TM ze skończonym opisem, który komputeruje silnię dowolnej liczby N za pomocą algorytmu

 int fact(int n) 
 { 
 int r = 1; 
 for(int i=2;i<=n;i++) 
 r = r*i; 
 return r; 
 } 

zawiera założenie, że TM ma „sprzęt” do porównywania liczb o dowolnym rozmiarze za pomocą komparatora „<=”, a także ADDers do zwiększania i do dowolnej liczby, ponadto możliwość reprezentowania liczb o dowolnym rozmiarze.

Czy coś brakuje? Dlaczego podejście, które przedstawiłem w drugim pytaniu, jest mniej wykonalne w odniesieniu do nieskończoności niż to?

Maszyna Turinga nie ma możliwości „porównywania liczb o dowolnym rozmiarze za pomocą <=komparatora”, ponieważ maszyna Turinga nie ma „ <=komparatora”. Maszyna Turinga ma ustalony, skończony zestaw  stanów i stały, skończony alfabet taśmy  . Na każdym etapie obliczeń maszyna Turinga sprawdza swój obecny stan i symbol pod głowicą do odczytu / zapisu i decyduje, co dalej: jaki stan wprowadzić, który symbol zapisać na taśmie i w jaki sposób przenieść taśmę głowa.$Q$$\Sigma$

Z tego powodu maszyna Turinga nie może porównywać dowolnie dużych liczb w jednej <=instrukcji. Korzystając ze stanu, pamięta co najwyżejróżne liczby i używając alfabetu może pisać najwyżejróżne liczby w pojedynczej komórce taśmy (używając każdego możliwego symbolu do przedstawienia jednej liczby). Jako taki, aby porównać dowolnie duże liczby na maszynie Turinga, musisz zapisać każdą liczbę jako ciąg cyfr na taśmie i napisać algorytm, który podejmie wiele kroków w celu porównania tych dwóch liczb. Jak możesz sobie wyobrazić, pisanie programów maszynowych Turinga jest dość kłopotliwe.$|Q|$$|\Sigma|$

Maszyny Turinga tak naprawdę „nie radzą sobie z nieskończonością”: zajmują się nieograniczonymi skończonymi rzeczami, przynajmniej w swojej standardowej definicji. Dane wejściowe są łańcuchem skończonym, a po dowolnej skończonej liczbie kroków urządzenie zbadało lub zapisało tylko skończoną liczbę komórek taśmy. Nie ma ograniczeń co do wielkości danych wejściowych ani liczby kroków obliczeniowych, ale dane wejściowe są skończone, a po dowolnej skończonej liczbie kroków powstaje tylko skończona ilość danych wyjściowych.

Myślę, że ważnym rozróżnieniem jest to, że opis maszyny Turinga jest skończony, podobnie jak dane wejściowe do maszyny, podczas gdy taśma używana jako pamięć jest nieskończona. TM to głównie skończona maszyna, która używa skończonej taśmy. Rozważ taśmę złożoną z komórek, przy czym każda komórka może zawierać jedną wartość. Dane wejściowe do TM są zapisane na taśmie.

Opis TM to skończony zestaw krotek <current state, input, output, move, next state>.

Na każdym kroku można znaleźć dopasowanie do bieżącego stanu i danych wejściowych. Np. Jesteśmy w stanie 0 i czytamy 1, więc znajdujemy krotkę, która się zaczyna<0, 1, ...> a następnie zapisujemy nową wartość w bieżącej komórce, przesuwamy się w lewo lub w prawo (myślę, że klasyczna definicja pozwala również pozostać w tej samej komórce również), a następnie zmienić na nowy stan.

Na przykład, potrzebujesz albo nieskończenie dużego opisu TM (nieskończona liczba <current state, input, output, move, next state> krotek), albo dołączasz informacje wyszukiwania do danych wejściowych do bazy TM. Uważam, że wkład do bazy TM jest określony jako skończony. Prawdopodobnie nie jest to coś, co można zrobić z klasycznie zdefiniowaną maszyną Turinga.

Natomiast przykład Fibonacciego można obliczyć binarnie ze skończoną liczbą krotek, aby opisać TM, i ma skończony wkład.

W skrócie : Turing Machine może wykonywać (skończone) obliczenia nieskończone na (skończonych) nieskończonych danych i generować (skończone) nieskończone wyniki. Podstawową ideą jest to, że te nieskończoności mogą być zdefiniowane jako granica bytów skończonych, zdefiniowana w matematycznie odpowiedni sposób. Jest to podstawa matematycznej semantyki obliczeń. Jeśli weźmiesz pod uwagę programy, a nie Maszyny Turinga, programy te mogą również zawierać (dokładnie określone) nieskończone struktury danych. Przypadek funkcji tabelarycznejfact jako możliwego algorytmu jest ostatecznie analizowany, jako program lub jako model TM, z podpowiedzią dotyczącą związku z leniwą oceną nieskończonych obiektów.

Z wieloma innymi szczegółami

Jeśli chodzi o twoje ostatnie pytanie, baza TM nie oblicza na liczbach dowolnych, ale na symbolicznej reprezentacji tych liczb jako arbitralnych (nieograniczonych) długich łańcuchów symboli je reprezentujących. Prawidłowe kodowanie modulo, prawdą jest, że mogą one porównywać lub wykonywać arytmetykę z takimi liczbami za pomocą tych reprezentacji.

Ale pierwotne pytanie dotyczy roli nieskończoności w maszynach Turinga w ogóle.

Częstą odpowiedzią na to pytanie jest to, że maszyny Turinga nigdy nie mają do czynienia z nieskończonością. Są one skończone i wszystko, co obliczają, jest obliczane w skończonym czasie na skończonej części taśmy (stąd wystarczy skończona taśma, która jest większa). Prawdą jest, że wymagania dotyczące czasu dla TM są nieograniczone, co nie jest tym samym co nieskończoność.

Stąd każda odpowiedź obliczona przez TM może być również obliczona przez automat skończony (FSA), który jest „do pewnego stopnia” jednym ze sposobów patrzenia na tabelę. Trudność polega na tym, że niektóre rozmiary wejściowe (prawie zawsze do tego dochodzi, jeśli tylko odczytać dane wejściowe), przekraczają rozmiar automatu. Ale wtedy możemy po prostu użyć większego. Więc jeśli chcemy rozważyć nieograniczony rozmiar danych wejściowych, potrzebujemy nieskończonej sekwencji FSA, która może wykonać obliczenia. W rzeczywistości możemy potrzebować maszyny o stanie skończonym, nieco bardziej złożonej niż tradycyjne FSA, ponieważ może istnieć wyjście do obliczenia (zamiast odpowiedzi typu „tak-nie”), ale prawdopodobnie powinien to zrobić przetwornik stanu skończonego.

Tak więc, jeśli patrzymy na problem, który ma nieskończony zestaw instancji, taki jak obliczanie GCD lub po prostu stosowanie arytmetyki na liczbach całkowitych o dowolnym rozmiarze, widzimy, że nieskończoność wraca do nas tylnymi drzwiami, ponieważ ta nieskończoność zestaw FSA.

Ale jest inny problem. Powyższa analiza działa tylko wtedy, gdy weźmiemy pod uwagę obliczenia, które kończą się wynikiem. Ale nie wszystkie TM to robią. Niektórzy mogą wymienić członków zbioru nieskończonego. Zazwyczaj ma to miejsce w przypadku TM, która oblicza ułamki dziesiętne$\pi$i dodawaj nowe w nieskończoność. Oczywiście oblicza tylko skończoną odpowiedź w skończonym czasie, ale interesuje nas tak naprawdę nieskończona sekwencja wytworzona przez nieskończone obliczenia. Zauważ, że mamy teraz dwa aspekty nieskończoności: nieskończoność obliczeń i nieskończoność wyniku (tj. Niektórych obliczonych danych). W rzeczywistości może to nawet doprowadzić do rozważenia nieskończonych danych wejściowych ... ale zignorujmy tę komplikację, która dotyczy nieograniczonych strumieni danych. Zauważ też, że takie obliczenia dają wyniki inne niż tak

Z drugiej strony możemy zastąpić to nieskończoną sekwencją skończonych obliczeń skończonymi maszynami. Ale my oszukujemy.

Z fizycznego punktu widzenia jest to najlepsze, co możemy zrobić. Wiemy tylko, jak budować maszyny skończone, przynajmniej zgodnie z obecnym stanem wiedzy w dziedzinie fizyki, który nie powinien zmienić się zbytnio w tej kwestii w najbliższej przyszłości.

Ale w jaki sposób możemy poradzić sobie z tymi nieskończonościami w sposób spójny i możliwy do zrozumienia z matematycznego punktu widzenia.

Jeśli weźmiesz pod uwagę nieskończony zestaw FSA, który może współpracować w celu obliczenia nieskończonego zestawu odpowiedzi, nie możesz tego zrobić arbitralnie. Potrzebujesz pewnych zabezpieczeń, aby upewnić się, że to, co robisz, ma sens. Powszechnie wiadomo, że można w prosty sposób budować dowolny zestaw z nieskończonym połączeniem regularnych zbiorów, w rzeczywistości z nieskończonym połączeniem zestawów singletonów. Zatem rozważenie dowolnych nieskończonych związków automatów bez żadnych ograniczeń nie doprowadzi cię do nikąd. Rozważasz nawet w tym samym zestawie automatów, które dają niespójne odpowiedzi.

To, czego naprawdę chcesz, to zdefiniowanie pojęcia spójności. Ale to wymaga pewnych środków ostrożności. Załóżmy, że używasz nieskończonej sekwencji automatów do symulacji bazy TM, która odpowiada tak lub nie lub nie zatrzymuje się. Problem polega na tym, że FSA zawsze zatrzyma się z odpowiedzią, na przykład tak lub nie. Ale jeśli użyjesz FSA, który w rzeczywistości nie jest wystarczająco duży dla wybranego wejścia, na co powinien odpowiedzieć. Zarówno tak, jak i nie są zarezerwowane dla przypadków, w których FSA faktycznie zakończyło obliczenia TM, a użycie jednej z tych odpowiedzi przy niedokończonym obliczeniu doprowadziłoby tylko do zamieszania. Potrzebujesz odpowiedzi, która brzmi: „ przepraszam, jestem za mała i nie mogę powiedzieć. Spróbuj z większym facetem w rodzinie ”. Innymi słowy, chcesz uzyskać odpowiedź, np. Przepełnienie lub nie wiem. W rzeczywistości semantycy nazywają to „ niezdefiniowanym ” lub „ dolnym ” i często zapisywane „$\bot$„.

Potrzebujesz więc automatów, które mają 3 rodzaje stanów: akceptujący, nieakceptujący i niezdefiniowany. Nieokreślony stan może być postrzegany jako stan oznaczający brakującą część automatu, która wymusza zatrzymanie obliczeń. Tak więc, gdy obliczenia zostają zatrzymane, w zależności od stanu, w którym się zatrzymują, pojawia się odpowiedź tak , nie lub niezdefiniowana .

Teraz widzisz, że to, czego chcesz, to nieskończone sekwencje automatów, które są spójne . Zarówno tak, jak i nie są zgodne z nieokreślonym , ale tak nie jest zgodne z nie . Wtedy dwa automaty są spójne, gdy udzielają spójnych odpowiedzi na tym samym wejściu.

Można to rozszerzyć na automaty obliczające inne rodzaje odpowiedzi. Na przykład, jeśli obliczają kolory, takie jak czerwony, niebieski, zielony ..., możesz dodać niezdefiniowany kolor, który jest zgodny ze wszystkimi innymi. Jeśli odpowiedź jest nieskończoną sekwencją cyfr takich jak$\pi$, wówczas każdą cyfrę można konsekwentnie i niezależnie zastąpić niezdefiniowaną, aby $3.14\bot\bot\bot\bot...$ jest zgodny z $3.1415\bot\bot\bot\bot...$ i z $\bot.\bot5159\bot\bot\bot\bot...$, ale dwa ostatnie nie są zgodne z $3.1416\bot\bot\bot\bot...$. W tym sensie$3.1416\bot\bot\bot\bot...$ nie jest przybliżeniem $\pi$. Mówimy, że odpowiedź jest lepiej zdefiniowana niż inna, gdy zawiera wszystkie informacje, które można znaleźć w drugiej, i być może więcej. W rzeczywistości jest to częściowe zamówienie.

Nie będę dalej rozwijał tych teoretycznych aspektów, co jest nieco niewygodne w przypadku maszyn Turinga. Chodzi o to, że koncepcje te prowadzą do idei, że domeny obliczeniowe (dane lub maszyny) tworzą struktury matematyczne, takie jak sieci, w których obiekt nieskończony można odpowiednio zdefiniować jako granice nieskończenie rosnących (tj. Lepiej i lepiej zdefiniowanych) sekwencji obiekty skończone. Zdefiniowanie nieskończonych sekwencji wymaga nieco więcej aparatu i pojęcia ciągłości. Na tym właśnie polega teoria semantyki Dany Scott i daje ona nieco inny pogląd na pojęcia obliczalności.

Następnie maszyny Turinga lub inne urządzenia formalne, które mogą wykonywać „obliczenia nieskończone”, można zdefiniować jako granice sekwencji skończonych przybliżeń maszyn, które są coraz lepiej definiowane. To samo dotyczy dowolnych danych obliczanych przez maszyny, zarówno wejściowych, jak i wyjściowych.

Najprostszym dokumentem, jaki kiedykolwiek czytałem na ten temat, jest odręczny zestaw notatek z wykładów Dany Scott, często nazywany notatkami z wykładów z Amsterdamu. Ale nie mogłem go znaleźć w sieci. Każdy wskaźnik do kopii (nawet niekompletny, ponieważ mam jej część) byłby mile widziany. Ale możesz spojrzeć na inne wczesne publikacje Scotta, takie jak Zarys matematycznej teorii obliczeń .

Powrót do początkowego przykładu pytania

Te koncepcje aproksymacji dotyczą zarówno danych, jak i programów. Funkcja factjest definiowana rekurencyjnie, co oznacza, że ​​jest to najmniej ustalony punkt funkcji, którego można użyć do obliczenia sekwencji zbieżnej skończonej aproksymacji fact. Ta sekwencja coraz bardziej zdefiniowanych funkcji skończonych zbiega się w nieskończoną całość, którą nazywamy funkcją fact.

Ale jeśli używasz wyszukiwania tablicowego, możesz zrobić dokładnie to samo, z kodem zawierającym coraz większe tabele, które są skończonymi przybliżeniami nieskończonej tabeli wstępnie obliczonych wartości fact. Każda z tych tablic może faktycznie dać odpowiedź na dowolną liczbę całkowitą, ale odpowiedź może być$\bot$( niezdefiniowany ), gdy tabela nie jest wystarczająco zdefiniowana (wystarczająco duża). Algorytm wyszukiwania tabeli również musi być zdefiniowany przez sekwencję aproksymacji, ponieważ oblicza się go z tabelą nieskończoną.

Prawdą jest, że jeśli weźmiemy pod uwagę elementarny model obliczeniowy TM, takiej nieskończonej tablicy nie można wyrazić w tym formalizmie. Nie oznacza to, że nie miałoby to sensu. Maszyna Turinga może mieć drugą taśmę, która ma zostać zainicjowana za pomocą wartości tabelarycznych niektórych funkcji, takich jak fact. Nie zmienia to mocy obliczeniowej bazy TM, o ile funkcja ta jest funkcją obliczalną, o ile tabela może zostać zainicjalizowana nieskończonym obliczeniem innej bazy TM, która może obliczyć wszystkie pary argumentów i wartości dla odpowiedniej funkcji.

Ale w praktyce nie można wykonać nieskończonego obliczenia. Dlatego właściwym sposobem jest leniwe obliczenie tabeli, tj. Wypełnianie wpisów tylko wtedy, gdy jest to potrzebne. Dokładnie to samo dzieje się z zapamiętywaniem, czyli odpowiedzią, którą udzieliłem z różnymi uzasadnieniami na poprzednie pytanie.

Istotą tej odpowiedzi jest to, że Maszyny Turinga mogą naśladować wszystko, co możemy zaprogramować, i wykonujemy obliczenia programowe na obiektach nieskończonych i przy ich użyciu.

Jest to druga odpowiedź skupiająca się bardziej na konkretnym zadanym pytaniu niż na ogólnych ramach teoretycznych, które uzasadniają odpowiedź, i byłaby zdecydowanie potrzebna do udzielenia odpowiedzi na bardziej ogólny tytuł pytania. Jest w pełni zgodny z moimi poprzednimi odpowiedziami na pytania PO, oba Czym dokładnie jest algorytm? i Czy maszyny Turinga zakładają kiedyś coś nieskończonego? , odpowiedzi, w których rozwinąłem bardziej kontekst teoretyczny. Można to uznać za odpowiedź na oba pytania.

Maszyny Turinga mają zdolność radzenia sobie z nieskończonością , podobnie jak wszystkie Turing mogą uzupełniać modele obliczeniowe, choć tylko z nieskończoną liczbą nieskończoności. Naszym problemem jest to, że możemy obserwować tylko część tej nieskończoności, ale musimy rozważyć całość, ponieważ część, którą możemy obserwować, jest nieograniczona.

Innym problemem jest to, że możemy sobie poradzić tylko z konkretnie określonymi podmiotami. W rzeczywistości cała struktura nauki, jaką znamy, spada, jeśli weźmiemy pod uwagę byty, które nie są określone w ostateczny sposób, ponieważ niemożliwe jest sprawdzenie spójności definicji, a nawet wiedzieć, jakie są definicje, ponieważ możemy uzyskać dostęp tylko do części z nich w skończony czas.

Istnieje prawdopodobnie inna fundamentalna kwestia, która jest nieco podobna do faktu, że zamknięcie w ramach nieskończonego związku definiuje dowolny zestaw, który chcesz, chyba że możesz ostatecznie odpowiednio ograniczyć to, co jest dozwolone w takim związku. Ale nie jestem pewien, czy w pełni rozumiem ten problem.

Jak powiedziałem, maszyny Turinga potrafią radzić sobie z nieskończonością . Sprzeciwiam się innym dobrze ocenionym odpowiedziom niektórych użytkowników o wysokich przedstawicielach, którzy powinni wiedzieć, o czym mówią na tak podstawowy temat.

Problem polega na tym, że Turing wybrał bardzo elementarny model obliczeń, aby osiągnąć swój teoretyczny cel. Im prościej, tym lepiej. Chodzi o bardziej zaawansowane / wyrafinowane modele obliczeń, czym właściwie jest język maszynowy w programowaniu: coś bardzo niejasnego, gdzie nie można rozpoznać żadnej z pojęć, które mają sens w programowaniu na wysokim poziomie. Faktem jest, że podobnie jak język maszynowy, TM może naśladować znacznie więcej niż bezpośrednio.

Ponadto nikt tak naprawdę nie wierzy w te ograniczenia maszyny Turinga i opracowano wiele odmian TM o mniej lub bardziej egzotycznych cechach. Jeśli niektóre zestawy nieskończone są nazywane wyliczalnymi rekurencyjnie, dzieje się tak dlatego, że TM może faktycznie wyliczyć (reprezentację) swoich elementów, co wymaga nieskończonego obliczenia (patrz Turing Machines as Enumerators w Hopcroft-Ullman 1979, strona 167 ). Oczywiście zawsze możemy zakodować to jako obliczenia skończone, które odpowiadałyby na pytania takie jak: co to jest$23{rd}$ członek zestawu według ich wyliczenia? Ale nadal byłby często implementowany jako nieskończone obliczenie, które jest sztucznie zatrzymywane, gdy zostanie uzyskana właściwa odpowiedź.

W rzeczywistości wszyscy użytkownicy, którzy twierdzą, że wszystko jest skończone, ale nie ma ograniczeń w TM, bardzo ostrożnie dodają, że uważają maszyny Turinga w swojej standardowej definicji . Problem polega na tym, że standardowa definicja jest tylko narzędziem upraszczającym teorię, ale jest praktycznie nieistotna przy próbie zrozumienia struktur obliczeniowych.

W rzeczywistości jedyną rzeczą, która ma znaczenie w obliczeniach, jest to, że wszystko musi być skończone określone w sposób obliczalny, a nie to, że będzie ono skończone .

Zakładamy, że maszyna Turinga musi być skończonym przedmiotem. Ale to nie jest prawda. Możesz zdefiniować model maszyny Turinga za pomocą drugiej taśmy, która jest tylko do odczytu i zawiera funkcję tabelaryczną dla wszystkich wartości całkowitych, bez żadnych ograniczeń. To jest nieskończone. Ale nie kupuje to żadnej dodatkowej mocy obliczeniowej, o ile zawartość tej taśmy jest określona obliczeniowo (obliczalność oznacza, że ​​jest ona ostatecznie określona). Dodatkowa taśma mogłaby zostać zastąpiona maszyną TM osadzoną w drugiej i zapewniłaby odpowiedzi, zamiast szukać ich na dodatkowej taśmie. Z wyższego poziomu różnica nie jest widoczna.

Z praktycznego punktu widzenia moglibyśmy mieć fact maszynę Turinga obliczającą silnie i tabulujące je na dodatkowej taśmie, podczas gdy inna TM używałaby silni z tabeli na dodatkowej taśmie, tylko czekając na pierwszą TM, ilekroć w tabeli nadal brakuje niektórych wejście. Ale druga maszyna zakłada, że ​​zawartość taśmy jest ostatecznie nieskończona. Maszyna do tworzenia tabel nie musi nawet cały czas działać, ale musi wznowić obliczenia za każdym razem, gdy żądane są dane z tabeli i nie można ich tam znaleźć.

Wracając do pytania, główna różnica między nieograniczonymi liczbami całkowitymi a nieskończoną tabelą polega tylko na tym, że liczby całkowite są skończone, nieograniczone, ale całkowicie obliczone w skończonym czasie. Tabela nieskończoności jest obliczana na czas nieokreślony, skończony, ale wciąż rośnie do nieskończoności. To nie jest problem, ale różnica. Obiekty nieskończone są dostępne tylko poprzez skończone przybliżenia, ale są nieskończone. Obliczalne liczby niewymierne są w tym sensie obiektami nieskończonymi, przynajmniej dla ich reprezentacji jako liczby binarne.

Wszystkie algorytmy są zdefiniowane w kontekście niektórych teorii matematycznych. A przegląd tabeli wraz z tabelą nieskończoną to algorytm. Jest to jednak algorytm w teorii matematycznej posiadający skończony zbiór nieskończonych zbiorów aksjomatów, które szczegółowo określają (a nie intensywnie) wartości funkcji, które aksjatyzuje dla każdego argumentu liczb całkowitych. (patrz moja odpowiedź na poprzednie pytanie ). W takim przypadku zawsze jest to uzasadnione, ponieważ zawsze możesz dodać udowodnione, prawdziwe stwierdzenia do aksjomatów teorii.

Stwierdzenia Usula, powtórzone w twoim obecnym pytaniu, są moim zdaniem niepoprawne (choć wszystko jest również kwestią definicji). Jego wniosek w odpowiedzi , że nie powielałeś się, jest taki, że użycie nieskończonej tabeli nie może być uważane za algorytm, ponieważ może być zaimplementowane tylko przez niejednorodny model obliczeń, przez zbiór różnych maszyn, a zatem takie używa „ nie ma skończonego opisu, który można zaimplementować w celu rozwiązania„ całego ”problemu dla dowolnego rozmiaru wejściowego". To źle. Jego podział na rozłączne maszyny, które mają oddzielne domeny definicji, jest po prostu złym sposobem robienia rzeczy. Właściwym sposobem jest posiadanie nieskończonej sekwencji spójnych maszyn z coraz większymi domenami definicji, które mogą odpowiednio zbiegać się do nieskończonej maszyny, która odpowiada na pytanie. Jest to jeden z zasadniczych celów matematycznej teorii semantyki obliczeń zdefiniowanej przez Dana Scott. Przy pomocy odpowiedniego aparatu matematycznego precyzyjnie definiuje maszyny nieskończone, wartości o nieskończonych reprezentacjach (takich jak e lub$\pi$) lub nieskończone struktury danych, które wszystkie są obliczalne. (patrz moja pierwsza odpowiedź na to pytanie).

Sposób, w jaki takie nieskończone istoty są obliczane w praktyce, polega na leniwej ocenie , obliczaniu tylko części potrzebnej w dowolnym momencie i wznawianiu obliczeń dla reszty, gdy tylko zajdzie taka potrzeba. Dokładnie to zaproponowano powyżej, gdy factmaszyna leniwie oblicza silnię, która ma być przechowywana w tabeli, ilekroć potrzeba więcej danych z tabeli.

W pewien sposób wydaje się to potwierdzać twierdzenie (w odpowiedzi DanielV ), że przestrzeń kodowa musi być skończona, ponieważ leniwa ocena będzie faktycznie oparta na jakimś skończonym kodzie. Jednak obliczalność jest wszechobecną grą kodowania, dlatego między innymi odróżnianie kodu od danych jest zawsze w oczach obserwatora. Rzeczywiście, wiele współczesnych języków programowania nie robi dużej różnicy między intensywną i ekstensywną specyfikacją wartości, a Denotational Semantics tak naprawdę nie odróżnia „2 + 2” od „4”. Semantyka jest naprawdę tym, o czym mówimy, zadając pytanie takie jak „ Co to jest X ? ”.

Ten pogląd na skończoność kodu, również postrzegany jako statyczny, jest kolejnym powodem, dla którego nieskończona tabela (uważana za część kodu) nie jest postrzegana na równi z nieograniczonymi liczbami całkowitymi używanymi jako dane. Ale to kolejna iluzja, która nie przetrwała znanej praktyki programowania w metaprogramowaniu , językach zwrotnych i użyciu tej evalfunkcji. W tych językach kod może być rozszerzony bez ograniczeń przez uruchomiony program, o ile komputer jest uruchomiony. Rzeczywiście można rozważyć Maszyny Turinga, które modyfikują własne reguły przejścia, zwiększając ich liczbę bez ograniczeń. Jest to bardzo zbliżone do sposobu działania maszyn Universal Turing.

Projektując ramy teoretyczne, zawsze istnieje napięcie między prostotą a rzetelnością lub ekspresyjnością. Prostota sprawia, że ​​analiza frameworka jest często prostsza, szczególnie jeśli chodzi o udowodnienie określonych właściwości lub sprowadzenie go do innych frameworków. Ale często niewygodne jest wyrażanie koncepcji wysokiego poziomu, które należy następnie zakodować. Nie programujemy w maszynach Turinga, ale w językach wysokiego poziomu, które są o wiele bardziej wyraziste i wnikliwe, i mogą jednocześnie usuwać niektóre bariery, takie jak rozróżnienie między kodem a danymi, na podstawie równoważności semantycznej. Maszyny Turinga wydają się proste, ale mogą wykraczać daleko poza ich podstawową definicję.

Krótka odpowiedź: nie . Maszyny Turinga w żadnym momencie nie zakładają niczego nieskończonego.

Jest to jeden z powodów, dla których są one poprawne jako model do obliczeń. Opisywanie obliczeń jako czegoś wykonywanego przez nieskończone urządzenie nie ma sensu.

Jednak ich działanie może być nieskończone: może się nie skończyć. To kolejny powód, dla którego są one poprawne jako model do obliczeń. Urządzenia, które mogą wykonywać tylko operacje, które gwarantują zawsze zakończenie, nie mogą wyrażać wszystkich możliwych obliczeń.

Co więcej: operacja wymaga nieograniczonej pamięci: chociaż rzeczywista ilość używanej pamięci jest zawsze skończona, może ona dowolnie wzrosnąć. Nie możesz więc dostarczyć całej pamięci, jakiejkolwiek operacji będzie potrzebować z góry. Urządzenia, które mogą wykonywać tylko operacje, które gwarantują, że nigdy nie wykorzystają więcej niż określonej stałej ilości pamięci, nie mogą wyrazić wszystkich możliwych obliczeń.

„myślenie po wyjęciu z pudełka” i uogólnianie tego pytania, które dociera do sedna abstrakcji maszyn Turinga, i wymyślanie innego kąta, na który jeszcze nie udzielono odpowiedzi: tak, maszyny Turinga mają pewne nieodłączne aspekty „zakładania nieskończoności” tylko ponieważ koncepcja jest nieodłączna od matematyki. TM to abstrakcja fizycznych maszyn. fizyczne koncepcje Czasu i Przestrzeni są celowo wykorzystywane w teorii TM, ale jako abstrakcje, ale także z aspektami ich prawdziwych odpowiedników.

w skrócie, TM może teoretycznie działać wiecznie , czyli problem zatrzymania . taśma jest nieskończona, ale w danym momencie można zapisać tylko jej skończoną liczbę. TM, która działa wiecznie, zasadniczo zakłada, że ​​czas i przestrzeń są nieograniczone, tzn. „nieskończone”. w rzeczywistości istnieje odpowiednia hierarchia czasu i przestrzeni / „kontinuum”, które jest nieskończone.

ale żadna fizyczna realizacja tej abstrakcyjnej koncepcji nie jest możliwa, zakładając, że fizyczny wszechświat jest ograniczony (przestrzeń, czas, materia, z których ostatnia jest nieco analogiczna do „symboli” lub „atramentu” w maszynie Turinga). nieco podobnie / analogicznie, w fizyce czasem wszechświat jest uważany za nieograniczony / nieskończony, ale tylko jako abstrakcja. aby to odwrócić, dlatego też „modelowanie” współczesnego komputera jako maszyny Turinga jest abstrakcją, ponieważ komputer może mieć tylko skończoną pamięć itp.

innym przydatnym porównaniem jest linia liczbowa w matematyce. linia liczbowa jest nieskończona, ale oznacza liczby skończone. każda liczba na linii liczbowej reprezentuje skończoną ilość, ale istnieje nieskończona liczba tych skończonych wielkości. taśma maszyny Turinga ma silne podobieństwo do koncepcji linii liczbowej z matematyki. Turing mógł łatwo zdefiniować ją jako nieskończoną tylko w jednym kierunku, ale zdefiniował ją jako nieskończoną w obu kierunkach, podobnie jak linia liczb matematycznych, z pozycjami ujemnymi „na lewo” na taśmie i pozycjami dodatnimi „na prawo”.