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

17

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?

Dave Clarke
źródło
1
Czy masz odniesienie do uwzględnienia w swoim pytaniu? Znam formalną definicję Maszyny Turinga, ale nie wiem dokładnie, co rozumiesz przez „interakcję”.
Janoma
Wydaje się również, że „nie można poradzić sobie z interakcją ze środowiskiem” jest podobne do „nie może poradzić sobie z prawdziwą przypadkowością”, co może być prawdą, ale oba z nich można dość dobrze aproksymować za pomocą czujników i pseudolosowości. Ale to jest niedoinformowany komentarz, nie znający definicji interakcji.
Janoma
2
Maszyny Turinga nie mają czujników.
Dave Clarke
1
Jestem tego świadomy. A jednak, komputery zrobić czujniki stosowania, które są szczególnym sposobem przekazywania wejście do maszyny Turinga. Więc TM zrobić interakcji z zewnętrznych sygnałów / środowiska jakoś.
Janoma
2
Pytanie nie dotyczy komputerów. Jedyną interakcją z bazą TM jest to, że środowisko zapewnia jeden sygnał wejściowy na początku i odbiera co najwyżej jeden wynik na końcu. To nie jest ogólna interakcja.
Dave Clarke

Odpowiedzi:

11

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.

Carl Mummert
źródło
Taśmy Oracle nie modelują poprawnie interakcji. Rozważ próbę udowodnienia, że ​​system komputerowy nie ujawnia prywatnych informacji. Nie można tego sformalizować w kategoriach TM ze stałą taśmą Oracle, ponieważ właściwość ta zależy od charakterystyki obliczeń, jakie może wykonać środowisko - dokładnie tego, co wyodrębniamy taśmą Oracle.
Neel Krishnaswami
Zależy to od tego, co rozumiesz przez „poprawnie model”. Niektóre artykuły (np. Ze społeczności hiperkomputerów) wydają się sugerować, że interakcja w jakiś sposób powiększa zestaw funkcji obliczeniowych. Co robi, dokładnie tak samo jak obliczenia w Oracle. Oczywiście nie można używać baz TM do badania właściwości rzeczywistego środowiska obliczeniowego; jeśli chcesz wiedzieć, czy procesor w komputerze jest wadliwy, nie pomoże całkowicie go zignorować i po prostu spojrzeć na maszyny Turinga. Ale w przypadku pytań dotyczących wyłącznie funkcji , która jest wyliczana, interakcja i wyrocznie są równoważne.
Carl Mummert
Nie, tak nie jest: istnieją ograniczenia ciągłości możliwych interakcji, których taśmy oracle nie modelują. Jeśli środowisko nie widzi wewnątrz programu, to dane wejściowe, które dostarcza w czasie mogą zależeć tylko od danych wyjściowych we wcześniejszych czasach n . (Oznacza to, że patrząc na dane wejściowe jako funkcję danych wyjściowych, funkcja wejściowa musi być nieekspansywna w odniesieniu do metryki Cantora.) Tak jak obliczalność „wydaje się być” topologią klasycznego matematyka, interaktywność „przypomina„ topologię konstruktywną matematycy. nn
Neel Krishnaswami
Aby naprawdę dokładnie opracować tę analogię, zobacz Peter Hancock, Pierre Hyvernat: Interfejsy programowania i podstawowa topologia. citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.107.919
Neel Krishnaswami
1
Dane wejściowe, które operator wprowadza w czasie mogą być dowolnymi wejściami, a zatem zbiór wszystkich możliwych przebiegów wejściowych zawiera wszystkie nieskończone sekwencje elementów wejściowych. Nie ma tam ciągłości, ponieważ operator może wprowadzić wszystko. Wykonalności (który biorę oznaczać złożoności obliczeniowej) nie ma znaczenia dla kwestii jestem sekretarką - każdy funkcja może być wyliczana przez maszynę oracle, jeśli funkcja ta jest podana na taśmie Oracle i podobnie dowolnymn funkcja może być obliczona przez interakcję maszyna, jeśli operator jest przygotowany do wprowadzenia dowolnych wartości funkcji na żądanie.
Carl Mummert
8

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.

Ben
źródło
8

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.

Mohammad Al-Turkistany
źródło
6

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.

Raphael
źródło
Zatem maszyny Turinga z Wyroczniami są potężniejsze niż Maszyny Turinga bez nich i Maszyny Turinga z Wyroczniami mogą modelować interakcje. Tak więc odpowiedź wydaje się twierdząca.
Dave Clarke
1
@DaveClarke Jeśli uważasz za doskonałe wyrocznie, tak.
Raphael
2
Myślę, że nieautoryzowana (przez jakąkolwiek formę wyroczni lub wejścia) maszyna (lub program) mogłaby w zasadzie znaleźć każdy dowód. Istnieją dwa problemy: (1, teoretyczny): nigdy nie będzie w stanie stwierdzić, że wypowiedź nie ma dowodu, i (2, praktyczne): ślepe generowanie dowodów w nadziei natknięcia się na dane oświadczenie jest tak okropnie nieefektywne, że nikt nie chce spróbować, a więc asystenci ds. dowodu wolą przeszukiwanie z przewodnikiem, rezygnując z „zapewnionego” sukcesu na wypadek, gdyby dowód istniał.
Marc van Leeuwen,
2
Jak Ben wskazuje w swojej odpowiedzi, właściwym sposobem patrzenia na to nie jest: „Maszyny Turinga z wyroczniami są mocniejsze”; same maszyny robią tylko obliczalne rzeczy. Właściwy sposób spojrzenia na to brzmi: „niektóre wyrocznie nie są obliczalne, a więc z tych wyroczni możemy obliczyć rzeczy, których nie moglibyśmy obliczyć bez wyroczni”. Siła obliczeniowa pochodzi z wyroczni, a nie z maszyny.
Carl Mummert
Wydaje się, że maszyny Turinga z Wyroczniami są najpotężniejsze. Po co zawracać sobie głowę nowymi definicjami?
saadtaame