Computability theory

Charakterisierungen von Algorithmen sind Versuche, den Begriff „Algorithmus“ zu formalisieren . Es gibt keine allgemein anerkannte formale Definition für „Algorithmus“. Forscher arbeiten aktiv an diesem Problem.

In der mathematischen Logik und Informatik ist eine allgemeine rekursive Funktion , partielle rekursive Funktion oder μ-rekursive Funktion eine partielle Funktion von natürlichen Zahlen in natürliche Zahlen, die sowohl

Berechenbarkeit ist die Fähigkeit, ein Problem durch ein effektives Verfahren zu lösen.

In der Berechenbarkeitstheorie ist eine Menge natürlicher Zahlen berechenbar (oder entscheidbar oder rekursiv ), wenn es einen Algorithmus gibt , der die Zugehörigkeit jeder natürlichen Zahl zu dieser Menge in endlich

In der Mathematik sind berechenbare Zahlen reelle Zahlen , die mit einem endlichen, terminierenden Algorithmus mit beliebiger Genauigkeit berechnet werden können .

Eine Berechnung ist jede Art von arithmetischer oder nicht-arithmetischer Berechnung , die wohldefiniert ist.

In der Berechenbarkeitstheorie ist die Church-Turing-These eine These über die Natur berechenbarer Funktionen .

In der Metalogik , der mathematischen Logik und der Berechenbarkeitstheorie ist eine effektive Methode oder ein effektives Verfahren ein deterministisches Verfahren mit endlicher Laufzeit zur Lösung eines Problems einer

Der Begriff „elementar“ wurde ursprünglich von László Kalmár im Kontext der Berechenbarkeitstheorie eingeführt .

In der Berechenbarkeitstheorie und der Komplexitätstheorie ist ein Entscheidungsproblem ein Rechenproblem , das als Ja/Nein-Frage zu einer Menge von Eingabewerten formuliert werden kann.

In der Mathematik und Informatik ist das Entscheidungsproblem ( ausgesprochen ) eine Herausforderung, die 1928 von David Hilbert und Wilhelm Ackermann formuliert wurde.

In der theoretischen Informatik zielt das Busy-Beaver-Spiel darauf ab, ein terminierendes Programm gegebener Größe zu finden , das (je nach Definition) entweder die größtmögliche Ausgabe erzeugt oder die längste Laufzeit

In der Berechenbarkeitstheorie ist das Halteproblem die Entscheidung , ob ein beliebiges Computerprogramm und eine beliebige Eingabe irgendwann beendet wird und anhält oder unendlich lange weiterläuft.

In der Physik , Kosmologie und Metaphysik ist die Hypothese des mathematischen Universums ( MUH ), auch bekannt als ultimative Ensembletheorie , eine spekulative „ Theorie von Allem “ (TOE), die vom Kosmologen Max

In der Berechenbarkeitstheorie ist eine primitiv-rekursive Funktion , vereinfacht gesagt, eine Funktion, die von einem Computerprogramm berechnet werden kann, dessen Schleifen ausschließlich „for“-Schleifen sind (d.

In der Informatik ist Rekursion eine Methode zur Lösung von Rechenproblemen , deren Lösung von Lösungen kleinerer Instanzen desselben Problems abhängt.

In Mathematik , Logik und Informatik ist eine rekursive (oder entscheidbare ) Sprache eine rekursive Teilmenge des Kleene-Abschlusses eines Alphabets .

In der mathematischen Logik besagt der Satz von Craig (auch bekannt als Craigs Trick ), dass jede rekursiv aufzählbare Menge wohlgeformter Formeln einer Sprache erster Stufe rekursiv axiomatisierbar , ja sogar primitiv

Der Niedrigbasissatz ist einer von mehreren Basissätzen in der Berechenbarkeitstheorie .

In der Berechenbarkeitstheorie beschreibt der nach Emil Post benannte Satz von Post den Zusammenhang zwischen der arithmetischen Hierarchie und den Turing-Graden .

LOOP ist eine einfache Registersprache, die die primitiv-rekursiven Funktionen präzise abbildet . Die Sprache basiert auf dem Modell der Zählermaschinen .

In der Informatik und der mathematischen Logik misst der Turing-Grad (benannt nach Alan Turing ) oder Grad der Unlösbarkeit einer Menge natürlicher Zahlen den Grad der algorithmischen Unlösbarkeit der Menge.

Eine Turingmaschine ist ein mathematisches Berechnungsmodell, das eine abstrakte Maschine beschreibt , die Symbole auf einem Band gemäß einer Regeltabelle manipuliert.

In der Komplexitätstheorie und der Berechenbarkeitstheorie ist ein Zählproblem eine Art von Rechenproblem , das durch Verschärfung eines Entscheidungsproblems entsteht .