Was ist der Unterschied zwischen Entscheidbarkeit und Berechenbarkeit?

Wenn sie unterschiedlich sind, was sind die typischen Probleme in jedem, die nicht in die andere Kategorie fallen? Oder schließen sich die gegenseitig aus oder erfasst das eine das andere vollständig?

computability terminology sdfasdgasg
quelle

Berechenbarkeit ist eine Eigenschaft von Funktionen, Entscheidbarkeit ist eine Eigenschaft von Sprachen (und Problemen, die sie darstellen). Ich kenne keinen anderen Unterschied als diesen.

Saadtaame

Danke ... Ich bin allerdings neugierig: Was sind einige typische Beispiele für Funktionen, die nicht berechenbar sind? Und ist eine Sprache eine endliche Menge von Zeichenfolgen? Was macht eine Sprache entscheidbar oder nicht?

SDFASDGASG

Eine erforderliche Eigenschaft eines Algorithmus ist die der Beendigung. Berechenbare Funktionen werden definiert, um diese Eigenschaft zu erfassen. Daher ist jeder Turing-Maschinenprogramm- / Funktionscomputer, der nicht bei allen Eingaben anhält, nicht berechenbar. Eine Sprache ist eine Reihe von Zeichenfolgen über einem endlichen Alphabet. Die Sprache kann unendlich sein (z. B. die Menge der Binärzeichenfolgen). Eine Sprache ist entscheidbar, wenn es eine Turing-Maschine gibt (eigentlich sollte ich Turing-Maschinenprogramm sagen), die über die Mitgliedschaft in dieser Sprache entscheidet (sagt JA, wenn die Eingabezeichenfolge in die Sprache gehört).

Saadtaame

Schreiben Sie Ihren letzten Satz: Warum kümmert sich die Turing-Maschine darum, ob die Eingabezeichenfolge Teil einer bestimmten Sprache ist (sie kann sowieso nicht alles auf einmal lesen / auswerten). Besteht nicht nur die Frage, ob das TM das Symbol lesen kann, in dem sich sein Kopf gerade befindet, und der aktuelle Status des TM?

SDFASDGASG

Auch dies ist ziemlich einfach, meistens definitiv. Sie sollten sich mehr um Ihre Fragen kümmern und genau angeben, wo Ihr Problem liegt.

Raphael

Antworten:

Eine Funktion über endlichen Zeichenfolgen wird als berechenbar bezeichnet, wenn sie von einem Programm (formal eine Turing-Maschine) berechnet werden kann.

Ein Satz endlicher Zeichenfolgen ist berechenbar, wenn es ein Mitgliedsproblem in diesem Satz gibt (gegeben $x$ ist $x \in L$ ?) kann algorithmisch entschieden werden (formeller mit einer Turing-Maschine).

Sie werden für verschiedene Arten von Objekten verwendet.

Das Wort "berechenbar" kann für eine Menge verwendet werden. Wenn wir sagen, dass eine Menge berechenbar ist, meinen wir, dass die Menge entscheidbar ist (was gleichbedeutend ist mit der Aussage, dass die charakteristische Funktion der Menge berechenbar ist).

Es macht keinen Sinn zu sagen, dass eine Funktion entscheidbar ist.

Kaveh
quelle

Im zweiten Absatz meinen Sie "entscheidbar" statt "berechenbar", nicht wahr? ("Eine Reihe endlicher Zeichenketten ist entscheidbar ...") Warum übrigens die "endliche" Einschränkung?

chs

@chs Wann würde das TM "entscheiden", wenn es unendlich wäre?

OJFord