Czy maszyna Turinga „z definicji” jest najmocniejszą maszyną?

Zgadzam się, że maszyna Turinga może „rozwiązać wszystkie możliwe problemy matematyczne”. Jest tak, ponieważ jest to tylko reprezentacja algorytmu na maszynie: najpierw zrób to, a następnie zrób to, a na końcu wyślij to.

Chodzi mi o to, że wszystko, co można rozwiązać, może być reprezentowane przez algorytm (ponieważ jest to dokładnie definicja „rozwiązania”. To tylko tautologia. Nie powiedziałem tu nic nowego.

A tworzenie maszynowej reprezentacji algorytmu, który rozwiąże wszystkie możliwe problemy, nie jest niczym nowym. To także zwykła tautologia. Zasadniczo, kiedy mówi się, że maszyna Turinga jest najpotężniejszą maszyną, oznacza to, że najpotężniejsza maszyna jest najpotężniejszą maszyną!

Definicja „najpotężniejszego”: tego, który może zaakceptować dowolny język.
Definicja „Algorytmu”: proces robienia czegokolwiek. Komputerowa reprezentacja „algorytmu”: maszyna, która może zrobić wszystko.

Dlatego logiczne jest, że reprezentacja algorytmu przez maszynę będzie najpotężniejszą maszyną. Co nowego dało nam Alan Turing?

Zgadzam się, że maszyna Turinga może „rozwiązać wszystkie możliwe problemy matematyczne”.

Nie powinieneś, bo to nieprawda. Na przykład maszyny Turinga nie mogą ustalić, czy wielomiany ze współczynnikami całkowitymi mają rozwiązania liczb całkowitych ( dziesiąty problem Hilberta ).

Czy maszyna Turinga „z definicji” jest najmocniejszą maszyną?

Nie. Możemy wymyślić nieskończoną hierarchię potężniejszych maszyn . Jednak maszyna Turinga jest najpotężniejszą maszyną, którą wiemy, przynajmniej w zasadzie, jak budować. Nie jest to jednak definicja: jutro nie mamy pojęcia, jak zbudować coś mocniejszego, a nawet jeśli jest to możliwe.

Co nowego dało nam Alan Turing?

Formalna definicja algorytmu. Bez takiej definicji (np. Maszyny Turinga) mamy tylko nieformalne definicje algorytmu, zgodnie z „Dokładnie określoną procedurą rozwiązywania problemu”. Ok świetnie. Ale jakie poszczególne kroki mogą podjąć te procedury?

Czy są podstawowe kroki operacji arytmetycznych? Czy znalezienie gradientu krzywej jest krokiem? Czy znalezienie korzeni wielomianów jest krokiem? Czy znalezienie liczb całkowitych pierwiastków wielomianów jest krokiem? Każda z nich wydaje się równie naturalna. Jeśli jednak zezwolisz na wszystkie z nich, twoje „ściśle określone procedury” będą potężniejsze niż maszyny Turinga, co oznacza, że ​​mogą rozwiązywać rzeczy, których algorytmy nie mogą rozwiązać. Jeśli zezwolisz na wszystko oprócz ostatniego, nadal jesteś w sferze obliczeń Turinga.

Gdybyśmy nie mieli formalnej definicji algorytmu, nie bylibyśmy nawet w stanie zadać tych pytań. Nie bylibyśmy w stanie dyskutować, co algorytmy mogą zrobić, bo nie wiedzą, co algorytm jest .

Nie masz racji, gdy wielokrotnie wypowiadasz się na temat tego lub tego, że jest to „tylko tautologia”. Pozwól mi więc umieścić twoje roszczenia w nieco historycznym kontekście.

Przede wszystkim musisz sprecyzować stosowane pojęcia. Co jest problemem Co to jest algorytm? Co to jest maszyna? Może ci się wydawać, że są oczywiste, ale znaczna część lat 20. i 30. XX wieku została wydana przez logików próbujących to rozgryźć. Było kilka propozycji, z których jedną były maszyny Turinga, która odniosła największy sukces. Później okazało się, że inne propozycje były równoważne z maszynami Turinga. Musisz sobie wyobrazić epokę, w której słowo „komputer” oznaczało osobę, a nie maszynę. Po prostu płyniesz po fali i konsekwencjach genialnych wynalazków genialnych umysłów sprzed stu lat, nie zdając sobie z tego sprawy.

Maszyny Turinga są konkretnie opisane w kategoriach stanów, głowy i taśmy roboczej. Nie jest wcale oczywiste, że wyczerpuje to możliwości obliczeniowe wszechświata, w którym żyjemy. Czy nie moglibyśmy stworzyć mocniejszej maszyny wykorzystującej elektryczność, wodę lub zjawiska kwantowe? Co jeśli latamy maszynę Turinga do czarnej dziury z właściwą prędkością i kierunkiem, aby mogła wykonać nieskończenie wiele kroków w tym, co wydaje się nam skończonym czasem? Nie można po prostu powiedzieć „oczywiście nie” - najpierw należy wykonać kilka obliczeń ogólnej teorii względności. A co, jeśli fizycy znajdą sposób komunikowania się i kontrolowania równoległych wszechświatów, abyśmy mogli uruchomić nieskończenie wiele maszyn Turinga w tym samym czasie?

To nie nie ma znaczenia, że w chwili obecnej nie możemy zrobić te rzeczy. Ważne jest jednak to, że rozumiesz, że Turing musiał pomyśleć o tym, co było fizycznie możliwe (na podstawie ówczesnej wiedzy z fizyki). Nie tylko zapisał „zwykłą tautologię”. Daleko od tego, dokładnie przeanalizował, co oznacza obliczenia w sensie nieformalnym, a następnie zaproponował model formalny, bardzo ostrożnie argumentował, że model ten przechwytuje to, co ludzie rozumieją przez „obliczenia”, i wyprowadził z niego kilka ważnych twierdzeń na ten temat. Jedno z tych twierdzeń mówi, że maszyny Turinga nie są w stanie rozwiązać wszystkich problemów matematycznych (w przeciwieństwie do jednego z twoich fałszywych stwierdzeń). Wszystko to w jednym artykule, napisanym podczas letnich szczepień, gdy był studentem.powstał wynalazek nowoczesnego komputera ogólnego zastosowania. Potem była to tylko prosta kwestia inżynierii.

Czy to odpowiada, co Turing wniósł do ludzkości poza zwykłą tautologią? Czy czytałeś jego gazetę ?

To, że „wszystko, co można rozwiązać, może być reprezentowane przez algorytm”, wcale nie jest oczywiste.

Było to przedmiotem intensywnej debaty, ponieważ Alan Turing, przerabiając idee Alonzo Church, zaproponował definicję liczb obliczalnych, które przybrały formę maszyny, o której mówisz. Co ważne, w tamtym czasie nie byli to jedyni ludzie pracujący nad tego rodzaju rzeczami.

Nadal nazywamy to tezą - lub przypuszczeniem - ponieważ „wszystko, co można obliczyć”, wyraźnie nie jest precyzyjnym obiektem matematycznym, którego strukturę i zasięg można zbadać w sposób niespekulacyjny.

Po pierwsze, należy pamiętać, że maszyny Turinga zostały początkowo opracowane przez Turinga nie jako model dowolnego typu fizycznie wykonalnego komputera, ale raczej jako idealne ograniczenie tego, co można obliczyć człowiek oblicza w obliczeniach mechanicznych krok po kroku sposób (bez użycia intuicji). Ten punkt jest powszechnie źle rozumiany - patrz [1], aby uzyskać doskonałą prezentację na ten temat i pokrewne tematy.

Ograniczenia skończoności postulowane przez Turinga dla jego maszyn Turinga są oparte na postulowanych ograniczeniach ludzkiego aparatu sensorycznego. Uogólnienia analiz Turinga na fizycznie wykonalne urządzenia komputerowe (i analogiczne tezy Church-Turinga) pojawiły się dopiero później (1980) z powodu Robina Gandy'ego - z ograniczeniami opartymi na prawach fizyki. Jak mówi Odifreddi na str. 51 z [2] (biblia klasycznej teorii rekurencji)

Maszyny Turinga są urządzeniami teoretycznymi, ale zostały zaprojektowane z uwzględnieniem fizycznych ograniczeń. W szczególności wprowadziliśmy do naszego modelu ograniczenia wynikające z:

• (a) ATOMISM, zapewniając, że ilość informacji, które można zakodować w dowolnej konfiguracji maszyny (jako systemu skończonego) jest ograniczona; i

• (b) WZGLĘDNOŚĆ, wykluczając działania na odległość i sprawiając, że efekt przyczynowy rozprzestrzenia się poprzez interakcje lokalne. Gandy [1980] wykazał, że pojęcie maszyny Turinga jest na tyle ogólne, że obejmuje dokładnie, każde urządzenie komputerowe spełniające podobne ograniczenia.

i na str. 107: (Ogólna teoria dyskretnych, deterministycznych urządzeń)

Analiza (Church [1957], Kołmogorov i Uspenskii [1958], Gandy [1980]) rozpoczyna się od założeń atomizmu i teorii względności. Pierwszy z nich redukuje strukturę materii do skończonego zestawu podstawowych cząstek o ograniczonych wymiarach, a tym samym uzasadnia teoretyczną możliwość demontażu maszyny do zbioru podstawowych składników. Ta ostatnia nakłada górną granicę (prędkość światła) na prędkość propagacji zmian przyczynowych, a tym samym uzasadnia teoretyczną możliwość zmniejszenia efektu przyczynowego wytwarzanego w jednej chwili na ograniczonym obszarze przestrzeni V, do działań wytwarzanych przez regiony których punkty znajdują się w odległości c * t od pewnego punktu V. Oczywiście założenia nie uwzględniają układów, które są ciągłe lub które umożliwiają nieograniczone działanie na odległość (jak newtonowskie układy grawitacyjne).

Analiza Gandy pokazuje, że ZACHOWANIE MA REKURSUJĄCE SIĘ DLA KAŻDEGO URZĄDZENIA ZE STAŁYM ZWIĘKSZENIEM KOMPLEKSOWOŚCI JEGO MOŻLIWYCH KONFIGURACJI (w tym sensie, że zarówno poziomy nagromadzenia pojęć z poszczególnych składników, jak i liczba składników w dowolnej ustrukturyzowanej części dowolna konfiguracja, są ograniczone) ORAZ STAŁY SKOŃCZONY, DETERMINISTYCZNY ZESTAW INSTRUKCJI DOTYCZĄCYCH DZIAŁAŃ LOKALNYCH I GLOBALNYCH (pierwsza z nich mówi, jak określić wpływ działania na części ustrukturyzowane, druga - jak złożyć lokalne efekty). Co więcej, analiza jest optymalna w tym sensie, że po dokładnym rozluźnieniu warunków staje się kompatybilna z dowolnym zachowaniem, a zatem zapewnia wystarczający i konieczny opis zachowania rekurencyjnego.

Analiza Gandy daje bardzo pouczające spojrzenie na moc i ograniczenia maszyn Turinga. Warto przeczytać, aby uzyskać więcej informacji na te tematy. Ostrzegamy jednak, że artykuł Gandy'ego z 1980 r. [3] jest uważany za trudny nawet przez niektórych cognoscenti. Pomocne może okazać się zapoznanie się z artykułami w [4] J. Shepherdsona i A. Makowsky'ego.

[1] Sieg, Wilfried. Procedury mechaniczne i doświadczenie matematyczne. [s. 71–117 w Matematyki i umyśle. Artykuły z konferencji na temat filozofii matematyki, która odbyła się w Amherst College, Amherst, Massachusetts, 5-7 kwietnia 1991 r. Pod redakcją Alexander George. Logika obliczeniowa. Philos., Oxford Univ. Press, New York, 1994. ISBN: 0-19-507929-9 MR 96m: 00006 (Recenzent: Stewart Shapiro) 00A30 (01A60 03A05 03D20)

[2] Odifreddi, Piergiorgio. Klasyczna teoria rekurencji. Teoria funkcji i zbiorów liczb naturalnych. Ze wstępem GE Sacks. Studies in Logic and the Foundations of Mathematics, 125. North-Holland Publishing Co., Amsterdam-Nowy Jork, 1989. xviii + 668 s. ISBN: 0-444-87295-7 MR 90d: 03072 (Recenzent: Rodney G. Downey ) 03Dxx (03-02 03E15 03E45 03F30 68Q05)

[3] Gandy, Robin. Teza Kościoła i zasady mechanizmów. Sympozjum Kleene. Materiały z sympozjum odbywającego się na University of Wisconsin, Madison, Wis., 18-24 czerwca 1978 r. Pod redakcją Jon Barwise, H. Jerome Keisler i Kenneth Kunen. Studia logiki i podstawy matematyki, 101. North-Holland Publishing Co., Amsterdam-Nowy Jork, 1980. xx + 425 s. ISBN: 0-444-85345-6 MR 82h: 03036 (Recenzent: Douglas Cenzer) 03D10 (03A05)

[4] Uniwersalna maszyna Turinga: ankieta z pół wieku. Druga edycja. Pod redakcją Rolf Herken. Computerkultur [Kultura komputerowa], II. Springer-Verlag, Wiedeń, 1995. XVI + 611 s. ISBN: 3-211-82637-8 MR 96j: 03005 03-06 (01A60 03D10 03D15 68-06)

Najlepszą popularną dyskusją na to pytanie, jaką kiedykolwiek przeczytałem, jest esej profesora MIT Scotta Aaronsona, który może nazwać większą liczbę? , w którym bada między innymi implikacje maszyn super-Turinga, maszyn Turinga i maszyn Turinga.

Nie, bazy TM nie są najmocniejsze. Dwa przykłady:

a) Mogą istnieć inne maszyny, które obliczają te same wyniki co TM, ale algorytmicznie szybsze (np. komputery kwantowe obliczające czynniki pierwsze). „Szybszy” jest rodzajem siły.

b) TM nie mogą reprezentować ogólnych liczb rzeczywistych z doskonałą precyzją. Ale komputer analogowy (AC) może być w stanie reprezentować i wykonywać arytmetykę liczb rzeczywistych z doskonałą precyzją. Byłoby to silniejsze niż jakakolwiek TM.

Oczywiście (b) wymaga, aby nasz wszechświat miał pewne ciągłe właściwości (grawitacja?), Które AC może wykorzystać do przedstawienia rzeczywistych wartości. Może każda własność fizyczna, w tym grawitacja, jest kwantowana. Ale możemy spekulować na temat maszyn w ciągłym wszechświecie. Zatem bazy TM nie są najsilniejsze „z definicji”.

Jeśli spojrzysz na złożoność obliczeniową, maszyna Turinga jest najpotężniejszą maszyną - ponieważ ma nieograniczoną pamięć i nie ma jej żadna prawdziwa maszyna. Żadna prawdziwa maszyna nie może rozwiązać problemów o dowolnym rozmiarze; nie potrafią nawet odczytać problemu, a tym bardziej go rozwiązać.

Z drugiej strony, jeśli spróbujesz zaimplementować prawdziwą maszynę Turinga, powiedzmy z zastrzeżeniem, że zatrzyma się i zabrzmi alarm, jeśli skończy się taśma, przekonasz się, że wykonanie wielu obliczeń wymagałoby znacznie więcej kroków niż, powiedzmy, prawdziwa maszyna w tanim telefonie i byłaby znacznie wolniejsza w rozwiązywaniu prawdziwych problemów. Przekonasz się również, że pisanie odpowiedzi na taśmie nie jest bardzo dobrym interfejsem użytkownika. Przekonasz się, że wiele osób korzysta z komputerów nie w celu rozwiązywania problemów, ale w celu wysyłania nagich zdjęć do znajomych i oglądania filmów kotów, a Maszyna Turinga w ogóle do tego nie służy.