Czy interakcja ma większą moc niż algorytmy?

Słyszałem motto oddziaływanie jest silniejsze niż algorytmów z Peterem Wegner . Podstawą tego pomysłu jest to, że (klasyczna) Maszyna Turinga nie jest w stanie poradzić sobie z interakcją, to znaczy komunikacją (wejście / wyjście) ze światem zewnętrznym / środowiskiem.

Jak to może być tak? Jak coś może być mocniejsze niż maszyna Turinga? Jaka jest istota tej historii? Dlaczego nie jest bardziej znany?

Maszyny Turinga radzą sobie dobrze z interakcją, używając taśm oracle. Działa to następująco: z punktu widzenia komputera, który obsługuje interakcję, dane wejściowe operatora są po prostu kolejną sekwencją bitów wysyłanych od czasu do czasu do komputera. Wszyscy wiemy, że leniwy sysadmin może napisać skrypt, aby wysłać dane wejściowe do programu, gdy zostanie o to poproszony, aby sysadmin mógł wcześniej przerwać. Maszyna interakcji nie ma sposobu, aby dowiedzieć się, czy na konsoli rzeczywiście znajduje się operator działający na żywo lub czy dane wejściowe są przesyłane strumieniowo z innego programu.

Przygotowanie wszystkich danych wejściowych do interakcji z wyprzedzeniem jest takie samo, pod względem teoretycznym, jak posiadanie wszystkich danych wejściowych na osobnej taśmie, z której korzysta wyrocznia Turinga. Ilekroć komputer zwykle prosi operatora o interakcję, urządzenie zamiast tego czyta z taśmy wejściowej. Jeśli rzecz odczytana z taśmy wydaje się w jakiś sposób nieważna, maszyna Turinga robi dokładnie to, co zrobiłaby maszyna interakcji po otrzymaniu tego wejścia.

Sądzę, że Wagner zdaje sobie sprawę z możliwości używania taśm oracle do wprowadzania kodu, więc musisz wziąć jego komentarze z odrobiną soli, albo musisz zapytać, co on właściwie znaczy. Uważam, że ludzie, którzy myślą o interakcji, ogólnie martwią się o dwie rzeczy:

• „Prawdziwe” komputery mają interakcje, ale algorytmy zdefiniowane przez Turinga nie. Możemy sobie z tym poradzić, kodując dane wejściowe na taśmach Oracle, ale nadal nie odpowiada to działaniu prawdziwych komputerów. Przydałoby się badanie modeli obliczeniowych, które są ściślej dopasowane do rzeczywistych komputerów.

• Algorytmy oparte na Oracle nie są często brane pod uwagę w codziennych obliczeniach, ponieważ normalne komputery nie mają magicznej „wyroczni” do dostarczania danych. Ale możemy być w stanie po prostu użyć osoby jako wyroczni. Jeśli osoba rozumie żądane dane, może nawet być w stanie pomóc algorytmowi, zwiększając w ten sposób jego wydajność. Innymi słowy, człowiek może być w stanie zapewnić przydatną taśmę Oracle, a nie tylko przypadkową, i w zasadzie może to prowadzić do szybszych lub bardziej wydajnych metod obliczeniowych w porównaniu do metod nie opartych na Oracle. Podobna rzecz dzieje się w przypadku obliczeń losowych, gdy maszyna otrzymuje sekwencję losowych bitów jako dodatkowe dane wejściowe.

Obliczanie modelu maszyn tokarskich i brak koncepcji interakcji. W tym sensie maszyna obsługująca interakcję z systemem zewnętrznym może robić rzeczy, których nie potrafi Tokarka. Ale obliczenia dokonane między bitem danych wejściowych ze źródła zewnętrznego mogą oczywiście zawsze być modelowane przez maszynę Turinga, więc nawet „maszyna IO” nie może zrobić nic z zewnętrznym wejściem, czego maszyna Turinga nie mogłaby zrobić.

W pewnym sensie taka maszyna może być w stanie „decydować” o problemach nierozstrzygalnych przez Maszyny Turinga, ale tylko jeśli wyobrażasz sobie, że system, z którym współpracuje, ma moc Super-Turinga i jest niezawodny (w pewien sposób; niezawodność probabilistyczna powinno wystarczyć).

Wyobraź sobie program dla maszyny IO, taki jak: „dla dowolnego początkowego wejścia na taśmę wydrukuj zawartość taśmy, a następnie odczytaj symbol z zewnętrznego wejścia; zaakceptuj, jeśli symbolem jest 1, i odrzucaj inaczej”. Ten program może rozwiązać każdy problem. Ale tylko wtedy, gdy system zewnętrzny, z którym może współpracować, jest w stanie rozstrzygnąć problem; dla mnie nie jest to zbyt interesujący sposób powiedzenia, że ​​Maszyna IO jest w stanie decydować o problemach nierozstrzygalnych przez Turing Machines.

Myślę, że zawsze byłoby możliwe przedstawienie interaktywnego obliczenia, wyobrażając sobie maszynę, która pobiera jako dane wejściowe na taśmie kodowanie niektórych wcześniejszych konfiguracji wraz z zewnętrznym wejściem i każe maszynie zatrzymać się na taśmie zawierającej kodowanie konfiguracji razem z wyjściem. Następnie proces „uruchamiania programu” wielokrotnie uruchamia tę maszynę Turinga w sposób mechaniczny, przy czym jedyną „niemechaniczną” częścią jest jednak źródło zewnętrzne. Jestem pewien, że możesz udowodnić, że jeśli taki system uzyskałby swój wkład, przekazując go innej maszynie Turingaskonfigurowany do działania w podobny sposób, wówczas połączony system ma identyczne moc obliczeniowe jak pojedyncza Maszyna Turinga. Uważam, że przekonujący argument, że obliczenia interaktywne nie są potężniejsze niż obliczenia nieinteraktywne, chyba że system, z którym te obliczenia oddziałują, jest potężniejszy niż Maszyna Turinga .

Istnieje jednak teoretyczny sens, w którym interaktywność może zwiększyć zdolność komputera do rozwiązywania problemów. Istnieje wiele rzeczy, które ludzie robią bardzo dokładnie, i nie wiemy, jak sprawić, by komputery działały bardzo dobrze. Ale jest też wiele rzeczy, w których ludzie są śmieciami, na które możemy zmusić komputery. Połączenie tych dwóch elementów może prowadzić do takich projektów, jak reCaptcha , która skutecznie automatycznie digitalizuje książki poprzez rozwiązywanie problemów rozpoznawania słów w trudnych przypadkach. Powstały system pracy komputerowej + ludzkiej osiąga wynik, który jest obecnie niepraktyczny do osiągnięcia przy pomocy samego obliczenia lub samej pracy ludzkiej.

Ostatnio ACM zorganizowało sympozjum Ubiquity „ Czym jest obliczenie? „w którym Peter Wegner opublikował artykuł odzwierciedlający jego poglądy na temat komputerów interaktywnych.

Oto dwa fragmenty artykułu Petera Wegnera:

Jedną z nowych koncepcji, której brakowało we wczesnych maszynach Turinga, jest „Interactive Computing”, który uwzględnia interakcję ze środowiskiem podczas obliczeń.

Maszyny interakcji mogą wykonywać bardziej wydajne formy obliczeniowe niż maszyny Turinga i mogą wykonywać takie myślenie, jakie proponuje Turing, ponieważ interakcja poprawia ich wydajność w porównaniu z maszynami Turinga.

Jednak Fortnow, który ma artykuł na tym samym sympozjum, wydaje się nie zgadzać z poglądami Wegnera i uważa, że ​​interaktywne obliczenia nie oferują żadnej dodatkowej mocy nad maszynami Turinga.

Aby dodać do miksu, wydaje się, że wciąż debatujemy i definiujemy obliczenia. Mosze Vardi ma artykuł: Co to jest algorytm ?, Komunikacja ACM, t. 55, nr 3, marzec 2012 r.

Vardi informuje o dwóch nowych definicjach algorytmów. Pierwszy jest proponowany przez Gurewicza, a drugi przez Moschovakisa.

Gurevich argumentował, że każdy algorytm można zdefiniować w kategoriach abstrakcyjnej maszyny stanu.

Moschovakis argumentował natomiast, że algorytm jest zdefiniowany w kategoriach rekursora, który jest rekurencyjnym opisem zbudowanym na podstawie arbitralnych operacji traktowanych jako prymitywy.

Nie sądzę, że modele z IO są „mocniejsze” niż maszyny Turinga, po prostu modelują różne rzeczy.

Teoretycznie można postrzegać IO jako (hałaśliwą?) Wyrocznię. Dzięki doskonałej wyroczni możesz komputerowo obliczać funkcje Turinga; ale skąd wziąć wyrocznię? Ludzie są jedynym wyborem „super-Turinga” (jeśli istnieje) i wiadomo, że jesteśmy bardzo niewiarygodni.

Klasą programów pasujących do tego modelu są interaktywne asystujące proofy (np. Isabelle / HOL , Coq ). Mają do czynienia z nierozstrzygalnymi spacjami, ale (prawdopodobnie) każdy dowód można znaleźć (i sprawdzić) z odpowiednim wkładem użytkownika.

Sprawdź to :) „ Pomysły Turinga i modele obliczeń ” https://www.cs.montana.edu/~elser/turing%20papers/Turing%27s%20Ideas%20and%20Models%20of%20Computation.pdf