Die Church-Turing-These besagt, dass alles, was physikalisch berechnet werden kann, auf einer Turing-Maschine berechnet werden kann. Die Arbeit "Analoge Berechnung über neuronale Netze" (Siegelmannn und Sontag, Theoretical Computer Science , 131: 331–360, 1994; PDF ) behauptet, dass ein neuronales Netz einer bestimmten Form (die Einstellungen werden in der Arbeit vorgestellt) leistungsfähiger ist. Die Autoren sagen, dass ihr Modell in exponentieller Zeit Sprachen erkennen kann, die im Turing-Maschinenmodell nicht berechenbar sind.
Widerspricht das nicht der These von Church-Turing?
Um Lukes Antwort ein wenig zu erläutern , müssen zum physischen Aufbau eines neuronalen Netzes zur Lösung einer beliebigen Sprache elektronische Komponenten mit unendlich präzisen Widerständen usw. hergestellt werden. Dies ist in mehrfacher Hinsicht nicht möglich:
Sie können keinen Widerstand von genau erzeugen2Ω
Der Widerstand ändert sich mit der Temperatur, und der durch den Widerstand fließende Strom ändert seine Temperatur.
Selbst wenn Sie einen Elektroniker / Zauberer kennen, der Widerstände mit einem von Ihnen gewählten genauen Wert herstellen kann und der den Widerstand nicht mit der Temperatur ändert, sind für die Einrichtung Ihrer Maschine zur Auswahl einer nicht berechenbaren Sprache nicht berechenbare Widerstandswerte erforderlich. Sie können Ihrem Elektroniker / Zauberer also auf keinen Fall sagen, welchen Widerstandswert Sie benötigen.
Obwohl diese Maschinen im Prinzip über jede Sprache entscheiden können, verletzen sie Church-Turing nicht, weil sie nicht physisch konstruiert werden können.
Vielleicht möchten Sie sich auf ein regelkonformes Vorgehen einlassen und behaupten, jemand könnte Ihnen eine dieser Maschinen aushändigen und sagen: "Hey, schauen Sie, diese Maschine hat zufällig genau die richtigen Widerstandswerte, um das Halteproblem zu lösen!" Sie haben jedoch keine Möglichkeit, diese Behauptung zu beweisen, da sie die Komponenten nicht mit unendlicher Genauigkeit messen können. Das Beste, was sie mit Recht behaupten können, ist: "Ich habe dies an einer endlichen Menge von Eingaben getestet und das Problem des Anhaltens richtig entschieden diese Eingänge. " Nun, jede endliche Untergruppe des Halteproblems ist bereits nach Turing bestimmbar, das ist also nichts Aufregendes.
quelle