12 Beziehungen: Berechenbarkeit, Berechenbarkeitstheorie, Entscheidbar, Gödelnummer, Halteproblem, Indexmenge (Mathematik), Komplement (Mengenlehre), Nummerierung (Informatik), Partielle Funktion, Rekursiv aufzählbare Menge, Relation (Mathematik), Satz von Rice.
Berechenbarkeit
Eine mathematische Funktion ist berechenbar (auch effektiv berechenbar oder rekursiv), wenn für sie eine Berechnungsanweisung (Algorithmus) formuliert werden kann (Berechenbarkeitstheorie).
Neu!!: Indexmenge (Berechenbarkeitstheorie) und Berechenbarkeit · Mehr sehen »
Berechenbarkeitstheorie
Die Berechenbarkeitstheorie (auch Rekursionstheorie) ist ein Teilgebiet der theoretischen Informatik und der mathematischen Logik, die sich mit dem Begriff der Berechenbarkeit befasst, insbesondere damit, welche Probleme mit Hilfe einer Maschine (genauer: eines mathematischen Modells einer Maschine) oder eines anderen mathematischen Modells der Berechenbarkeit lösbar sind.
Neu!!: Indexmenge (Berechenbarkeitstheorie) und Berechenbarkeitstheorie · Mehr sehen »
Entscheidbar
In der theoretischen Informatik heißt eine Eigenschaft auf einer Menge entscheidbar (auch rekursiv, rekursiv ableitbar), wenn es ein Entscheidungsverfahren für sie gibt.
Neu!!: Indexmenge (Berechenbarkeitstheorie) und Entscheidbar · Mehr sehen »
Gödelnummer
Eine Gödelnummer ist eine natürliche Zahl, die einem Wort einer formalen Sprache nach einem bestimmten Verfahren zugeordnet wird und dieses Wort eindeutig kennzeichnet.
Neu!!: Indexmenge (Berechenbarkeitstheorie) und Gödelnummer · Mehr sehen »
Halteproblem
Das Halteproblem beschreibt eine Frage aus der theoretischen Informatik.
Neu!!: Indexmenge (Berechenbarkeitstheorie) und Halteproblem · Mehr sehen »
Indexmenge (Mathematik)
In der Mathematik bezeichnet Index (Plural: Indizes) ein Element einer Indexmenge, das zur Nummerierung unterschiedlichster Objekte herangezogen wird.
Neu!!: Indexmenge (Berechenbarkeitstheorie) und Indexmenge (Mathematik) · Mehr sehen »
Komplement (Mengenlehre)
In der Mengentheorie und anderen Teilgebieten der Mathematik sind zwei verschiedene Komplemente definiert: Das relative Komplement und das absolute Komplement.
Neu!!: Indexmenge (Berechenbarkeitstheorie) und Komplement (Mengenlehre) · Mehr sehen »
Nummerierung (Informatik)
Eine Nummerierung einer Menge M, im Sinne der Berechenbarkeitstheorie, ist eine möglicherweise partielle surjektive Funktion \nu:\mathbb N\to_p M. Nummerierungen und die verwandten Notationen sind z. B.
Neu!!: Indexmenge (Berechenbarkeitstheorie) und Nummerierung (Informatik) · Mehr sehen »
Partielle Funktion
Eine partielle Funktion von der Menge X nach der Menge Y ist eine binäre, rechtseindeutige Relation, das heißt eine Relation, in der jedem Element der Menge X höchstens ein Element der Menge Y zugeordnet wird.
Neu!!: Indexmenge (Berechenbarkeitstheorie) und Partielle Funktion · Mehr sehen »
Rekursiv aufzählbare Menge
Als rekursiv aufzählbare Menge (auch semi-entscheidbare Menge, positiv semi-entscheidbare Menge, halb-entscheidbare Menge, berechenbar aufzählbare Menge, kurz r.e., c.e.) wird in der Berechenbarkeitstheorie eine Menge von natürlichen Zahlen bezeichnet, wenn es einen Algorithmus gibt, der die Elemente dieser Menge aufzählt.
Neu!!: Indexmenge (Berechenbarkeitstheorie) und Rekursiv aufzählbare Menge · Mehr sehen »
Relation (Mathematik)
Eine Relation („Beziehung“, „Verhältnis“) ist allgemein eine Beziehung, die zwischen Dingen bestehen kann.
Neu!!: Indexmenge (Berechenbarkeitstheorie) und Relation (Mathematik) · Mehr sehen »
Satz von Rice
Der Satz von Rice ist ein Ergebnis der Theoretischen Informatik.
Neu!!: Indexmenge (Berechenbarkeitstheorie) und Satz von Rice · Mehr sehen »