Η σταθερά του Chaitin είναι ένα παράδειγμα (στην πραγματικότητα μια οικογένεια παραδειγμάτων) ενός μη υπολογίσιμου αριθμού. Το αντιπροσωπεύει την πιθανότητα ότι ένα πρόγραμμα που δημιουργείται τυχαία (σε ένα συγκεκριμένο μοντέλο) θα σταματήσει. Μπορεί να υπολογιστεί κατά προσέγγιση, αλλά δεν υπάρχει (αποδεδειγμένα) αλγόριθμος για τον υπολογισμό του με αυθαίρετη ακρίβεια.
Τι κάνει έναν αριθμό υπολογίσιμο;
Ένας υπολογίσιμος αριθμός είναι ένας αριθμός που μπορεί να υπολογιστεί από ένα πεπερασμένο πρόγραμμα υπολογιστή. Όλοι οι αριθμοί που έχετε ακούσει ποτέ, όπως 3, √2, π, e, κ.λπ. είναι υπολογίσιμοι. Μερικοί αριθμοί (όπως π) αντιπροσωπεύονται από μια άπειρη συμβολοσειρά μη επαναλαμβανόμενων ψηφίων.
Τι σημαίνει μη υπολογίσιμο;
Ένα μη υπολογίσιμο είναι ένα πρόβλημα για το οποίο δεν υπάρχει αλγόριθμος που να μπορεί να χρησιμοποιηθεί για την επίλυσή του. Το πιο διάσημο παράδειγμα μη υπολογισιμότητας (ή μη αποφασιστικότητας) είναι το Πρόβλημα Παύσης.
Υπάρχουν μη υπολογίσιμοι αριθμοί;
Όχι μόνο υπάρχουν μη υπολογίσιμοι αριθμοί, αλλά στην πραγματικότητα είναι πολύ πιο άφθονοι από τους υπολογίσιμους αριθμούς. Πολλοί, πολλοί πραγματικοί αριθμοί είναι απλώς άπειρες ακολουθίες φαινομενικά τυχαίων ψηφίων, χωρίς μοτίβο ή ειδική ιδιότητα. … Ως ένα τέτοιο παράδειγμα, θεωρήστε έναν αριθμό του οποίου το μέρος πριν από την υποδιαστολή είναι 0.
Είναι υπολογίσιμοι οι πραγματικοί αριθμοί;
Ένας πραγματικός αριθμός είναι υπολογίσιμος εάν και μόνο εάν το σύνολο των φυσικών αριθμών που αντιπροσωπεύει (όταν γράφεται σε δυαδικό και θεωρείται ως χαρακτηριστική συνάρτηση) είναι υπολογίσιμο. Κάθε υπολογίσιμοο αριθμός είναι αριθμητικός.
