(False?) Beweis für Berechenbarkeit einer Funktion?

19

Betrachten , eine Funktion , die 1 zurückkehrt iff Nullen erscheinen nacheinander in . Jetzt gab mir jemand einen Beweis, dass berechenbar ist: $f(n)$ $n$ $\pi$ $f(n)$

Entweder für alle n, erscheint in , oder es ist am st erscheint in und nicht. Für die erste Möglichkeit ; Für das zweite iff , sonst 0. $0^n$ $\pi$ $0^m$ $\pi$ $0^{m+1}$ $f(n) := 1$ $f(n) := 1$ $n \leq m$

Der Autor behauptet, dies beweise die Berechenbarkeit von , da es einen Algorithmus zu seiner Berechnung gibt. $f(n)$

Ist dieser Beweis richtig?

computability Mike B.
quelle

2

Sie können Latex in Ihren Fragen verwenden, um sie besser lesbar zu machen.

Dave Clarke

7

Das Argument ist richtig, aber nicht konstruktiv. Die Person gibt Ihnen kein TM, er gibt Ihnen zwei TMs und sagt Ihnen , dass einer von ihnen ist die Berechnung der Funktion , die Sie wollen, aber nicht wissen , welche.

Kaveh

1

Ihre Version ist berechenbar. Ich habe jedoch aus Versehen eine Version falsch gelesen und festgestellt, die meines Erachtens nicht berechenbar ist. Die einzige Änderung: Statt genau n Nullen fragen Sie, ob π höchstens n Nullen hat. Wenn dies wirklich der Fall ist, können Sie es meines Erachtens nicht bestätigen, da π eine unendliche Anzahl von Ziffern hat und (anscheinend?) Kein Muster erneut auftritt.

chazisop

Ich habe einmal eine Wikipedia-Seite korrigiert, die einen ähnlichen Fehler gemacht hat. Dabei habe ich behauptet, dass die Existenz von Chaitins Konstante die Existenz von "nicht berechenbaren ganzen Zahlen" bewiesen hat.

Geoffrey Irving

Fragen dieser Art beziehen sich in der Regel auf "Trivialsprachen". Beachten Sie jedoch, wie gewöhnlich eine leichte Neuformulierung, z. B. wenn die Sprache wobei eine (oder die erste) Stelle der Zeichenfolge oder -1, wenn es keine solche Zeichenfolge gibt, unentscheidbar sein kann. siehe auch wie kann es entscheidbar sein, dass eine Ziffernfolge hat? / Informatik

f (n, k) = m

$f(n, k) = m$

m

$m$

0^{k}

$0^k$

π

$\pi$

vzn

23

Denken Sie daran , auf diese Weise, Mike: Dieser Nachweis wird „Verzweigung“ in mehr möglichen Fälle, von denen um wahr zu sein hat (das Gesetz vom ausgeschlossenen Dritten mit , dass für jeden Satz , entweder wahr ist oder wahr ist ). Am Ende jeder dieser Verzweigungen können Sie jedoch immer nachweisen, dass die Funktion berechenbar ist. Daher muss berechenbar sein , egal welcher der Fälle tatsächlich im wirklichen Leben gilt . (Der genaue Grund, warum berechenbar ist, ist jedoch je nach Zweig unterschiedlich.) $p$ $p$ $\neg p$ $f$ $f$ $f$

Ryan Williams
quelle

16

Es ist korrekt. Dies ist dasselbe wie das Folgende: Definiere als die konstante Funktion wenn Gott existiert, und wenn Gott nicht existiert. Die resultierende Funktion ist eine konstante Funktion, also berechenbar. Möglicherweise können Sie diese Funktion nicht angeben, aber die Funktion selbst ist berechenbar. $f(x)$ $x \mapsto 0$ $x \mapsto 1$

Hier ist eine der beiden Möglichkeiten wahr: Entweder existiert ein solches , oder es existiert nicht. Die Funktion ist entweder die konstante Funktion oder eine einfache Schwellenfunktion, die mit definiert ist . $m$ $x \mapsto 1$ $m$

Michaël Cadilhac
quelle

4

P \neq N P

$P \neq NP$

m

$m$

5

Es ist nicht wirklich Sinn zu reden darüber , ob eine ganze Zahl ist berechenbar oder nicht. Was auch immer Wert m nimmt, gibt es eine Turing - Maschine , dass gibt es aus . Findet es könnte schwierig natürlich sein, aber das ist nicht so verschieden von der allgemeinen Situation: Findungsalgorithmen hart ist, was die Tatsache ist , dass viele von uns hält beschäftigt.

Aaron Roth

0^{m}

$0^m$

π

$\pi$

0^{m + 1}

$0^{m+1}$

m

$m$

m

$m$

m

$m$

0

$0$

14

Ich denke - und Hoffnung -, dass jeder Informatik-Student mit diesem Problem konfrontiert wird, die wie ein Paradoxon fühlt. Es ist ein sehr gutes Beispiel für den Unterschied der berechenbaren in TCS Sinne und berechenbar im praktischen Sinne.

$\pi$ $\pi$

$f$ $\exists M \in TM : f_M = f$

Die Grundidee des Beweises ist: Ich gebe Ihnen eine unendliche Klasse von Funktionen, die alle berechenbar sind (zu zeigen; hier trivial). Ich beweise dann, dass die Funktion, nach der Sie suchen, in dieser Klasse ist (um zu zeigen, Fallunterscheidung hier). qed

Raphael
quelle

9

Ja, das ist richtig, seine berechenbar. Das Problem ist, dass Ihre Funktion nicht wirklich die Lösung für eine unendliche Familie von Problemen liefert, wie es beispielsweise bei einer Funktion der Fall ist, die eine Lösung für das Halteproblem berechnet. Es gibt also kein Problem mit der Berechnung. Stattdessen repräsentieren Sie in Funktionsform eine einzelne mathematische Tatsache mit endlicher Repräsentation - entweder eine ganze Zahl oder die Tatsache, dass f die konstant 1-Funktion ist

$\Omega$

Natürlich könnte es schwierig sein, den richtigen Algorithmus zu finden. Richtige Algorithmen zu finden ist jedoch normalerweise schwierig!

Aaron Roth
quelle

3

post ein bisschen alt, wollte aber eine andere antwort posten.

Dies ist ein nicht-konstruktiver Nachweis (oder Argument) der Berechenbarkeit. Er sagt einfach , dass die Funktion in einem gewissen Sinne existieren muss , da ich es (oder richtiger indiziert) darstellen kann, in der Menge (oder Universum) der berechenbaren Funktionen. Es erstellt jedoch weder die Maschine selbst (dh den Algorithmus) noch den Index (unter der Annahme einer effektiven Aufzählung berechenbarer Maschinen). Der Englisch Begriff „ Danke für nichts “, scheint in diesen Fällen am besten geeignet, wie die folgenden:

-- Look, I proved there is water somewhere! 

Now you can be happy, while dying from thirst!

Menschen in der Geschichte der Mathematik haben sich viel über die tatsächliche Gültigkeit (oder den Gültigkeitsbereich) und die Bedeutung solcher Argumente gestritten. Das Endergebnis ist , dass die gleiche Art von Argumenten in den Unvollständigkeitssätze von Gödel wieder erscheinen und sich gegen diese „geschlossene Universum Annahme“ .

Wenn Ihnen diese Argumente nicht so gut gefallen, würde ich Ihnen keine Vorwürfe machen.

Nikos M.
quelle

(False?) Beweis für Berechenbarkeit einer Funktion?

Antworten: