moi ulubieni autorzy (David Deutsch, Roger Penrose i Douglas Hofstadter) zagłębiają się w kościelną tezę Turinga o teorii obliczeniowej i, co ważniejsze, jej najsilniejszą interpretację: zasadę Turinga. W tym poście najpierw wyjaśnię tezę kościelno-Turinga w kategoriach laickich.
kiedy pracowałem nad moim dyplomem z informatyki, studiowałem maszyny Turinga i pracę Churcha Turinga na wstępie do klasy teorii obliczeniowej. Wtedy myślałem, że to wielka strata czasu. Chciałem tylko zaprogramować Komputery i nie mogłem się przejmować tym dawno martwym gościem Turinga (ani tym facetem z kościoła) ani jego głupimi teoretycznymi maszynami.
teraz, kiedy Rozumiem filozoficzne konsekwencje tezy kościelno-Turinga, żałuję, że nie zwróciłem uwagi na zajęciach! Ponieważ teza kościelno-Turinga, jeśli jest prawdziwa, ma pewne głębokie konsekwencje filozoficzne i może nam również powiedzieć coś o głębokiej-i szczególnej-naturze rzeczywistości.
automaty skończone
wszystkie teksty i klasy z teorii obliczeń zaczynają się od czegoś, co nazywa się ” automatami skończonymi.”Podstawowa idea stojąca za nimi jest dość prosta. Wystarczy wyobrazić sobie prostą „maszynę”, która jest w stanie dokonywać wyborów i poruszać się między Stanami. Oto przykład bardzo prostego, który reprezentuje „logikę” kołowrotu na monety.
w prostym języku angielskim, mówi to, że jeśli spróbujesz przepchnąć przez zablokowany kołowrót, nie możesz, jeśli nie włożyłeś najpierw monety. Jeśli włożyłeś monetę, ale jeszcze nie przebiłeś, dodatkowe monety po prostu pozostaw ją w stanie odblokowanym. Jeśli włożyłeś monetę, możesz ją przepchnąć. Następnie zamyka się ponownie dla następnej osoby.
to chyba łatwiej było zrozumieć z diagramu niż z opisu.
automaty skończone są w stanie wykonywać znacznie bardziej skomplikowaną logikę niż ta. Ale to powinno dać wam podstawowe odczucie jak działają automaty skończone.
należy zauważyć, że skończony automat, jak ten powyżej, jest czysto teoretyczny, ponieważ istnieje tylko jako pęk pęcherzyków i linii na kartce papieru. To nie jest tak, że jest jakaś mała „skończona maszyna automatyczna” wewnątrz kołowrotu, która podejmuje te decyzje. A może powinienem zamiast tego powiedzieć, że sam kołowrót jest skończonym automatem.
gdybyśmy naprawdę chcieli, prawdopodobnie moglibyśmy zbudować maszynę w prawdziwym życiu, która byłaby skończonym automatem.Nic nie powstrzymuje kogoś przed zbudowaniem go jako prawdziwej maszyny w prawdziwym życiu, a następnie zainstalowaniem go w kołowrotku. To nie jest najtańszy sposób.
więc każdy 'program’, który tworzysz jako rysunek skończonego automatu, może zostać przekształcony w prawdziwe „obliczenie”, które naprawdę działa. Znaczenie różnicy między maszyną obliczeniową, która może faktycznie istnieć (jak automat skończony) a maszyną, która jest tylko hipotetyczna i narusza prawa fizyki, staje się ważne w jednej chwili.
mocniejsze Maszyny
w miarę postępu zajęć z teorii obliczeniowej uczniowie są wprowadzani do coraz bardziej złożonych „maszyn”, które są mocniejsze niż automaty skończone. Jak pokazuje rysunek po prawej stronie, następnym najpotężniejszym jest Pushdown Automata (PDA). PDA to tak naprawdę tylko DFA z dodatkiem czegoś w rodzaju „pamięci”. Ta pamięć pozwala PDA na tworzenie i uruchamianie obliczeń (lub programów), których Dfa nie może.
kluczowym punktem jest tylko to, że istnieją pewne typy programów, które mogą być napisane dla PDA, które nie mogą być napisane na deterministycznym automacie skończonym (Dfa). Innymi słowy PDA są ” potężniejsze „niż Dfa, ponieważ mogą wyrażać klasy” programów”, których Dfa nie mogą.
istnieje więc związek między Dfa a PDA pod względem ” mocy obliczeniowej.”Mianowicie można udowodnić, że każdy program napisany na DFA może być również napisany na PDA, ale odwrotność nie jest prawdą.
dowód znajduje się w dowodzie
dowód, że PDA może uruchomić wszystko, co DFA może zrobić, wymyślając schemat, za pomocą którego logika DFA może być odwzorowana na PDA. Ponieważ PDA to tylko DFA z pamięcią, nie jest to trudne — po prostu nie używaj „funkcji pamięci”.
ale co z rewersem? Czy możemy udowodnić, że niemożliwe jest wzięcie pewnych rodzajów „programów” napisanych na PDA i przełożenie ich na DFA? To znaczy, czy istnieje dowód na to, że automaty Pushdown nie mogą być zmapowane do automatów skończonych? A może po prostu Zakładamy, że skończony automat jest mniej wydajny niż automat Pushdown, ponieważ obecnie nie znamy sposobu mapowania PDA z powrotem do FDA? Może istnieje sposób na mapowanie PDA na FDA i może nikt jeszcze nie odkrył jak to zrobić? Czy to nie jest możliwe?
jak się okazuje, można udowodnić, że PDA może uruchamiać pewne typy programów, których Dfa nie może. Sposób, w jaki to zrobisz, to znajdziesz obliczenia (tj. program), że można udowodnić, że DFA nie może obliczyć, a następnie wykazać, że PDA może to obliczyć.
moc obliczeniowa Maszyny
ten fakt — że istnieją potężniejsze (PDA) i mniej wydajne (Dfa) maszyny logiczne — jest interesujący sam w sobie.
ale to prowadzi do filozoficznego pytania: czy istnieje coś takiego jak ” najpotężniejsza maszyna obliczeniowa?”
gdyby istniała taka „najpotężniejsza maszyna”, skąd byśmy wiedzieli, że jakaś konkretna proponowana maszyna jest ” najpotężniejsza?”A może są dostępne tylko różne typy maszyn obliczeniowych i trzeba wybrać odpowiednią do tego zadania?
maszyny Turinga
jaka maszyna jest mocniejsza od PDA?
jak mówi historia, w tym samym czasie zaproponowano dwa bardzo różne typy „maszyn”, które były prawdopodobnie mocniejsze niż PDA.
jednym z nich była maszyna Turinga Alana Turinga. Drugi był nie tyle maszyną, co sprytnym zestawem notacji opracowanych przez Alonzo Churcha, które służyły temu samemu celowi, co opracowanie maszyny. Z tych dwóch” maszyn ” maszyna Turinga jest koncepcyjnie łatwiejsza do nauczenia, więc zwykle jest to maszyna, która jest nauczana na kursie teorii obliczeniowej.
maszyny Turinga są zabawnymi małymi maszynami teoretycznymi, które mają głowicę odczytu/zapisu i (hipotetyczną) taśmę papierową, z której może odczytywać lub zapisywać. W oparciu o to, co czyta maszyna Turinga, wprowadza maszynę Turinga w stan akcji, który wykonuje jakąś kombinację zadań polegającą na przesuwaniu głowicy odczytu/zapisu do przodu lub do tyłu, odczytywaniu z nowej pozycji na taśmie lub zapisywaniu nowej pozycji na taśmie. Maszyna Turinga wygląda tak:
maszyny Turinga i nowoczesne komputery
jedną z rzeczy interesujących jest to, że maszyna Turinga jest, pomimo wyglądu powierzchniowego, w rzeczywistości bardzo podobna do nowoczesnego komputera. W nowoczesnym komputerze jednostka centralna (CPU) jest odpowiednikiem głowicy odczytu / zapisu maszyny Turinga. Układy pamięci (RAM lub ROM)są bardzo podobne do komórek długiej taśmy papierowej, z której maszyna Tokarska może odczytywać lub zapisywać. Współczesne komputery wydają się być mniej więcej odpowiednikiem maszyny Turinga.
nowoczesny komputer ma jedną przewagę nad maszyną Turinga. Nowoczesny komputer nie musi przemieszczać się z jednej komórki swojej „pamięci” w kolejności sekwencyjnej, jak robi to maszyna Turinga.
fakt, że maszyna Turinga może przenosić tylko jedną komórkę na raz, wydaje się poważnym ograniczeniem, prawda? Właśnie zobaczyliśmy, jak niektóre maszyny są logicznie „mocniejsze” od innych: PDA może wykonywać zadania obliczeniowe, których nie może FDA. Więc być może są maszyny, które są potężniejsze niż maszyny Turinga, które mogą wykonywać zadania, których maszyny Turinga nie mogą? A może nowoczesny komputer — ze względu na zdolność do skakania po pamięci, a nie przechodzenia z komórki na komórkę sekwencyjnie-może uruchomić niektóre programy, których maszyna Turinga nie potrafi?
w rzeczywistości współczesny komputer ma mniejszą siłę ekspresji niż maszyna Turinga, ponieważ maszyny Turinga zostały pomyślane jako posiadające nieskończenie długą taśmę papierową (tj. nieskończoną pamięć), gdzie jako prawdziwy komputer zawsze będzie miał skończoną pamięć. Jednak w ogóle to robi bardzo małą różnicę w tym, jakie rodzaje obliczeń można wykonać, ponieważ istoty ludzkie nie są na ogół wszystkim, którzy są zainteresowani nieskończenie długimi obliczeniami, które dają nieskończenie długie wyniki. Dlatego mówię, że nowoczesne komputery i maszyny Turinga są „mniej więcej” odpowiednikami. W rzeczywistości, tak długo jak zakładamy dowolny, ale skończony rozmiar pamięci, są one dokładnie równoważne pod względem rodzajów programów, które mogą uruchamiać.
Kościół teza Turinga: maszyna Turinga = Max Moc logiczna
ale co z biednym Kościołem Alonzo? Jego biedna „maszyna” zapomniała, bo maszyny Turinga są łatwiejsze do nauczenia. Czy jego maszyna może być w stanie wyrazić pewne obliczenia / programy, których maszyna Turinga nie może, lub odwrotnie?
czy to nie byłby niesamowity zbieg okoliczności, gdyby tak się stało, że Alan Turing i Alonzo Church tak się złożyli, tworząc dwa zupełnie różne typy teoretycznych maszyn obliczeniowych i tak się złożyło, że były one dokładnie identyczne pod względem rodzajów obliczeń, które mogliby wykonać?
wyobraźcie sobie zdziwienie wszystkich, kiedy Alan Turing był w stanie przedstawić dowód, że każdy program napisany dla maszyny Turinga może być również napisany dla maszyny Turinga, a także dowód, że każdy program napisany dla maszyny kościelnej może być również napisany dla maszyny Turinga.
w rzeczywistości istnieje wiele proponowanych typów teoretycznych maszyn obliczeniowych. Na przykład teoretycy próbowali pozwolić maszynie Turinga na posiadanie wielu taśm do odczytu/zapisu. Próbowali nawet pozwolić maszynie Turinga na 2-wymiarowy „arkusz” do odczytu i zapisu. Teoretycy próbowali wszelkiego rodzaju ulepszeń maszyn Turinga (i maszyn kościelnych).
i do tej pory udało się stworzyć dowód dla każdego z nich, że są one równoważne prostej maszynie Turinga.
to chyba dziwny zbieg okoliczności, prawda? I byłby to dziki zbieg okoliczności, chyba że istnieje górna ograniczona do tego, jakie rodzaje obliczeń można wykonać.
jeśli istnieje taka górna granica, to nie byłoby przypadkiem, że maszyna Turinga, Maszyna Churcha i wszystkie inne maszyny obliczeniowe zaproponowały wszystko, co ma taką samą moc obliczeniową, ponieważ w rzeczywistości powodem, dla którego wszystkie są równoważne, jest to, że osiągnęliśmy górną granicę mocy obliczeniowej.
ale czy możemy udowodnić, że nie ma jakiejś maszyny obliczeniowej — takiej, której jeszcze nie odkryliśmy — która ma zdolność do wykonywania obliczeń, których maszyna Turinga nie może?
jak, dokladnie, stworzyc taki dowód? Faktem jest, że nie możemy udowodnić, że nie ma nic potężniejszego niż maszyna Turinga. Kto wie, może jest.
ale faktem jest, że nie możemy znaleźć (ani wymyślić) takich maszyn.
tak więc po sporym wysiłku prób i niepowodzeń, aby znaleźć sposób na poprawę mocy maszyn Turinga, ostatecznie teza Kościoła-Turinga została przyjęta, mimo że nie została udowodniona, że jest prawdziwa. Teza kościelno-Turinga zasadniczo mówi coś takiego:
nie można wymyślić żadnej maszyny obliczeniowej, która może wykonać program logiczny, którego zwykła stara maszyna Turinga nie może.
lub innymi słowy:
maszyny Turinga i ich odpowiedniki są najpotężniejszymi możliwymi typami maszyn obliczeniowych i nie ma mocniejszych, o których jeszcze nie wiemy.
po wielu latach badań nad tą tezą, teza ta nadal zasadniczo się trzyma. Zobaczymy później, że nastąpiła pewna modyfikacja tezy wraz z wprowadzeniem teoretycznych komputerów kwantowych. Ale zasadniczo teza ta nadal jest prawdziwa. Nikt nigdy nie wymyślił sposobu, aby prześcignąć maszyny Turinga, jeśli chodzi o logiczną ekspresję. Maszyny Turinga są nadal aktualnym Mistrzem.
więc teraz rozumiesz tezę Kościoła-Turinga. Teza kościelno-Turinga nie jest jednak do końca równoznaczna z zasadą Turinga. Więc w przyszłym poście rozwinę, jaka jest różnica i jakie są filozoficzne konsekwencje.
Uwagi
Zasada Turinga. Tak nazwany przez Rogera Penrose ’ a, który w niego nie wierzy (przynajmniej nie w obecnej formie). Została ona rozwinięta w zasadę Turinga-Deutsch przez Davida Deutsch, który wierzy w nią, przynajmniej w swoją formę.) (Więcej szczegółów w artykule w Wikipedii)