Τελικά μήπως στον υπολογιστή πρακτικά ασχολούμαστε μόνο με τους ρητούς (λόγω της πεπερασμένης αποθήκευσης);
Φυσικά και στον υπολογιστή δεν ασχολούμαστε μόνο με ρητούς, αφού ασχολούμαστε ακόμα και με μη-υπολογίσιμους πραγματικούς σύμφωνα με την προηγούμενη παράγραφο. Βλ. σχετικά Symbolic Computation και C.A.S (Computer Algebra System). 'Ενα κλασσικό παράδειγμα (επίλυση δευτεροβάθμιας με συντελεστές που συμπεριλαμβάνουν τον υπερβατικό (και υπολογίσιμο πραγματικό) π): https://www.wolframalpha.com/input/?i=solve+x%5E2%2B%CF%80x%2B-2 (https://www.wolframalpha.com/input/?i=solve+x%5E2%2B%CF%80x%2B-2)
Δεν νομίζω. Νομίζω ότι ασχολούμαστε με οτιδήποτε μπορούμε να αναπαραστήσουμε ψηφιακά.
Ας μην ξεχνάμε ότι και ο άρρητος "Ρίζα(3)" είναι πεπερασμένος σαν πληροφορία. Είναι ένα string από 7 chars. Δεν μας υποχρεώνει κανείς να τον μετατρέψουμε σε δεκαδικό αριθμό για να τον αποθηκεύσουμε στον υπολογιστή, μπορούμε π.χ. να τον αναπαραστήσουμε ως record: { function="Ρίζα", parameter="3" }.
Δεν έχω δουλέψει Matlab αλλά νομίζω ότι υποστηρίζει τέτοια πράγματα και έτσι μπορεί να κάνει πράξεις με ρίζες κλπ χωρίς να χάνεται καθόλου πληροφορία με στρογγυλοποιήσεις αριθμών. Είναι λίγο πρόκληση το πώς θα υλοποιηθούν όλα αυτά (π.χ. το τετράγωνο της ρίζας να δίνει τον αρχικό αριθμό χωρίς απώλειες) αλλά σίγουρα μπορούμε σε ορισμένες περιπτώσεις να ασχολούμαστε και με άρρητους, και με μιγαδικούς και με οτιδήποτε άλλο θέλουμε, χωρίς απώλεια στην πληροφορία και με πεπερασμένο χώρο αποθήκευσης.
Οι μη-υπολογίσιμοι πραγματικοί είναι όμως ορίσιμοι (definable) σε κάποια τυπική μαθηματική θεωρία (formal theory) η οποία εκφράζεται με κάποια τυπική γλώσσα (formal language). Για κάθε τέτοια γλώσσα υπάρχει μια μηχανή Turing που την αναγνωρίζει. Επομένως, μ' αυτήν την έννοια βεβαίως και οι μηχανές Turing αφορούν κάθε πραγματικό αριθμό, αλλά και κάθε μαθηματική θεωρία. [/url].Αυτό πραγματικά πρώτη φορά το ακούω και θα ήθελα αν σου είναι εύκολο ένα σύνδεσμο για περαιτέρω μελέτη.
Οι μη-υπολογίσιμοι πραγματικοί είναι όμως ορίσιμοι (definable) σε κάποια τυπική μαθηματική θεωρία (formal theory) η οποία εκφράζεται με κάποια τυπική γλώσσα (formal language). Για κάθε τέτοια γλώσσα υπάρχει μια μηχανή Turing που την αναγνωρίζει. Επομένως, μ' αυτήν την έννοια βεβαίως και οι μηχανές Turing αφορούν κάθε πραγματικό αριθμό, αλλά και κάθε μαθηματική θεωρία.
Αυτό πραγματικά πρώτη φορά το ακούω και θα ήθελα αν σου είναι εύκολο ένα σύνδεσμο για περαιτέρω μελέτη.
υγΤου Παπαδημητρίου είναι απλά εγώ έχω βάλει την έμφαση ;)
Όλα αυτά βέβαια επιβεβαιώνουν το μοτό σου, το οποίο είναι και δικό μου.
Του Παπαδημητρίου είναι απλά εγώ έχω βάλει την έμφαση ;)
(https://gbougioukas.files.wordpress.com/2016/10/p26.png)
Όπου d o υπολογίσιμος πραγματικός αριθμός που ορίζεται ως εξής:
Ακέραιο μέρος ίσο με 0 και:
1ο δεκαδικό ψηφίο: 0 αν αριθμός 4 γράφεται ως άθροισμα δύο πρώτων, αλλιώς 1
2ο δεκαδικό ψηφίο: 0 αν αριθμός 6 γράφεται ως άθροισμα δύο πρώτων, αλλιώς 1
3ο δεκαδικό ψηφίο: 0 αν αριθμός 8 γράφεται ως άθροισμα δύο πρώτων, αλλιώς 1
...
(https://gbougioukas.files.wordpress.com/2016/10/p26.png)
Όπου d o υπολογίσιμος πραγματικός αριθμός που ορίζεται ως εξής:
Ακέραιο μέρος ίσο με 0 και:
1ο δεκαδικό ψηφίο: 0 αν αριθμός 4 γράφεται ως άθροισμα δύο πρώτων, αλλιώς 1
2ο δεκαδικό ψηφίο: 0 αν αριθμός 6 γράφεται ως άθροισμα δύο πρώτων, αλλιώς 1
3ο δεκαδικό ψηφίο: 0 αν αριθμός 8 γράφεται ως άθροισμα δύο πρώτων, αλλιώς 1
...
(https://gbougioukas.files.wordpress.com/2016/10/p26.png)
Όπου d o υπολογίσιμος πραγματικός αριθμός που ορίζεται ως εξής:
Ακέραιο μέρος ίσο με 0 και:
1ο δεκαδικό ψηφίο: 0 αν αριθμός 4 γράφεται ως άθροισμα δύο πρώτων, αλλιώς 1
2ο δεκαδικό ψηφίο: 0 αν αριθμός 6 γράφεται ως άθροισμα δύο πρώτων, αλλιώς 1
3ο δεκαδικό ψηφίο: 0 αν αριθμός 8 γράφεται ως άθροισμα δύο πρώτων, αλλιώς 1
...
Πέρα από την απόδειξη που παρουσιάζω, αν το δεδομένο πρόβλημα είναι επιλύσιμο και μάλιστα δομημένο όπως ισχυρίζεται το βιβλίο χωρίς να περιορίζει τους συντελεστές στο σύνολο των ρητών αριθμών, τότε θα πρέπει κάποιος να γνωρίζει τον αλγόριθμο. Παρακαλείται λοιπόν όποιος τον γνωρίζει να παραθέσει την χρήση αυτού του αλγορίθμου για την επίλυση της παρακάτω εξίσωσης (Ε1) στο ℝ:
(https://gbougioukas.files.wordpress.com/2016/10/p26.png)
Όπου d o υπολογίσιμος πραγματικός αριθμός που ορίζεται ως εξής:
Ακέραιο μέρος ίσο με 0 και:
1ο δεκαδικό ψηφίο: 0 αν αριθμός 4 γράφεται ως άθροισμα δύο πρώτων, αλλιώς 1
2ο δεκαδικό ψηφίο: 0 αν αριθμός 6 γράφεται ως άθροισμα δύο πρώτων, αλλιώς 1
3ο δεκαδικό ψηφίο: 0 αν αριθμός 8 γράφεται ως άθροισμα δύο πρώτων, αλλιώς 1
...
Ο υπολογισμός του d είναι ισοδύναμο πρόβλημα με τον υπολογισμό του d+1.
Αυτό δεν σημαίνει ότι η πρόσθεση δύο αριθμών είναι ανοικτό πρόβλημα.
Κάνεις σύνθεση δύο συναρτήσεων/αλγορίθμων, Δευτεροβάθμια(Goldbach()), και επειδή το αποτέλεσμά τους είναι ανοικτό, θεωρείς ότι και οι δύο αλγόριθμοι είναι ανοικτά προβλήματα. Δεν ισχύει ο συλλογισμός σου.
Είναι παρόμοιος με το "το π είναι άρρητος <=> το 3*π είναι άρρητος => το 3 είναι άρρητος", όπου προφανώς το τελευταίο σκέλος δεν ισχύει.
Άρα: Goldbach()=ανοικτό, Δευτεροβάθμια(Goldbach())=ανοικτό, αλλά Δευτεροβάθμια()=επιλύσιμο.
Α) Θα βοηθούσε λίγο να θυμηθούμε ποιο είναι το πρόβλημα της επίλυσης 2θμιας εξίσωσης:
«Με γνωστούς τους συντελεστές ενός τριωνύμου, ποιες είναι οι ρίζες του;»
Ο αλγόριθμος που έχουμε για την επίλυση τριωνύμου λύνει το παραπάνω πρόβλημα. Εσύ παρουσιάζεις ένα τριώνυμο στο οποίο δεν γνωρίζουμε όλους τους συντελεστές. Δεν υπάρχει αλγόριθμος που να λύνει τριώνυμο χωρίς να ξέρουμε τους συντελεστές.
Η απόδειξη που παρουσιάζεις στο λινκ είναι λάθος. Το πρώτο-πρώτο θεώρημα που παρουσιάζεις, δλδ
«Το πρόβλημα της ισότητας δύο πραγματικών σταθερών είναι μη-αποφασίσιμο (Θ1).»
είναι λάθος. Το σκεπτικό σου στηρίζεται στο ότι μια μηχανή δεν μπορεί να αναπαραστήσει/χειριστεί/αποθηκεύσει τους πραγματικούς αριθμούς ...
(https://gbougioukas.files.wordpress.com/2016/10/p26.png)
Όπου d o υπολογίσιμος πραγματικός αριθμός που ορίζεται ως εξής:
Ακέραιο μέρος ίσο με 0 και:
1ο δεκαδικό ψηφίο: 0 αν αριθμός 4 γράφεται ως άθροισμα δύο πρώτων, αλλιώς 1
2ο δεκαδικό ψηφίο: 0 αν αριθμός 6 γράφεται ως άθροισμα δύο πρώτων, αλλιώς 1
3ο δεκαδικό ψηφίο: 0 αν αριθμός 8 γράφεται ως άθροισμα δύο πρώτων, αλλιώς 1
...
Θεωρώ ότι υπολογίζω το d με την ακρίβεια που μου επιτρέπει το υπολογιστικό σύστημα που έχω.
Το υπολογίζω όπως θα υπολόγιζα και το π ή το e με τις αντίστοιχες σειρές.
ο ορισμός για την πραγματική σταθερά d (η οποία είναι ακολουθία ρητών αριθμών Cauchy) είναι η πεπερασμένη συμβολοσειρά που αποτελείται από τον κώδικα (σε όποια Turing-πλήρη) γλώσσα προγραμματισμού θέλεις (πχ Java) που παράγει το νιοστό δεκαδικό ψηφίο της d.
@gbougioukas, για να απλοποιήσουμε τη συζήτηση, τελικά πιστεύεις ότι η πρόσθεση δύο οποιωνδήποτε πραγματικών αριθμών είναι επιλύσιμο πρόβλημα ή όχι;
Άρα το d+d είναι επιλύσιμο, ενώ η δευτεροβάθμια που έχει ως συντελεστή το d δεν είναι;
Άρα το d+d είναι επιλύσιμο, ενώ η δευτεροβάθμια που έχει ως συντελεστή το d δεν είναι;
Άλκη το πρόβλημα δεν είναι οι βασικές πράξεις αν κατάλαβα καλά αλλά η ρίζα η οποία υπολογίζεται προσεγγιστικά
Το πρόβλημα είναι ότι δεν μπορούμε να τον συγκρίνουμε με το μηδέν. Δεν ξέρω πόσο σημαντικό είναι αυτό για τους μαθηματικούς. Πάντως για τον δικό μας κλάδο δεν δημιουργείται κανένα θέμα. Όλοι οι αλγόριθμοι ισχύουν, απλώς βάζουμε d στην θέση του π ή του e. Αν ο αλγόριθμος πρέπει να ελέγξει αν το d είναι μηδέν, τότε βάζουμε ένα if (d==0) και τελειώνουμε.
Θα σε συμβούλευα να κάνεις μια ερώτηση στο Quora. Θα σου απαντήσουν επαγγελματίες μαθηματικοί που κατέχουν καλά αυτό το topic. Σ' αυτό το φόρουμ δεν νομίζω να μπορεί κανείς να βοηθήσει περισσότερο.
Το πρόβλημα με το d δεν βλέπω να αφορά τους υπολογιστές. Για τον κλάδο μας δύο περιπτώσεις υπάρχουν:
1) Αν θέλουμε να μεταχειριστούμε το d ως πραγματικό θα χρησιμοποιήσουμε ένα πρόγραμμα όπως το mathematica. Το αποτέλεσμα της πρόσθεσης που φέρνεις ως παράδειγμα θα είναι 1+d (το 0.999.. είναι ειδική περίπτωση).
2) Αν θέλουμε αριθμητική επίλυση έκφρασης που περιέχει το d, τότε θα πάρουμε μια προσέγγιση με όσο μεγάλη ακρίβεια θέλουμε (όπως κάνουμε και με το e). Ο κανόνας για να υπολόγιζουμε οποιοδήποτε δεκαδικό ψηφίο υπάρχει. Σ' αυτή την περίπτωση βέβαια και με τα σημερινά δεδομένα το d θα είναι πάντα μηδέν.
Η αναπαράσταση στον υπολογιστή πρέπει να γίνεται όχι μόνο σε πεπερασμένο χώρο, αλλά και σε πεπερασμένο χρόνο. Εάν χρειάζεσαι απειροσειρά/άπειρο χρόνο εκτέλεσης για τον υπολογισμό ενός αριθμού ή μιας βασικής πράξης ή μιας σύγκρισης, τότε πλέον δεν μιλάς για αλγορίθμους.
Συνεχίζοντας το παράδειγμα με τις προσθέσεις, έστω ότι ορίζω τον αριθμό α=0.99999 (περίοδος) και θέλω να τον προσθέσω με το "d". Ποιο θα είναι το πρώτο ψηφίο του αποτελέσματος; 1 ή 0;
Μήπως τώρα και η πρόσθεση δύο πραγματικών έγινε μη επιλύσιμη;
Συνεχίζοντας το παράδειγμα με τις προσθέσεις, έστω ότι ορίζω τον αριθμό α=0.99999 (περίοδος) και θέλω να τον προσθέσω με το "d". Ποιο θα είναι το πρώτο ψηφίο του αποτελέσματος; 1 ή 0;
Μήπως τώρα και η πρόσθεση δύο πραγματικών έγινε μη επιλύσιμη;
Έχω αντίρρηση στο 0.99999=1, αλλά για να μην φάμε την ώρα μας με αυτό, ας αλλάξω λίγο την εκφώνηση.
Κάνε το ίδιο με το 1-d.
Ακέραιο μέρος = πόσο;
1ο δεκαδικό ψηφίο = πόσο;
Αν δεν μπορείς καν να υπολογίσεις το πρώτο ψηφίο αυτού του αριθμού, μήπως η αφαίρεση πραγματικών είναι μη επιλύσιμο πρόβλημα;
Ισχύει 1 = 0.999... ("..." σημαίνει άπειρα εννιάρια)
....
Ακέραιο μέρος ίσο με 0 και
Δηλαδή το ακέραιο μέρος του 1 είναι το 0; ?!?!?!
Εγώ όμως ξέρω ότι το ακέραιο μέρος του 1 είναι το 1, άρα μόλις απέδειξες ότι 0=1; ?!?!?!
Δεν μπορείς να μιλάς προσεγγιστικά για το ακέραιο μέρος ενός αριθμού, έχει μια πολύ συγκεκριμένη ακέραια τιμή. Δεν μπορεί να είναι και 1 και 0 ταυτόχρονα.
@gbougioukas, δεν διαφωνώ ότι 0.9999...=1 (https://en.wikipedia.org/wiki/0.999...) σε μερικά συστήματα αρίθμησης των μαθηματικών (δες το λινκ για κάποια που δεν ισχύει), αλλά όπως βλέπεις και παραπάνω στην απόδειξή σου, αυτό προϋποθέτει άπειρα δεκαδικά ψηφία, που στον υπολογιστή δεν τα έχουμε (γιατί αλλιώς 10χ=9.999990, με μηδέν στο όσο-μεγάλο-θέλουμε-αλλά-περιορισμένου-μεγέθους δεκαδικό μέρος). Ισοδύναμα, στις κλασσικές αναπαραστάσεις πραγματικών αριθμών στον υπολογιστή υπάρχει πάντα ο "επόμενος πραγματικός αριθμός", ενώ στα μαθηματικά δεν υπάρχει. Αυτά δεν είναι άσχετες συζητήσεις με το αρχικό θέμα, αλλά ήθελα να τις αποφύγω γιατί είναι απόρροιες της αναπαράστασης και όχι αίτια.
Ουσιαστικά αυτό που θέλω να πω είναι ότι το να περιγράψουμε έναν αριθμό σε πεπερασμένο χώρο/χρόνο δεν σημαίνει και ότι θα μπορούμε να κάνουμε και πράξεις με αυτόν σε πεπερασμένο χώρο/χρόνο, και γι' αυτό το λόγο αυτού του είδους οι αναπαραστάσεις δεν είναι κατάλληλες για υπολογιστές ούτε μπορούν να χρησιμοποιηθούν για την απόδειξη μη επιλυσιμότητας προβλημάτων πραγματικών αριθμών από υπολογιστή.
@alkisg1η παρατήρηση
Παραθέτω μια απόδειξη:
(https://wikimedia.org/api/rest_v1/media/math/render/svg/2d95ab37b469c220c90bae45e797a62a1c539f8f)
Κάθε μαθηματικός ορισμός (εξ' ορισμού) είναι μια πεπερασμένη συμβολοσειρά. Άρα μπορεί να χρησιμοποιηθεί μια χαρά στον υπολογιστή. Σ' ένα σύνηθες CAS υπάρχει για παράδειγμα το άπειρο άθροισμα (σειρά). Κάθε υπολογίσιμη πραγματική σταθερά γράφεται ως σειρά. Για παράδειγμα ο αριθμός d είναι η παρακάτω πεπερασμένη συμβολοσειρά στο maxima:
sum(product(1−(product(1−product(sin((%pi*k+%pi*i)/p)^2/sin((%pi*k)/p)^2,k,1,p−1),p,2,sqrt(i)))*product(1−product(sin((%pi*(2*k−i+2)+%pi*k)/p)^2/sin((%pi*k)/p)^2,k,1,p−1),p,2,sqrt(2*k−i+2)),i,2,k+1)/10^k,k,1,inf);
Στην τρίτη παράγραφο το λέει, "In most such number systems, the standard interpretation of the expression 0.999… makes it equal to 1, but in some of these number systems, the symbol "0.999…" admits other interpretations that contain infinitely many 9s while falling infinitesimally short of 1."
Το να ορίσω έναν αριθμό σε πεπερασμένο χώρο/κώδικα δεν είναι το ίδιο με το να μπορώ να κάνω πράξεις με αυτόν σε πεπερασμένο χώρο/χρόνο. Γι' αυτό και στους υπολογιστές χρησιμοποιούμε πραγματικούς αριθμούς περιορισμένης ακρίβειας. Δυστυχώς όμως είναι πεπερασμένος και ο χρόνος που μπορούμε να διαθέσουμε σε τέτοιες συζητήσεις... :)
Θα χαρώ πολύ να δω μια καινούργια κατασκευή των πραγματικών, όποτε την κάνεις let me know :)Δεν χρειάζεται, υπάρχουν καμιά 20αριά διαφορετικές κατασκευές των πραγματικών κάποιες από τις οποίες είναι και σχετικά καινούργιες.
Δεν χρειάζεται, υπάρχουν καμιά 20αριά διαφορετικές κατασκευές των πραγματικών κάποιες από τις οποίες είναι και σχετικά καινούργιες.
The Real Numbers - A Survey of Constructions (https://arxiv.org/pdf/1506.03467.pdf)
2η παρατήρηση
Όπως είπα και προηγουμένως ο "αριθμός" 0.99999... είναι στην πραγματικότητα το όριο μιας σειράς με άπειρους όρους. Κρύβει δηλαδή μέσα του έναν αλγόριθμο ο οποίος προσθέτει άπειρους όρους. (αλγόριθμος που προσθέτει άπειρους όρους??? :(σίγουρα θα έχω τρελαθεί)
Το αναφέρω όμως γιατί παραπάνω είχες πει το εξής:Κάθε μαθηματικός ορισμός (εξ' ορισμού) είναι μια πεπερασμένη συμβολοσειρά. Άρα μπορεί να χρησιμοποιηθεί μια χαρά στον υπολογιστή. Σ' ένα σύνηθες CAS υπάρχει για παράδειγμα το άπειρο άθροισμα (σειρά). Κάθε υπολογίσιμη πραγματική σταθερά γράφεται ως σειρά. Για παράδειγμα ο αριθμός d είναι η παρακάτω πεπερασμένη συμβολοσειρά στο maxima:ουσιαστικά επειδή δεν μπορείς να υπολογίσεις τον αριθμό θεωρείς ως αναπαράστασή του τον αλγόριθμο υπολογισμού του. Διότι ο συμβολισμός με το Σ είναι ένας αλγόριθμος υπολογισμού σειράς άπειρων όρων.
sum(product(1−(product(1−product(sin((%pi*k+%pi*i)/p)^2/sin((%pi*k)/p)^2,k,1,p−1),p,2,sqrt(i)))*product(1−product(sin((%pi*(2*k−i+2)+%pi*k)/p)^2/sin((%pi*k)/p)^2,k,1,p−1),p,2,sqrt(2*k−i+2)),i,2,k+1)/10^k,k,1,inf);
Με το ίδιο ακριβώς σκεπτικό θεωρώ και εγώ τον παρακάτω αλγόριθμο ή για να είμαι πιο ακριβής την παρακάτω πεπερασμένη συμβολοσειρά:Κώδικας: C++
Goldbach = True for (i=2; Goldbach ; i+=2) Goldbach = False for (j=2; j<i; i++) if (j is prime and i–j is prime) Goldbach = True if not Goldbach return False; return Goldbach;
η οποία δίνει την απάντηση στο ερώτημα αν ισχύει η εικασία του Goldbach ή όχι
Με το ίδιο ακριβώς σκεπτικό που εσύ χρησιμοποιείς τον αλγόριθμο υπολογισμού ως πεπερασμένη συμβολοσειρά
μπορώ και εγώ να θεωρήσω τον παραπάνω αλγόριθμο ο οποίος λύνει την εικασία του Goldbach επίσης ως πεπερασμένη συμβολοσειρά. άρα με το ίδιο σκεπτικό το παραπάνω αποτελεί τη λύση της εικασίας.
ΥΓ. Για την ιστορία η εικασία του Goldbach ισχύει για όλους τους αριθμούς μέχρι τον 4 × 1018 οπότε στον "πραγματικό" κόσμο μάλλον ισχύει