Σταθερά του Chaitin
αγγλικά : Chaitin's constant
γαλλικά : Oméga de Chaitin
γερμανικά : Chaitinsche Konstante
Ο Gregory Chaitin όρισε μια πιθανότητα τερματισμού, που αναπαριστάται από το σύμβολο Ω, ένα είδος πραγματικού αριθμού που ανεπίσημα δηλώνει την πιθανότητα τερματισμού ενός τυχαίου προγράμματος. Αυτοί οι αριθμοί έχουν τον ίδιο βαθμό Turing όπως το πρόβλημα τερματισμού. Είναι ένας κανονικός και υπερβατικός αριθμός που μπορεί να προσδιορισθεί αλλά δεν μπορεί να υπολογιστεί. Αυτό σημαίνει ότι δεν υπάρχει αλγόριθμος που να παράγει όλα τα ψηφία του Ω αλλά μόνο μερικά αρχικά.
Το Ω είναι ένα παράδειγμα μη υπολογίσιμου αριθμού. Ορίζεται ως, σύμφωνα με τον Gregory Chaitin
\( \Omega =\sum _{{p\ {\mathrm {h{\ddot a}lt}}}}2^{{-\left|p\right|}} \)
όπου σημαίνει το άθροισμα όλων των προγραμμάτων
p (όλα τα προγράμματα που σταματούν μετά από έναν πεπερασμένο χρόνο εκτέλεσης χωρίς είσοδο) και το \({\ displaystyle | p |} \) δηλώνει τη διάρκεια του προγράμματος σε bit. Αυτό σημαίνει ότι κάθε πρόγραμμα με τερματισμό μήκους m bits αυξάνει το m-th bit της δυαδικής αναπαράστασης του \( \ Omega \) κατά 1.
Σημείωση: Δεδομένου ότι υπάρχει ορισμένη ελευθερία ορισμού της καθολικής μηχανής Turing, η ακριβής τιμή της σταθεράς εξαρτάται από τον ορισμό .
Η γνώση των πρώτων n bit της σταθεράς μπορεί να λύσει το πρόβλημα συγκράτησης για τερματισμού, έως και n bits, έτσι ώστε πολλά ενδιαφέροντα μαθηματικά προβλήματα να μπορούν να επιλυθούν γνωρίζοντας τις πρώτες χιλιάδες bit της σταθεράς.
Ωστόσο, δεδομένου ότι το πρόβλημα τερματισμού, δεν μπορεί να επιλυθεί, \(\ Omega \) δεν μπορεί να υπολογιστεί και ως εκ τούτου είναι ένας υπερβατικός πραγματικός αριθμός.
Το 2002 μια ερευνητική ομάδα με επικεφαλής τον Cristian Calude από το Πανεπιστήμιο του Ώκλαντ καθόρισε τα πρώτα 64 bit του αριθμού ελέγχοντας όλα τα προγράμματα Turing μήκους έως και 80 bit.
βιβλιογραφία
Eric W. Weisstein: Chaitinsche Konstante. In: MathWorld (englisch).
Cristian S. Calude’s Website. (die ersten 64 Bit einer chaitinschen Konstante)
Jörg Resag: Die Grenzen der Berechenbarkeit. joerg-resag.de, 2008, Kapitel 3.4
Hellenica World - Scientific Library
Από τη ελληνική Βικιπαίδεια http://el.wikipedia.org . Όλα τα κείμενα είναι διαθέσιμα υπό την GNU Free Documentation License
