Μη υπολογισιμότητα

Το πρόβλημα του τερματισμού (halting problem)

Τερματίζει(Πρόγραμμα, Δεδομένα)
Είσοδος: Πρόγραμμα, Δεδομένα
Έξοδος: Αληθές αν το πρόγραμμα τερματίζει με τα δεδομένα,
αλλιώς ψευδές.

Δοκιμή(Πρόγραμμα, Δεδομένα)
Αν Τερματίζει(Πρόγραμμα, Δεδομένα) Τότε
  Όσο αληθές
  Τέλος (Όσο)
Αλλιώς
  Δοκιμή := ψευδές
Τέλος (Αν)

Δοκιμή(Δοκιμή ..., Δοκιμή ...)

ΠροηγούμενηΠολυπλοκότητα
Περιεχόμενα
ΕπόμενηΑλγοριθμική οικουμενικότητα