Warum können Menschen bestimmte „unentscheidbare“ Probleme lösen?

Musteranpassung höherer Ordnung ist ein unentscheidbares Problem. Das heißt es gibt keinen Algorithmus, der eine Gleichung gegeben a => b, wo aund bsind offen Begriffe auf dem einfach Lambda - Kalkül eingegeben hat , findet eine Substitution , Sso daß aS => bS, wo =>steht für „die gleiche Bn Normalform“. Der Mensch kann dieses Problem jedoch effizient lösen. Zum Beispiel mit dem folgenden 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))))))

Jeder Mensch mit ausreichendem Wissen über die Lambda-Rechnung wird bemerken können, dass Fdie "doppelte" Funktion für Kirchenzahlen schnell mit der Lösung kommt, die

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

Meine Frage ist: Wenn dieses Problem unentscheidbar ist, wie kann es der Mensch schnell und mühelos lösen?

computability MaiaVictor
quelle

"Menschen können dieses Problem effizient lösen" - Zitat erforderlich. Was ist Ihr Beweis dafür? Das Anzeigen eines Beispiels, in dem Sie es effizient lösen können, bedeutet nicht, dass Sie es für alle Instanzen des Problems effizient lösen können. Sie können "X ist wahr, für alle X" nicht beweisen, indem Sie ein Beispiel für X zeigen, in dem X wahr ist.

Ein Problem ist unentscheidbar bedeutet, dass es keinen Algorithmus gibt, der für jede Instanz des Problems richtig mit "Ja" oder "Nein" antwortet . Es bedeutet nicht, dass man einen Algorithmus finden kann, der einige (oder viele) Fälle des Problems löst. [Heh. Wie DW antwortete, während ich diese Bemerkung verfasste.]

Rick Decker

Löse dieses Problem? Ich verstehe dieses Problem nicht einmal .

MikeTheLiar

So habe ich es verstanden: Diese Lösung ist eine Ad-hoc-Lösung. Jede Instanz des Problems hat eine - in den meisten Fällen nicht so leicht zu motivieren wie in Ihrem Beispiel, aber Sie können immer sagen: "Wenn Sie Instanz X erhalten, geben Sie Y aus", da ein Algorithmus nur auf der Grundlage der Korrektheit beurteilt werden kann. Das Hardcodieren aller solcher Lösungen auf diese Weise führt jedoch nicht zu einer endlichen Prozedur (was die einzig vernünftige Art ist und daher normalerweise gemeint ist). Alternativ gesagt, damit ein Problem entschieden werden kann, dürfen Sie nicht sehen, welche Instanz angegeben ist, bevor Sie die Strategie des Algorithmus auswählen.

Vandermonde

Dies ist auch der Grund, warum im Allgemeinen nur Probleme mit einer unendlichen Anzahl von Instanzen in Betracht gezogen oder als solche bezeichnet werden, da Sie ansonsten einfach alle Lösungen wie oben aufgeführt haben könnten.

Vandermonde

Antworten:

Menschen können einige Fälle dieses Problems effizient lösen , aber es gibt keinen Grund zu der Annahme, dass Menschen alle Fälle effizient lösen können . Das Anzeigen einer Instanz, die ein Mensch effizient lösen kann, bedeutet nicht, dass der Mensch alle Instanzen effizient lösen kann.

Unentscheidbar bedeutet "Es gibt keinen Algorithmus, der alle Instanzen lösen kann und der immer endet". Es könnte immer noch einen Algorithmus geben, der einige Fälle auch für ein unentscheidbares Problem lösen kann .

Es gibt also keinen Widerspruch.

DW
quelle

@srvm, yup, das bedeutet es doch. Hier ist zum Beispiel ein dummes Beispiel für einen Computeralgorithmus: "Wenn die Eingabe genau dem in Ihrer Frage angegebenen Beispiel entspricht, geben Sie sie aus F = (λ a b c . (a b (a b c)))und halten Sie an". Dies ist ein Computeralgorithmus, der das Problem in einigen Fällen (insbesondere in genau einem Fall) löst. Ja, das ist in Ordnung - so eine neue Frage zu stellen, scheint das Richtige zu sein. Wie üblich, teilen Sie uns bitte mit, welche Nachforschungen Sie in der Frage angestellt haben (bevor Sie fragen, sollten Sie einige Nachforschungen anstellen).

Wo die wirklich harten Probleme sind Behauptungen, dass selbst in NP vollständige Probleme die meisten Fälle leicht gelöst werden können. Dies entspricht meiner Erfahrung. Normalerweise gibt es Merkmale des Problems, die die Lösung (zumindest teilweise) offensichtlich machen. Die harten werden sorgfältig zwischen Erfolg und Misserfolg abgewogen, aber es gibt nicht viele davon.

Ross Millikan

@srvm Wenn du darüber nachdenkst, ist es genau das, was ein Optimierer tun muss, um schwierige Probleme wie diese in besonderen Fällen zu lösen .

Cort Ammon

@srvm: Ein hervorragendes Beispiel für ein unentscheidbares Problem, das Computer fast täglich lösen müssen, ist das Problem des Stillstands. Wir wissen, dass das Problem des Anhaltens nicht entschieden werden kann, schreiben aber weiterhin Linters, statische Analysatoren und Compiler, die versuchen, unerwünschte Endlosschleifen zu erkennen. Wie wir das machen, ist eine Faustregel. Das heißt, wir wissen aus menschlicher Erfahrung (nicht Algorithmus), dass bestimmte Arten von Code in die Endlosschleife eintreten. Deshalb bitten wir den Computer, nach den uns bekannten Fällen zu suchen. Wir wissen, dass solche Programme niemals alle Fehler abfangen werden. Aber es ist besser als nichts.

Slebetman

Für die Nachwelt ein neuer Link zu: Wo die wirklich schweren Probleme sind

Alex Moore-Niemi

Wie einer der Kommentare festhält, sollte man sich darüber im Klaren sein, dass es in der Praxis einige ziemlich gute Algorithmen zum Lösen von Mustern höherer Ordnung gibt (wie eine schnelle Google-Suche zeigen wird).

Ich kenne keine, die dieses spezielle Problem lösen, aber dieses "Verdopplungs" -Problem kommt dem Bereich der Programmsynthese näher . Ich glaube, dass es Programmsynthesesysteme gibt, die diese Art von Problem lösen können.

Es ist einfach, Beispiele zu erstellen, die diese Systemdrosseln verursachen, und es scheint, dass Menschen bei solchen Problemen besonders gut sind. Die Schaffung von Algorithmen, die den Menschen bei der Lösung derartiger Probleme näher kommen, ist das Ziel der automatischen Beweisführung und der künstlichen Intelligenz (für ehrgeizigere / unrealistischere Versuche).

Cody
quelle

Menschen versuchen immer, das Problem mit ihrem eigenen Wissen zu lösen, also entwickeln Menschen einen Algorithmus, um das Problem mit einigen Problemfällen zu lösen. So entwickeln Menschen einen Algorithmus, aber es gibt keine Gewissheit, dass der bestimmte Algorithmus jedes einzelne Problem lösen kann. Kein Algorithmus kann also jedes Problem lösen, aber es gibt immer noch ein Problem, das vom Menschen gelöst werden kann, obwohl es keinen perfekten Algorithmus dafür gibt, wie wir sagen können, dass wir wissen, wie man ein Problem löst, aber keinen Algorithmus haben .

quelle

Ist das nicht nur eine Umschreibung der bestehenden Antwort? Ich weiß, dass ich die meisten Ihrer Antworten kritisiert habe, so dass das Folgende unaufrichtig klingen mag, aber es ist nicht so. Es ist wirklich toll, dass Sie einen Beitrag zur Website leisten möchten. Es wäre wirklich großartig, wenn Sie uns helfen könnten, einige unserer 2500 unbeantworteten Fragen zu beantworten , anstatt Fragen, auf die wir bereits eine Antwort haben, die alles sagt, was Sie sagen möchten. Vielen Dank!

David Richerby