In der Computertheorie sind die Begriffe überprüfbar und entscheidbar austauschbar? Bedeuteten sie das Gleiche?Ist nachweisbar == entscheidbar?
Zum Beispiel sieht man oft die Frage, ob etwas nachweisbar als Entscheidungsproblem bezeichnet wird (Das Entscheidungsproblem).
Diese sind unterschiedlich. Sie beziehen sich auf ganz andere Bereiche.
Entscheidbar bedeutet, dass ein Entscheidungsproblem für alle möglichen Eingaben durch eine Turing-Maschine gelöst werden kann, die "akzeptieren" oder "ablehnen" ausgibt.
Nachweisbar bedeutet, dass eine mathematische Aussage bewiesen werden kann, na ja, ein mathematischer Beweis.
In der Tat können Sie 'entscheidbar' und 'beweisbar' nicht vergleichen, da diese Attribute sich auf ganz andere Dinge beziehen.
Sie müssen beweisen, dass die Entscheidung der Maschine richtig funktioniert;) – Dario
Vielleicht eine passende Frage für mathoverflow.net? –
Ich dachte darüber nach, aber als Comp. Theorie (und Komplexität) Kurs kann auf fast allen CS \ SE Kurse gefunden werden, die ich hier für besser geeignet hielt. –