Możliwość zastosowania tezy Church-Turinga do interaktywnych modeli obliczeniowych

Paul Wegner i Dina Goldin od ponad dekady publikują artykuły i książki, argumentując przede wszystkim, że teza o Kościele Turinga jest często fałszywie przedstawiana w społeczności CS Teorii i gdzie indziej. Oznacza to, że jest prezentowany jako obejmujący wszystkie obliczenia, podczas gdy w rzeczywistości dotyczy on tylko obliczeń funkcji, które są bardzo małym podzbiorem wszystkich obliczeń. Zamiast tego sugerują, że powinniśmy starać się modelować obliczenia interaktywne, podczas których komunikacja ze światem zewnętrznym odbywa się podczas obliczeń.

Jedyną krytyką, jaką widziałem w tej pracy, jest forum Lambda the Ultimate , gdzie ktoś ubolewał nad tymi autorami za ciągłe publikowanie tego, co jest oczywiście znane. Moje pytanie brzmi zatem: czy jest jakaś krytyka w tym sposobie myślenia, w szczególności w ich Wytrwałych Maszynach Turinga. A jeśli nie, to dlaczego wydaje się, że jest bardzo mało badany (mogę się mylić). Wreszcie, w jaki sposób pojęcie uniwersalności przekłada się na domenę interaktywną.

Oto moja ulubiona analogia. Załóżmy, że spędziłem dekadę, publikując książki i artykuły, argumentując, że w przeciwieństwie do dogmatu teoretycznej informatyki, teoria Kościoła-Turinga nie uchwyciła wszystkich obliczeń, ponieważ maszyny Turinga nie są w stanie opiekać chleba . Dlatego potrzebujesz mojego rewolucyjnego nowego modelu, Turing-Enhanced Turing Machine (TETM), który pozwala na chleb jako możliwy wkład i obejmuje opiekanie go jako prymitywną operację.

Można powiedzieć: jasne, mam „rację”, ale jest to całkowicie nieciekawe. Nikt nigdy nie twierdził, że maszyna Turinga poradziłaby sobie z każdą możliwą interakcją ze światem zewnętrznym, bez uprzedniego podłączenia go do odpowiednich urządzeń peryferyjnych. Jeśli chcesz, aby TM opiekała chleb, musisz połączyć go z tosterem; wtedy TM może z łatwością poradzić sobie z wewnętrzną logiką tostera (chyba że ten konkretny toster wymaga rozwiązania problemu zatrzymania lub czegoś takiego, aby określić, jak brązowy powinien być chleb!). Dokładnie w ten sam sposób, jeśli chcesz, aby TM obsługiwała komunikację interaktywną, musisz podłączyć ją do odpowiednich urządzeń komunikacyjnych, jak Neel omówił w swojej odpowiedzi. W żadnym wypadku nie mówimy niczego, co nie byłoby oczywiste dla samego Turinga.

Powiedziałbym więc, że powodem, dla którego nie było „kontynuacji” diatrybetów Wegnera i Goldina, jest to, że TCS umie modelować interaktywność w razie potrzeby i chętnie to robi, od samego początku tej dziedziny.

Aktualizacja (8/30): Powiązany punkt jest następujący. Czy krytycy kiedykolwiek zatrzymują się, że tutaj, w elitarnej wieży kościoła z kości słoniowej Turinga (ECTIT), głównymi tematami badań w ciągu ostatnich dwóch dekad były interaktywne dowody, wielopartyjne protokoły kryptograficzne, kody do interaktywnej komunikacji, asynchroniczne protokoły routingu , konsensus, rozpowszechnianie plotek, wybory liderów itp., a także cena anarchii w sieciach gospodarczych? Jeśli umieszczenie pojęcia obliczeń Turinga w centrum pola sprawia, że ​​tak trudno jest omówić interakcję, to dlaczego tak niewielu z nas zauważyło?

Kolejna aktualizacja: dla ludzi, którzy ciągle walą w bęben, że formalizacje wyższego poziomu są znacznie bardziej intuicyjne niż bazy TM i nikt nie myśli w kategoriach baz TM jako sprawy praktycznej, pozwólcie, że zadam niezwykle proste pytanie. Co sprawia, że ​​wszystkie języki wysokiego poziomu istnieją przede wszystkim, co gwarantuje, że zawsze można je skompilować do kodu maszynowego? Czy to może być ... Ech ... TURYSTYKA KOŚCIOŁA , ta sama, na którą się szarpałeś? Aby wyjaśnić, teza Kościoła Turinga nie jest twierdzeniem, że „ZASADA TUROWANIA MASZYNA !!” Jest raczej twierdzeniem, że każdy rozsądny język programowania będzie równoważny pod względem ekspresji mocy z maszynami Turinga - i w konsekwencji, że równie dobrze możesz myśleć w kategoriach języków wyższego poziomu, jeśli jest to wygodniejsze. Był to oczywiście zupełnie nowy wgląd 60–75 lat temu.

Ostatnia aktualizacja: Stworzyłem post na blogu w celu dalszej dyskusji na temat tej odpowiedzi.

Myślę, że problem jest dość prosty.

1. Wszystkie interaktywne formalizmy mogą być symulowane przez maszyny Turinga.

2. Bazy TM są niewygodnymi językami do badań nad obliczeniami interaktywnymi (w większości przypadków), ponieważ ciekawe problemy zagłuszają hałas kodowania.

3. Każdy, kto pracuje nad matematyzacją interakcji, wie o tym.

Pozwól, że wyjaśnię to bardziej szczegółowo.

Maszyny Turinga mogą oczywiście modelować wszystkie istniejące interaktywne modele obliczeń w następującym znaczeniu: Wybierz kodowanie odpowiedniej składni jako ciągi binarne, napisz TM, która przyjmuje jako dane wejściowe dwa zakodowane programy interaktywne P, Q (w wybranym modelu obliczeń interaktywnych) i zwraca prawdę dokładnie wtedy, gdy w odpowiednim systemie przepisywania terminów występuje jednoetapowe zmniejszenie z P do Q (jeśli rachunek różniczkowy ma trójskładnikową relację przejścia, postępuj mutatis mutandis). Masz więc TM, która wykonuje symulację krok po kroku obliczeń w rachunku interaktywnym. W tym sensie można wyrazić wyraźnie rachunek pi, rachunek otoczenia, CCS, CSP, sieci Petriego, rachunek pi w czasie i dowolny inny interaktywny model obliczeń. To ludzie mają na myśli, mówiąc, że interakcja nie wykracza poza TM.

N. Krishnaswami odnosi się do drugiego podejścia do modelowania interaktywności za pomocą taśm oracle. To podejście różni się od interpretacji powyższej relacji redukcji / przejścia, ponieważ zmienia się pojęcie TM: przechodzimy od zwykłych TM do TM z taśmami Oracle. Takie podejście jest popularne w teorii złożoności i kryptografii, głównie dlatego, że umożliwia badaczom z tych dziedzin transfer swoich narzędzi i wyników z sekwencyjnego do współbieżnego świata.

Problem z obydwoma podejściami polega na tym, że problemy teoretyczne dotyczące współbieżności są ukryte. Teoria współbieżności stara się rozumieć interakcję jako zjawisko sui generis. Oba podejścia za pośrednictwem baz TM zastępują wygodny formalizm do wyrażania interaktywnego języka programowania mniej wygodnym formalizmem.

W żadnym z tych podejść rzeczywiście teoretyczne kwestie teoretyczne, tj. Komunikacja i jej infrastruktura wspierająca mają bezpośrednią reprezentację. Są tam, widoczne dla wytrenowanego oka, ale zakodowane, ukryte w nieprzeniknionej mgle złożoności kodowania. Oba podejścia są złe w matematatyzacji kluczowych problemów związanych z obliczeniami interaktywnymi. Weźmy na przykład to, co może być najlepszym pomysłem w teorii języków programowania w ostatnim półwieczu, aksjatyzacja ekstruzji zakresu przez Milnera i in. (Co jest kluczowym krokiem w ogólnej teorii kompozycyjności):

Jak pięknie ten pomysł jest wyrażony w języku dostosowanym do potrzeb, takim jak rachunek pi. Wykonanie tego przy użyciu kodowania pi-rachunku w bazach TM prawdopodobnie wypełniłoby 20 stron.

Innymi słowy, wynalazek jawnych formalizmów interakcji wniósł do informatyki następujący wkład: bezpośrednia aksjatyzacja kluczowych prymitywów komunikacji (np. Operatory wejścia i wyjścia) oraz mechanizmów wspierających (np. Generowanie nowych nazw, składanie równoległe itp.) . Ta aksjatyzacja stała się prawdziwą tradycją badawczą z własnymi konferencjami, szkołami i terminologią.

Podobna sytuacja występuje w matematyce: większość pojęć można zapisać za pomocą języka teorii mnogości (lub teorii toposu), ale przeważnie preferujemy pojęcia wyższego poziomu, takie jak grupy, pierścienie, przestrzenie topologiczne i tak dalej.

Pod względem obliczalności liczbowej (tj. Funkcji obliczeniowych z ) wszystkie znane modele obliczeń są równoważne.$\mathbb{N} \to \mathbb{N}$

Jednak nadal jest prawdą, że maszyny Turinga są dość bolesne w przypadku modelowania takich właściwości, jak interaktywność. Powód jest nieco subtelny i dotyczy rodzajów pytań, które chcemy zadać na temat obliczeń interaktywnych.

Zwykle pierwsze przejście w interakcji modelowania z bazami TM odbywa się za pomocą taśm Oracle. Intuicyjnie możesz traktować ciąg wydrukowany na taśmie wyroczni jako „prognozę” interakcji we / wy maszyny Turinga z otoczeniem. Zastanów się jednak, jakie pytania chcemy zadać na temat programów interaktywnych: na przykład możemy chcieć wiedzieć, że program komputerowy nie wyśle ​​twoich danych finansowych, chyba że otrzyma twoją nazwę użytkownika i hasło jako dane wejściowe, a ponadto, że programy nie przeciekają informacje o hasłach. Mówienie o tego rodzaju ograniczeniach jest bardzo bolesne dla łańcuchów wyroczni, ponieważ odzwierciedla czasowe, epistemiczne ograniczenie śladu interakcji, a definicja taśm wyroczni wymaga dostarczenia całego łańcucha z przodu.

Podejrzewam, że uzyskanie tego prawa jest wykonalne i zasadniczo sprowadza się do (1) rozważenia ciągów wyroczni nie jako zbioru, ale jako przestrzeni topologicznej, której otwarte zbiory kodują logikę modalną czasu i wiedzy, którą chcesz modelować, oraz (2) zapewnienie że wszystkie twierdzenia, które udowodnisz, są ciągłe w odniesieniu do tej topologii, postrzegając predykaty jako ciągłe funkcje od ciągów wyroczni po wartości prawdy postrzegane jako przestrzeń Sierpińskiego. Powinienem podkreślić, że jest to przypuszczenie oparte na analogii z teorią domen. Trzeba by dopracować szczegóły (i prawdopodobnie przesłać je do LICS lub czegoś takiego), aby się upewnić.

W rezultacie ludzie wolą modelować interakcję za pomocą takich rzeczy jak model Dolev-Yao , w którym wyraźnie modelujesz interakcję między komputerami a środowiskiem, abyś mógł wyraźnie scharakteryzować to, co wie atakujący. Ułatwia to sformułowanie odpowiedniej logiki modalnej dla uzasadnienia bezpieczeństwa, ponieważ stan systemu plus stan środowiska są wyraźnie przedstawione.

czytając blog Lance Fortnows, właśnie natknąłem się na ten najnowszy / miły / długi artykuł ankietowy na temat subj z wieloma perspektywami i referencjami [1] (który nie był dotychczas cytowany), zawiera perspektywę Wegnera / Goldina (między innymi). Cudownie cytuję doskonałe Fortnows / wyraźne streszczenie / deklarację / stwierdzenie o prawie oficjalnej / jednolitej / jednomyślnej linii partii TCS:

„Kilku informatyków próbuje jednak argumentować, że teza [Church-Turing] nie uchwyciła niektórych aspektów obliczeń. Niektóre z nich zostały opublikowane w prestiżowych miejscach, takich jak Science, Communications of the ACM, a teraz jako cała seria artykuły w ACM Ubiquity. Niektórzy ludzie spoza informatyki mogą myśleć, że istnieje poważna debata na temat natury obliczeń. Nie ma. ”

[1] Turings Titanic Machine autorstwa Barry S Cooper CACM tom 55

Zgadzam się z uwagami Aaronsona.

Nie rozumiem pracy Milnera. (np. rachunek pi, który Milner wynalazł w celu opisania procesów komunikacyjnych). Jest to dla mnie dość nieczytelne, podobnie jak prawie wszystkie prace matematyczne i logiczne, takie jak teorie Lambka. Nie mam wątpliwości, że pomysły Lambka są bardzo dobre, ale chciałbym, aby przetłumaczono je na jakiś pidgin angielski, który mogę przeczytać.

Komentarz Milnera rzuca mnie, że rachunek lambda nadaje się do „procesów sekwencyjnych”, ale do komunikacji procesów potrzebne jest coś więcej.

Mój (być może naiwny) punkt widzenia był taki, że nie może tak być, ponieważ rachunek pi jest zakończony metodą Turinga, a zatem może zostać przekształcony mechanicznie w inny zapis Turinga pełny, tj. Rachunek lambda. Dlatego notacja pi-rachunku Milnera może być automatycznie konwertowana na rachunek lambda.

Wygląda na to, że zidentyfikowałem projekt: intuicyjnie powinna istnieć możliwość mechanicznej konwersji z jednego kompletnego języka Turinga na inny. czy istnieje algorytm, aby to zrobić? Będę musiał spojrzeć na Google. Może jest to niezwykle trudne i tak trudne, jak problem zatrzymania.

Wczoraj szukałem w sieci i znalazłem dokumenty na temat modeli rachunku lambda. Zaskoczyło mnie stwierdzenie, że jest to bardzo głęboka nora królika.

Richard Mullins

Po dodaniu (czystej) interaktywności formalność wychodzi poza okno. To już nie jest „zamknięty” system. Pytanie zatem brzmi: jakie jest pojęcie obliczeń po wejściu interaktywności? Ta odpowiedź: cóż, albo inny użytkownik / maszyna zastępuje część twoich obliczeń (które mogą być zapisane przez inną, większą, maszynę stanową), albo nie jesteś już w systemie definiowanym formalnie i grasz teraz gra , w takim przypadku nie ma zastosowania w Hipoteza Churcha-Turinga.

przeglądając gazetę Wegnera, jasne jest, że jest trochę melodramatyczny i przekorny, ale ma rację. Przyszłość informatyki jest prawdopodobnie znacznie bardziej skoncentrowana na robotyce , sztucznej inteligencji lub analizie danych (ogromnych „dużych danych” w prawdziwym świecie), o których nie wydaje się, by wspominał po imieniu, ale do których wyraźnie nawiązuje do swojego modelu. i obszary te w dużej mierze koncentrują się na wszechświecie poza wejściami i wyjściami TM.

historycznie nosiła również nazwę cybernetyka, zgodnie z wynalazkiem / sformułowaniem Weinera. celem robotyki jest to, że wejścia i wyjścia są nie tylko cyfrowe i pozbawione znaczenia, co można by zakończyć patrząc na TM; są, ale mają rzeczywiste implikacje / skutki / przyczyny itp., a maszyna tworzy pętlę sprzężenia zwrotnego z otoczeniem.

dlatego twierdzę, że TM i robotyka tworzą bardzo naturalną synergię lub symbiotyczną relację. ale nie jest to radykalne twierdzenie, a to, co Wegner ogłasza z wielką fanfarą, jest sformułowane inaczej, nie jest zbyt kontrowersyjne ani nowatorskie. innymi słowy, Wegner wydaje się być celowym intelektualistą lub akademickim ikonoblastem w swoim stylu celowo ... a więc kim jest społeczność TCS, która odmawia mu tego melodramatycznego kadrowania? niemniej patrz [2] na poważne obalenie.

Przykład prowadzenia samochodu przez Wegnera jest bardzo trafny i można wymienić inne kluczowe przemyślenia w TCS :

• wyzwanie wyścigu drogowego DARPA, a także zbliżanie się Google'a do technologii prowadzenia samochodu. [3]
• przypadek zwycięstwa Big Blue AI nad Kasparowem
• ostatnie zwycięstwo w Deep Blue Jeopardy Challenge
• coraz bardziej autonomiczny łazik marsjański
• niedawno ogłoszony przełom w rozpoznawaniu obiektów bez nadzoru przez Google. [4]
• komercyjne rozpoznawanie mowy

ale to prawda, co zaczęło się kilkadziesiąt lat temu, gdy sama teoria z TM jest obecnie zjawiskiem bardzo realnym, a segmenty społeczności TCS z wieży z kości słoniowej mogą być w pewnym oporze, a nawet zaprzeczać temu faktowi i związanej z nim, fundamentalnej [w pobliżu Kuhnian ] transformacja i przesunięcie „aktualnie w grze”. jest to nieco ironiczne, ponieważ Turing był bardzo stosowany w wielu jego perspektywach i badaniach, takich jak jego zainteresowanie operacyjnym testem AI (test Turinga), dynamika chemiczna, obliczenia rozwiązywania szachów itp. [5].

można to nawet zobaczyć w mikrokosmosie na tej stronie w sporze o to, jak zdefiniować zakres i gorących spórach o to, czy określony z pozoru nieszkodliwy tag zwany zastosowaniem teorii jest uzasadniony [7].

i zauważmy, że TCS faktycznie studiuje wiele interaktywnych modeli obliczeń i wiele kluczowych badań jest w tej dziedzinie ... szczególnie interaktywne systemy dowodowe, których wszystkie ważne klasy obliczeniowe można zdefiniować w kategoriach. [6]

[1] Teza Kościoła-Turinga - przełamywanie mitu przez Goldina i Wegnera

[2] Czy istnieją nowe modele obliczeń? odpowiedź dla Goldina i Wegnera autorstwa Cockshott i Michaelson

[3] Samojezdne samochody Googlesa - zalogowano 300 000 mil, ani jednego wypadku pod kontrolą komputera, Atlantyku

[4] Google bez nadzoru obiektu rozpoznaje obrazy z YouTube

[5] Wkład Alana Turingsa w CS

[6] Krajobraz interaktywnych systemów dowodowych

[7] W sprawie zmiany naszego zakresu - propozycja