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

54

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?

Sounak Bhattacharya
źródło
9
Tokarka nie może rozwiązać problemu zatrzymania. Jednak nie ma dowodów na to, że nie ma maszyny do jego rozwiązania. Model jest rodzajem TM z oracle lub całkowicie odmiennym podejściem. Jeśli podążasz za tezą Kościoła, TM reprezentuje tylko maszyny, z których obecnie korzystamy.
Eugene
16
To najmocniejsza maszyna, jaką potrafimy zbudować . Właściwie nie, możemy budować tylko skończone automaty.
Raphael
13
Twoim problemem jest to, że myślisz o bazach TM jako o czymś, co nastąpiło później. Nie było. Został (i jest) użyty do zdefiniowania klasy problemów obliczalnych Turinga . Znaleziono wiele równoważnych modeli, ale to nie zmienia definicji.
Raphael
3
Istnieją setki różnych (kompletnych Turingów) architektur komputerowych, wszystkie z bardzo różnymi zestawami instrukcji. Nie sądzę, że to oczywiste, w ogóle , że nie ma problemu, że można rozwiązać, ale innego nie może.
BlueRaja - Danny Pflughoeft
5
... czy to, co mówisz, nie jest po prostu tezą Turinga ? O ile wiemy, nikt nie obalił tezy, ale nie możemy wykluczyć istnienia innego modelu obliczeń, który jest „rozsądny” (tj. W pewien sposób możliwy do wdrożenia) i silniejszy niż bazy TM.
Bakuriu,

Odpowiedzi:

135

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 .

David Richerby
źródło
3
Komentarze nie są przeznaczone do rozszerzonej dyskusji; ta rozmowa została przeniesiona do czatu .
DW
Nie masz na myśli racjonalnych rozwiązań? Myślę, że rozwiązania całkowite można wykonać w skończonej liczbie kroków.
Trenin
2
@Trenin Link do strony w Wikipedii, którą zamieszczam, mówi „racjonalna liczba całkowita”, co tłumaczy, że jest frazą czasami używaną do odróżnienia zwykłych liczb całkowitych od obiektów takich jak liczby całkowite Gaussa (liczby zespolone za+jab gdzie , b Z ). za,bZ
David Richerby,
Rozumiem. Poza tym to, co uważałem za możliwe, okazuje się znacznie trudniejsze niż myślałem.
Trenin,
64

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ę ?

Andrej Bauer
źródło
19
„Musisz sobie wyobrazić epokę, w której słowo„ komputer ”oznaczało osobę, a nie maszynę”. To bardzo pomocne przypomnienie. Zasadniczo Turing starał się skutecznie symulować za pomocą swojej „maszyny” operacje, które dana osoba może wykonywać za pomocą pióra i papieru w tym czasie, aby coś obliczyć.
Sorrop
2
„Jego twierdzenie o istnieniu uniwersalnych maszyn było wynalezieniem nowoczesnego komputera ogólnego przeznaczenia”. - Cóż ... może w świecie matematyki. Ludzie tacy jak Konrad Zuse opracowali niezależnie komputery ogólnego zastosowania.
Raphael
6
@AndrejBauer To wciąż sugeruje oś czasu i zależność, których nie było, nie we wszystkich przypadkach. Nie obwiniam cię - niewiele osób wie, co zrobił Zuse. Faktem jest, że budował komputery od 1935 r. Przez całą II wojnę światową bez większego wkładu spoza Niemiec. W tym czasie opracował również swój Plankalkül. Myślę, że tak było z komputerami, jak z wieloma innymi rzeczami: nadszedł czas, tak wiele umysłów myślało podobnie. Chodzi o to, że Turing nie wymyślił komputerów .
Raphael
12
@Raphael: Konrad Zuse nie wiedział, że jego maszyna może przetwarzać wszystkie problemy obliczeniowe (teraz wiemy, że jego maszyny SĄ kompletne - pamięć modulo). Przyczynił się Turing NIE NIE pomysł, że maszyny mogą wykonywać obliczenia - Babbage zrobił to przed Zuse lub Turing. Turing przyczynił się do pomysłu, że zestawy instrukcji i języki programowania nie mają tak naprawdę znaczenia w teorii. To nie jest oczywisty pomysł. Jak na ironię to właśnie ta idea napędza rozwój procesorów i języków programowania
slebetman,
1
„zestawy instrukcji i języki programowania nie mają tak naprawdę znaczenia w teorii” - to oczywiście nieprawda. Różnice mogą mieć znaczenie, ale nie zawsze. Turing zdefiniował pewien model obliczeń i twierdził, że jest tak potężny, jak to tylko możliwe. Złapany między zastrzeżeniem nieskończonej pamięci a mocniejszymi modelami, nie jestem zbyt pewien, czy to twierdzenie zawiera jakąkolwiek wodę. Tak więc w pewnym sensie nie zrobił nic więcej niż Zuse, gdyby matematyka zamiast metalu.
Raphael
23

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.

André Souza Lemos
źródło
1
Ale wszystko, co można rozwiązać, musi zostać rozwiązane przez „proces” (z definicji). W tej chwili możemy nie znać procesu rozwiązania konkretnego „możliwego do rozwiązania” problemu. W takim przypadku oznacza to, że problem można rozwiązać, ale nie można go teraz rozwiązać. Czy nie oznacza to skutecznie, że „wszystko, co można rozwiązać, może być reprezentowane przez algorytm”, ponieważ „proces” = „algorytm”. Dlaczego mówisz, że to nie jest oczywiste?
Sounak Bhattacharya
13
Co to jest „proces”? Widzisz, łatwo jest biegać w kółko, zastępując jedną niejasną koncepcję inną. Próba Turinga była w rzeczywistości wcielonym eksperymentem myślowym, który do dziś napędza naszą wyobraźnię. To nie jest mała rzecz.
André Souza Lemos,
@SounakBhattacharya W pewnym procesie (lat i geniuszu) Sir Andrew Wiles udowodnił, że ostatnie twierdzenie Fermata jest prawdziwe. Czy wyobrażasz sobie, że istnieje TM, która mogłaby dokonać takiej determinacji?
OJFord,
1
@OllieFord Cóż, jeśli dowód jest wystarczająco rygorystyczny, aby każdy krok można było wyrazić w kategoriach istniejących dobrze określonych aksjomatów, wówczas dowód można zweryfikować za pomocą maszyny Turinga. Możemy wtedy określić maszynę Turinga, która wylicza wszystkie możliwe dowody i na pewno (ale bardzo powoli) maszyna znalazłaby taki dowód. Prosta fizyczna implementacja tej maszyny Turinga zajęłaby jednak ponad 400 lat i znacznie dłużej niż oczekiwany okres życia wszechświata.
gmatht,
19

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)

Bill Dubuque
źródło
2
Dziękuję bardzo! Zawsze uważałem, że maszyny Turinga były dziwnie nieeleganckie, ale to słusznie wyjaśnia, dlaczego może to być źle zrozumiane.
PJTraill,
6

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.

James Brock
źródło
2
Po „super-duper-pooper” pojawia się „super-duper-ooper-flooper”, a przynajmniej wydaje mi się, że pamiętam to, kiedy miałem 7 lub 8 lat. To prawdopodobnie poprawna terminologia formalna.
Peter Cordes,
4

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”.

Adam Gawne-Cain
źródło
3
Witamy na stronie! „Silniejszy” w kontekście teorii obliczeń zwykle oznacza „zdolny do obliczenia większej liczby funkcji”, a nie „zdolny do obliczenia w kilku krokach”, więc nie jestem pewien, czy twoje (a) naprawdę się liczy. Nie jest też jasne, w jaki sposób komputer może wykorzystywać prawdziwe wartości. Jak wprowadziłbyś prawdziwą wartość, która nie byłaby, powiedzmy, obliczalną rzeczywistością? Jak powiedziałbyś komuś innemu, jaką wartość powinien wnieść do swojej ciągłej maszyny i jak poradziłbyś sobie z hałasem? Ale może to głupi sprzeciw: „Jak wyprodukowałbyś wystarczającą ilość taśmy do użycia przez maszynę Turinga”.
David Richerby,
-4

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.

gnasher729
źródło
12
Czy możesz wyjaśnić, jak to odpowiada na pytanie?
David Richerby,
1
Oczywiście prawdziwa maszyna Turinga byłaby w stanie przetwarzać zdjęcia i filmy. Pewne urządzenie wyjściowe obrazu byłoby oczywiście potrzebne, aby ludzie je zobaczyli, ale dotyczy to każdego komputera; CPU + pamięć na płytce drukowanej też nie jest „w ogóle do tego użyteczna”.
hyde
1
Wśród modeli maszyn z nieskończoną pamięcią, TM nie należą do najmocniejszych!
Raphael