Die Webseiten der Fachschaft Informatik am ERG Saalfeld


Entscheidbarkeit - zweiseitig entscheidbar

In der Informatik heißt eine Eigenschaft auf einer Menge entscheidbar, wenn es ein Entscheidungsverfahren für sie gibt. Unter einem Entscheidungsverfahren versteht man in der Informatik ein Algorithmus, der für jedes Element der Menge beantworten kann, ob es die Eigenschaft hat oder nicht.

Wenn es kein solches Entscheidungsverfahren gibt, dann nennt man die Eigenschaft nicht entscheidbar. Besitzt es allerdings mehrere Möglichkeiten, die man zu speziellen Gruppen zuordnen kann, nennt man die Eigenschaft zweiseitig entscheidbar. Gibt es nur eine Möglichkeit für solch ein Entscheidungsverfahren, zählt man dies zu einseitig entscheidbar (oder semi-entscheidbar).



zweiseitig entscheidbar

Bei der zweiseitigen Entscheidbarkeit kann man deutlich mit ja und nein antworten. Dementsprechend kann man dies in jeweilige Gruppen einteilen.

Primzahlproblem

Ist 2 eine Primzahl? Ist 4 eine Primzahl?
Es geht also darum, durch einen Algorithmus zu entscheiden, ob eine eingegebene Zahl zu der Gruppe der Primzahlen gehört oder in die Gruppe der "Nichtprimzahlen".
(naiver) Algorithmus: Man dividiert die eingegebene Zahl durch 2, 3, 4, 5 ... bis zur eingegebenen Zahl. Wenn bei jeder dieser Rechnungen ein Rest ungleich 0 auftritt, dann ist es eine Primzahl, sonst ist es keine Primzahl. => (zweiseitig) entscheidbar

Gibt es unendlich viele Primzahlen?
Es geht bei dieser Fragestellung darum, ob die Menge der Primzahlen endlich ist oder ob die Menge der Primzahlen unendlich ist.
Aus der 5. Klasse ist durch den Beweis von Euklid bekannt, dass es unendlich viele Primzahlen gibt. => (zweiseitig) entscheidbar

Primzahlzwillinge

Gibt es unendlich viele Primzahlzwillinge? (3-5, 5-7, 11-13, 17-19 ...)
Es geht bei dieser Fragestellung darum, ob die Menge der Primzahluwillinge endlich ist oder ob die Menge der Primzahlzwillinge unendlich ist.
Natürlich kann es nur ein "ja" oder ein "nein" als Antwort geben, d.h. dieses Problem ist (zweiseitig) entscheidbar. ABER: es gibt noch keinen Beweis, weder für "ja" noch für "nein".

 

Aufgaben

  1. Ist ein Würfel ein platonischer Körper? Geben Sie dazu auch das Entscheidungskriterium an.
  2. Ist Phobos ein Mond? Geben Sie auch hierzu das Entscheidungskriterium an.

 

Weblinks

  1. www8.cs.fau.de/_media/ss16:thinfwil:milius-tl-ep_ho.pdf

 

zurück


© ERG Saalfeld   -   Hans-Dietrich Kirmse   25.03.2019