Effektive Methode - Effective method

In der Logik , Mathematik und Informatik , insbesondere der Metalogik und der Berechenbarkeitstheorie , ist eine effektive Methode oder ein effektives Verfahren ein Verfahren zur Lösung eines Problems aus einer bestimmten Klasse. Eine wirksame Methode wird manchmal auch als mechanische Methode oder Verfahren bezeichnet.

Definition

Die Definition einer effektiven Methode umfasst mehr als die Methode selbst. Damit eine Methode als effektiv bezeichnet werden kann, muss sie in Bezug auf eine Klasse von Problemen betrachtet werden. Aus diesem Grund kann ein Verfahren in Bezug auf eine Klasse von Problemen effektiv sein und in Bezug auf eine andere Klasse nicht effektiv sein.

Eine Methode wird formal als effektiv für eine Klasse von Problemen bezeichnet, wenn sie die folgenden Kriterien erfüllt:

  • Es besteht aus einer endlichen Anzahl von genauen, endlichen Anweisungen.
  • Wenn es auf ein Problem aus seiner Klasse angewendet wird:
    • Es endet immer ( beendet ) nach einer endlichen Anzahl von Schritten.
    • Es liefert immer eine richtige Antwort.
  • Im Prinzip kann dies von einem Menschen ohne Hilfsmittel außer Schreibmaterial durchgeführt werden.
  • Seine Anweisungen müssen nur rigoros befolgt werden, um erfolgreich zu sein. Mit anderen Worten, es erfordert keinen Einfallsreichtum, um erfolgreich zu sein.

Optional kann es auch erforderlich sein, dass die Methode niemals ein Ergebnis zurückgibt, als ob es eine Antwort wäre, wenn die Methode von außerhalb ihrer Klasse auf ein Problem angewendet wird . Das Hinzufügen dieser Anforderung reduziert die Menge der Klassen, für die es eine effektive Methode gibt.

Algorithmen

Eine effektive Methode zur Berechnung der Werte einer Funktion ist ein Algorithmus . Funktionen, für die eine effektive Methode existiert, werden manchmal als effektiv berechenbar bezeichnet .

Berechenbare Funktionen

Mehrere unabhängige Bemühungen um eine formale Charakterisierung der effektiven Berechenbarkeit führten zu einer Vielzahl von vorgeschlagenen Definitionen ( allgemeine Rekursion , Turing-Maschinen , λ-Kalkül ), die sich später als gleichwertig erwiesen. Der von diesen Definitionen erfasste Begriff wird als rekursive oder effektive Berechenbarkeit bezeichnet .

Die Church-Turing-These besagt, dass die beiden Begriffe zusammenfallen: Jede effektiv berechenbare zahlentheoretische Funktion ist rekursiv berechenbar . Da dies keine mathematische Aussage ist, kann sie nicht durch einen mathematischen Beweis bewiesen werden .

Siehe auch

Verweise

  • SC Kleene (1967), Mathematische Logik . Nachgedruckt, Dover, 2002, ISBN  0-486-42533-9 , S. 233 ff., insb. P. 231.