Gilt die Church-Turing-These auch für künstliche Intelligenz?

Nach Church-Turings These ist es unmöglich, einen Algorithmus zu entwerfen, um das Stoppproblem zu entscheiden.

Umfasst der Wortalgorithmus in diesem Zusammenhang künstliche Intelligenz oder nicht, dh gilt die Church-Turing-These auch für künstliche Intelligenz?

Ist es möglich, in Zukunft ein Nachrichtensystem zu entwerfen, um dieses Problem zu entscheiden, oder wird nach der These von Church-Turing keine KI in der Lage sein, das Problem des Stillstands zu entscheiden?

computability artificial-intelligence halting-problem church-turing-thesis M ama D.
quelle

Es ist unwahrscheinlich, dass ein KI-System irgendetwas entscheiden kann (im formalen, deterministischen Sinne), aber wenn es könnte, würde es sicherlich entweder gegen die Church-Turing-These oder gegen die Unentscheidbarkeit des Halting-Problems verstoßen. (Letzteres, wenn es in einer Turing-vollständigen Sprache geschrieben ist, Ersteres anders.)

Raphael

Warum halten Sie es für möglich, dass künstliche Intelligenz von der Charch-Turing-These nicht abgedeckt (oder betroffen) wird?

Babou

@babou, weil es Nichtdeterminismus, Lernen usw. beinhaltet. Es gibt nicht lösbare Probleme, bei denen AI uns eine sehr gute Annäherung an die Lösung gibt.

M ama D

@Drupalist: Die Entscheidbarkeit eines Problems bedeutet jedoch nur, dass es einen Algorithmus gibt, mit dem für jede Eingabe aus dem Eingaberaum des Problems die richtige Ausgabe erzeugt wird. Ja, ein AI-Algorithmus (oder ein anderer Algorithmus) könnte gute Annäherungen für das Stoppproblem liefern, aber dies bringt keine Entscheidbarkeit mit sich.

Roy O.

Antworten:

Die Church-Turing-These besagt, dass die informelle Vorstellung eines Algorithmus als Folge von Anweisungen mit Turing-Maschinen übereinstimmt. Entsprechend heißt es, dass jedes vernünftige Rechenmodell die gleiche Leistung wie Turing-Maschinen hat.

Eine künstliche Intelligenz ist ein Computerprogramm, dh ein Algorithmus. Wenn die Church-Turing-These zutrifft, können Sie diesen Algorithmus auf einer Turing-Maschine implementieren. Da Turing-Maschinen ihr eigenes Halteproblem nicht entscheiden können, folgt daraus, dass nach der Church-Turing-These künstliche Intelligenzen das Halteproblem für Turing-Maschinen nicht entscheiden können.

David Richerby
quelle

Wenn andererseits die KI auf einem analogen Computer oder einer ungleichmäßigen Endlosschaltung geschrieben wurde, ist das Halteproblem für Turing-Maschinen wieder auf der Platine.

DanielV

@DanielV Eine ungleichmäßige Endlosschaltung hilft nicht. Wenn es eine berechenbare Beschreibung hat, kann es das Stoppproblem nicht lösen. Wenn es keine berechenbare Beschreibung gibt, können Sie sie nicht erstellen.

David Richerby

Sie können es nicht mit einer Turing-Maschine bauen. Das bedeutet nicht, dass es nicht paradoxer ist als 2 Punkte, die einen willkürlichen Abstand voneinander haben.

DanielV

n

$n$

@DanielV Es gibt einige Probleme, die Sie einfach nicht berechnen können. Sie müssen in der Lage sein zu entscheiden, wann Sie das Problem gelöst haben und wie die Antwort lautet. Im Fall des Halteproblems gibt es keine Möglichkeit festzustellen, ob Sie das Problem gelöst haben, geschweige denn herauszufinden, wie die Antwort lautet.

Klarer