Dlaczego ludzie mogą rozwiązać niektóre „nierozstrzygalne” problemy?

Dopasowywanie wzorca wysokiego rzędu jest nierozstrzygalnym problemem. Oznacza to, że nie ma algorytmu, który, biorąc pod uwagę równanie a => b, gdzie ai bsą otwartymi terminami na prostym typie rachunku lambda, znalazłby podstawienie Stakie, że aS => bSgdzie =>skrót oznacza „ma tę samą postać normalną Bn”. Jednak ludzie mogą skutecznie rozwiązać ten problem. Na przykład biorąc pod uwagę następujący problem:

a = (λt . t 
    (F (λ f x . (f (f (f x))))) 
    (F (λ f x . (f (f x)))))
b = (λ t . t
    (λ f x . (f (f (f (f (f (f x)))))))
    (λ f x . (f (f (f (f x))))))

Każdy człowiek z wystarczającą wiedzą na temat rachunku lambda będzie w stanie zauważyć, Fże funkcja „podwójna” dla liczb kościelnych szybko pojawia się wraz z rozwiązaniem, które

 F = (λ a b c . (a b (a b c)))

Moje pytanie brzmi: jeśli ten problem jest nierozstrzygalny, jak ludzie mogą go szybko i bez wysiłku rozwiązać?

computability MaiaVictor
źródło

„ludzie mogą skutecznie rozwiązać ten problem” - potrzebne cytowanie. Jakie są na to twoje dowody? Przedstawienie jednego przykładu, w którym można go skutecznie rozwiązać, nie oznacza, że można go skutecznie rozwiązać we wszystkich przypadkach problemu. Nie możesz udowodnić, że „X jest prawdziwe, dla wszystkich X”, pokazując jeden przykład X, gdzie X jest prawdziwe.

Problem jest nierozstrzygalny oznacza, że nie ma algorytmu, który poprawnie odpowiadałby „tak” lub „nie” dla każdego wystąpienia problemu. Nie oznacza to, że można znaleźć algorytm, który rozwiązuje niektóre (lub wiele) przypadków problemu. [Heh. Jak DW odpowiedział podczas pisania tej uwagi.]

Rick Decker

Rozwiąż ten problem? Nawet nie rozumiem tego problemu.

MikeTheLiar

Zrozumiałem to tak: to rozwiązanie jest ad hoc. Każde wystąpienie problemu ma jeden - w większości przypadków nie jest tak łatwo zmotywowany jak w twoim przykładzie, ale zawsze możesz powiedzieć „jeśli dostaniesz wystąpienie X, wyjście Y”, ponieważ algorytm można ocenić tylko na podstawie poprawności - ale zakodowanie na stałe wszystkich takich rozwiązań w ten sposób nie powoduje skończonej procedury (co jest jedynym rozsądnym rodzajem, a zatem tym, co zwykle oznacza). Alternatywnie stwierdzono, że w celu rozstrzygnięcia problemu nie można zobaczyć, która instancja jest podana przed wybraniem strategii algorytmu.

Vandermonde

Także dlatego właśnie problemy z nieskończoną liczbą wystąpień są na ogół brane pod uwagę lub nazywane takimi, ponieważ w przeciwnym razie można po prostu wymienić wszystkie powyższe rozwiązania.

Vandermonde

Odpowiedzi:

Ludzie mogą skutecznie rozwiązać niektóre przypadki tego problemu, ale nie ma powodu, aby sądzić, że ludzie mogą skutecznie rozwiązać wszystkie przypadki . Pokazanie jednego wystąpienia, że człowiek może rozwiązać skutecznie, nie oznacza, że ludzie mogą rozwiązać wszystkie przypadki skutecznie.

Nierozstrzygalna oznacza „nie ma algorytmu, który mógłby rozwiązać wszystkie instancje i który zawsze się kończy”. Nadal może istnieć algorytm, który może rozwiązać niektóre przypadki , nawet w przypadku nierozstrzygalnego problemu.

Więc nie ma sprzeczności.

DW
źródło

@ srvm, tak, to znaczy, że. Oto na przykład głupi przykład algorytmu komputerowego: „jeśli dane wejściowe są dokładnie takie same, jak podane w pytaniu, to wypisz F = (λ a b c . (a b (a b c)))i zatrzymaj”. Jest to algorytm komputerowy, który rozwiązuje problem w niektórych przypadkach (w szczególności dla dokładnie 1 sprawy). Tak, to w porządku - zadawanie takich pytań wydaje się słuszne. Jak zwykle, powiedz nam, jakie badania przeprowadziłeś w pytaniu (powinieneś zrobić kilka pytań).

Tam, gdzie naprawdę trudnymi problemami są twierdzenia, że nawet w NP problemy kompletne większość przypadków można łatwo rozwiązać. To pasuje do mojego doświadczenia. Zazwyczaj są pewne cechy problemu, które sprawiają, że (przynajmniej część) rozwiązania jest oczywiste. Te twarde te są starannie wyważone między sukcesem a porażką, ale nie ma zbyt wiele osób.

Ross Millikan,

@ srvm, jeśli się nad tym zastanowić, rozwiązanie trudnych problemów w szczególnych przypadkach jest dokładnie tym, co musi zrobić optymalizator.

Cort Ammon

@srvm: Doskonałym przykładem nierozstrzygalnego problemu, który rozwiązujemy prawie codziennie, jest problem zatrzymania. Wiemy, że problem zatrzymania jest nierozstrzygalny, ale nadal piszemy lintery, analizatory statyczne i kompilatory, które próbują wykryć niepożądane nieskończone pętle. To, jak to robimy, odbywa się na zasadzie „kciuka”. Oznacza to, że z ludzkiego doświadczenia wiemy (nie algorytm), że niektóre rodzaje kodu wchodzą w nieskończoną pętlę. Dlatego prosimy komputer, aby szukał znanych nam przypadków. Wiemy, że takie programy nigdy nie wychwycą wszystkich błędów. Ale to lepsze niż nic.

slebetman

dla potomności nowy link do: Gdzie są naprawdę trudne problemy

Alex Moore-Niemi

Jak zauważa jedna z komentarzy, należy mieć świadomość, że istnieją w praktyce pewne całkiem dobre algorytmy rozwiązywania dopasowywania wzorca wyższego rzędu (jak ujawni szybkie wyszukiwanie w Google ).

Nie znam żadnego, który rozwiązałby ten konkretny problem, ale ten problem „podwajania” jest bliższy dziedzinie syntezy programów . Wierzę, że istnieją systemy syntezy programów, które mogą rozwiązać ten problem.

Łatwo jest tworzyć przykłady, które powodują, że system dławi się i wydaje się, że ludzie są szczególnie dobrzy w tego rodzaju problemach. Tworzenie algorytmów, które są bliżej ludzi w ich zdolności do rozwiązywania tego rodzaju problemów, jest zadaniem automatycznego dowodzenia twierdzeń i sztucznej inteligencji (dla bardziej ambitnych / nierealistycznych prób).

cody
źródło

Ludzie zawsze próbują rozwiązać problem z własną wiedzą, więc ludzie opracowują algorytm, aby rozwiązać problem z niektórymi przypadkami problemu. Tak więc ludzie opracowują algorytm, ale nie ma pewności, że dany algorytm może rozwiązać każdy problem. Więc żaden algorytm nie może rozwiązać każdego problemu, ale wciąż istnieje problem, który może rozwiązać człowiek, nawet jeśli nie ma idealnego algorytmu do tego, jak możemy powiedzieć, że wiemy, jak rozwiązać problem, ale nie mamy algorytmu .

źródło

Czy to nie tylko parafraza istniejącej odpowiedzi? Wiem, że skrytykowałem większość twoich odpowiedzi, więc poniższe mogą brzmieć nieszczerze, ale tak nie jest. To naprawdę wspaniałe, że chcesz przyczynić się do strony. Byłoby naprawdę wspaniale, gdybyś pomógł nam odpowiedzieć na niektóre z 2500 pytań bez odpowiedzi , zamiast pytań, na które już mamy odpowiedź, która mówi wszystko, co chcesz powiedzieć. Dzięki!

David Richerby,