Θέμα: Είναι πράγματι η επίλυση της δευτεροβάθμιας εξίσωσης επιλύσιμο πρόβλημα ;

[gbougioukas]

@apoldem

Το maxima δεν είναι ακόμα ετοιμο για την Ε1

[evry]

ο ορισμός για την πραγματική σταθερά d (η οποία είναι ακολουθία ρητών αριθμών Cauchy) είναι η πεπερασμένη συμβολοσειρά που αποτελείται από τον κώδικα (σε όποια Turing-πλήρη) γλώσσα προγραμματισμού θέλεις (πχ Java) που παράγει το νιοστό δεκαδικό ψηφίο της d.

το ίδιο δεν είπα και εγώ? απλά δεν έδωσα τον ορισμό των computable real numbers που είναι αυτό που περιγράφεις:

A computable number is one for which there is a Turing machine which, given n on its initial tape, terminates with the nth digit of that number
Marvin Minsky

Δεν κατάλαβα τι συνεισφέρουν στην κουβέντα οι ακολουθίες Cauchy που χρησιμοποιούνται για την κατασκευή των πραγματικών από τους ρητούς. Έχουν νόημα ως μαθηματική θεμελίωση του IR αλλά από υπολογιστικής πλευράς ο παραπάνω ορισμός αρκεί πιστεύω.

Όσον αφορά την αναπαράσταση με πεπερασμένη συμβολοσειρά που λες δεν καταλαβαίνω πάλι στο μέρος του υπολογισμού που μπορεί να είναι χρήσιμη. Αν είναι έτσι αντί να γράφουμε sin(x) θα χρησιμοποιούσαμε το συμβολισμό Σ με τη σειρά που υπολογίζει το sin(x) η οποία συγκλίνει. Αυτό όμως δεν σημαίνει ότι την υπολογίσαμε κιόλας.

[gbougioukas]

@evry
Η ρητή προσσέγγιση ενός πραγματικού είναι ρητός, δεν είναι πραγματικός. Η προσέγγιση είναι εξ ορισμού απώλεια πληροφορίας. (βλ. παραπάνω πως αποτυχαίνει το maxima (και καλά κάνει) όταν δώσουμε όλη την πληροφορία, αν δίναμε d=0.0000000000000000 θα μας έδινε 0, δηλαδή θα μας έλεγε ότι ισχύει η εικασία του Goldbach - μαντεύεις...χωρίς να πάρει το fields medal)

Για να μιλήσουμε για υπολογισμούς με τις πραγματικές σταθερές θα πρέπει να γνωρίζουμε τον ορισμό τους, γι' αυτό χρειάζεται η γνώση των ακολουθιών Cauchy. Όπως ακριβώς για να γράψουμε ένα πρόγραμμα για σκάκι θα πρέπει να ξέρουμε τους κανόνες του.

[alkisg]

@gbougioukas, για να απλοποιήσουμε τη συζήτηση, τελικά πιστεύεις ότι η πρόσθεση δύο οποιωνδήποτε πραγματικών αριθμών είναι επιλύσιμο πρόβλημα ή όχι;

[gbougioukas]

@gbougioukas, για να απλοποιήσουμε τη συζήτηση, τελικά πιστεύεις ότι η πρόσθεση δύο οποιωνδήποτε πραγματικών αριθμών είναι επιλύσιμο πρόβλημα ή όχι;

Ναι, είναι επιλύσιμο πρόβλημα (δεν πιστεύω, εξ' ορισμού).

[alkisg]

Άρα το d+d είναι επιλύσιμο, ενώ η δευτεροβάθμια που έχει ως συντελεστή το d δεν είναι;

[evry]

Άλκη το πρόβλημα δεν είναι οι βασικές πράξεις αν κατάλαβα καλά αλλά η ρίζα η οποία υπολογίζεται προσεγγιστικά

Άρα το d+d είναι επιλύσιμο, ενώ η δευτεροβάθμια που έχει ως συντελεστή το d δεν είναι;

[gbougioukas]

Άρα το d+d είναι επιλύσιμο, ενώ η δευτεροβάθμια που έχει ως συντελεστή το d δεν είναι;

Άλκη το πρόβλημα δεν είναι οι βασικές πράξεις αν κατάλαβα καλά αλλά η ρίζα η οποία υπολογίζεται προσεγγιστικά

Έχω ορίσει τον d ως εξής:
Ακέραιο μέρος ίσο με 0 και:
1ο δεκαδικό ψηφίο: 0 αν αριθμός 4 γράφεται ως άθροισμα δύο πρώτων, αλλιώς 1
2ο δεκαδικό ψηφίο: 0 αν αριθμός 6 γράφεται ως άθροισμα δύο πρώτων, αλλιώς 1
3ο δεκαδικό ψηφίο: 0 αν αριθμός 8 γράφεται ως άθροισμα δύο πρώτων, αλλιώς 1
...

Οπότε, ο d+d ορίζεται υπολογίζεται ως εξής (εξ' ορισμού βλ. CAUCHY’S CONSTRUCTION OF ℝ: Proposition 4.6.The operations +,⋅  in Definition 4.5(a),(b) are well-defined)

Ακέραιο μέρος ίσο με 0 και:
1ο δεκαδικό ψηφίο: 0 αν αριθμός 4 γράφεται ως άθροισμα δύο πρώτων, αλλιώς 2
2ο δεκαδικό ψηφίο: 0 αν αριθμός 6 γράφεται ως άθροισμα δύο πρώτων, αλλιώς 2
3ο δεκαδικό ψηφίο: 0 αν αριθμός 8 γράφεται ως άθροισμα δύο πρώτων, αλλιώς 2
...
Για να λύσεις την δευτεροβάθμια εξίσωση στο ℝ, κλασσικά με τον "αλγόριθμο" της διακρίνουσας πρέπει να έχεις έναν αλγόριθμο που να ελέγχει την σχέση διάταξης δύο πραγματικών σταθερών - για να ελένξεις αν η πραγματική σταθερά που λέγεται διακρίνουσα είναι μεγαλύτερη ή ίση από το 0 (για να πεις βασικά αν έχει ή δεν έχει λύσεις στο ℝ-δεν τίθεται καν θέμα προσέγγισης, υπάρχει ή δεν ύπάρχει λύση)! Άλλο πράγμα o έλεγχος της σχέσης διάταξης και άλλο η πρόσθεση. Για την συγκεκριμένη εξίσωση που παρουσίασα (Ε1) θα πρέπει να ελένξεις συγκεκριμένα την ισότητα με το 0 (δύο πραγματικοί αριθμοί είναι ίσοι αν η διαφορά τους έχει όριο το 0 - διαισθάνεται κανείς ότι αυτό δεν φαίνεται και πολύ αποφασίσιμο ). Στην εργασία μου αποδεικνύω ότι το πρόβλημα της ισότητας δύο πραγματικών σταθερών είναι μη-αποφασίσιμο.

Η σταθερά d είναι υπολογίσιμος πραγματικός όπως και ο π ή ο e. Την ίδια αναπαράσταση έχουν (ακολουθίες Cauchy). Αν στην εξίσωση Ε1 είχες τον π ή τον e δεν θα είχες πρόβλημα να την λύσεις, αλλά για τον d έχεις πρόβλημα (αυτό είναι ένδειξη είπαμε, η απόδειξη έχει να κάνει με την μη-αποφασισιμότητα του προβλήματος της ισότητας βλ. παραπάνω). Ένας αλγόριθμος, για να δικαιολογεί το όνομά του, πρέπει να υπολογίζει αποτέλεσμα για κάθε στιγμιότυπο, αλλιώς πρέπει να αναφέρει ρητά τον όποιο περιορισμό του συνόλου των στιγμιοτύπων).

[apoldem]

Ο ορισμός του d πληρεί τα κριτήρια της ακολουθίας Cauchy, συνεπώς είναι ένας πραγματικός αριθμός. Δεν έχει καμία διαφορά από τους ορισμούς άλλων πραγματικών αριθμών, π.χ. μπορώ να υπολογίσω μια προσέγγιση με όσα δεκαδικά ψηφία θέλω και επίσης μπορώ να κάνω όλες τις βασικές πράξεις (το αποτέλεσμα της πράξης είναι πάλι μια ακολουθία Cauchy, δλδ ένας άλλος πραγματικός αριθμός). Η τετραγωνική ρίζα ορίζεται μέσω των βασικών πράξεων. Νομίζω ότι δεν θα έχουμε πρόβλημα να ορίσουμε και την τετραγωνική ρίζα του d.

Το πρόβλημα είναι ότι δεν μπορούμε να τον συγκρίνουμε με το μηδέν. Δεν ξέρω πόσο σημαντικό είναι αυτό για τους μαθηματικούς. Πάντως για τον δικό μας κλάδο δεν δημιουργείται κανένα θέμα. Όλοι οι αλγόριθμοι ισχύουν, απλώς βάζουμε d στην θέση του π ή του e. Αν ο αλγόριθμος πρέπει να ελέγξει αν το d είναι μηδέν, τότε βάζουμε ένα if (d==0) και τελειώνουμε.

Θα σε συμβούλευα να κάνεις μια ερώτηση στο Quora. Θα σου απαντήσουν επαγγελματίες μαθηματικοί που κατέχουν καλά αυτό το topic. Σ' αυτό το φόρουμ δεν νομίζω να μπορεί κανείς να βοηθήσει περισσότερο.

[alkisg]

Η αναπαράσταση στον υπολογιστή πρέπει να γίνεται όχι μόνο σε πεπερασμένο χώρο, αλλά και σε πεπερασμένο χρόνο. Εάν χρειάζεσαι απειροσειρά/άπειρο χρόνο εκτέλεσης για τον υπολογισμό ενός αριθμού ή μιας βασικής πράξης ή μιας σύγκρισης, τότε πλέον δεν μιλάς για αλγορίθμους.

Συνεχίζοντας το παράδειγμα με τις προσθέσεις, έστω ότι ορίζω τον αριθμό α=0.99999 (περίοδος) και θέλω να τον προσθέσω με το "d". Ποιο θα είναι το πρώτο ψηφίο του αποτελέσματος; 1 ή 0;
Μήπως τώρα και η πρόσθεση δύο πραγματικών έγινε μη επιλύσιμη;

[apoldem]

Το πρόβλημα με το d δεν βλέπω να αφορά τους υπολογιστές. Για τον κλάδο μας δύο περιπτώσεις υπάρχουν:
1) Αν θέλουμε να μεταχειριστούμε το d ως πραγματικό θα χρησιμοποιήσουμε ένα πρόγραμμα όπως το mathematica. Το αποτέλεσμα της πρόσθεσης που φέρνεις ως παράδειγμα θα είναι 1+d (το 0.999.. είναι ειδική περίπτωση).
2) Αν θέλουμε αριθμητική επίλυση έκφρασης που περιέχει το d, τότε θα πάρουμε μια προσέγγιση με όσο μεγάλη ακρίβεια θέλουμε (όπως κάνουμε και με το e). Ο κανόνας για να υπολόγιζουμε οποιοδήποτε δεκαδικό ψηφίο υπάρχει. Σ' αυτή την περίπτωση βέβαια και με τα σημερινά δεδομένα το d θα είναι πάντα μηδέν.

[gbougioukas]

Το πρόβλημα είναι ότι δεν μπορούμε να τον συγκρίνουμε με το μηδέν. Δεν ξέρω πόσο σημαντικό είναι αυτό για τους μαθηματικούς. Πάντως για τον δικό μας κλάδο δεν δημιουργείται κανένα θέμα. Όλοι οι αλγόριθμοι ισχύουν, απλώς βάζουμε d στην θέση του π ή του e. Αν ο αλγόριθμος πρέπει να ελέγξει αν το d είναι μηδέν, τότε βάζουμε ένα if (d==0) και τελειώνουμε.

Όλοι οι αλγόριθμοι ισχύουν για τον δικό μας κλάδο; Που το γράφει αυτό; Αν ήταν έτσι θα ίσχυε και ο αλγόριθμος που...λύνει το halting problem. Αν δεν μπορείς να συγκρίνεις το d με το 0 πως θα βάλεις στον αλγόριθμο if(d==0);;;

Θα σε συμβούλευα να κάνεις μια ερώτηση στο Quora. Θα σου απαντήσουν επαγγελματίες μαθηματικοί που κατέχουν καλά αυτό το topic. Σ' αυτό το φόρουμ δεν νομίζω να μπορεί κανείς να βοηθήσει περισσότερο.

Δεν ζήτησα "βοήθεια" από κανένα, παρουσιάζω τους ισχυρισμούς μου με την μαθηματική αυστηρότητα που διδάχτηκα από το πρόγραμμα σπουδών που παρακολούθησα, το οποίο συμπεριλαμβάνει προτασιακό λογισμό, κατηγορηματικό λογισμό, κλασσική ανάλυση, γραμμική άλγεβρα, θεωρία πιθανοτήτων, συνδυαστική, άλγεβρα Βoole, γραμμικό προγραμματισμό, θεωρία γράφων, θεωρία υπολογισμού-αλγοριθμική πολυπλοκότητα, θεωρία αυτομάτων και τυπικών γλωσσών, γεννήτριες συναρτήσεις, θεωρία παιγνίων, java (που θα πει σύγχρονη μορφή μ-Αναδρομικών συναρτήσεων ή λογισμού Λάμδα) κλπ.

Αν αφήσουμε κατά μέρος την απόδειξή μου για την ανυπαρξία (γενικού εννοείται) αλγόριθμου, αν αυτό που λέει το βιβλίο ίσχυε, δηλαδή ότι (αποδειγμένα, πως αλλιώς;) υπάρχει δημοσιευμένος γενικός αλγόριθμος για την επίλυση της δευτεροβάθμιας εξίσωσης, τότε θα έπρεπε να υπάρχει δημοσιευμένος αλγόριθμος που να λύνει την Ε1, ή ισοδύναμα την εικασία του Goldbach.

[gbougioukas]

Το πρόβλημα με το d δεν βλέπω να αφορά τους υπολογιστές. Για τον κλάδο μας δύο περιπτώσεις υπάρχουν:
1) Αν θέλουμε να μεταχειριστούμε το d ως πραγματικό θα χρησιμοποιήσουμε ένα πρόγραμμα όπως το mathematica. Το αποτέλεσμα της πρόσθεσης που φέρνεις ως παράδειγμα θα είναι 1+d (το 0.999.. είναι ειδική περίπτωση).
2) Αν θέλουμε αριθμητική επίλυση έκφρασης που περιέχει το d, τότε θα πάρουμε μια προσέγγιση με όσο μεγάλη ακρίβεια θέλουμε (όπως κάνουμε και με το e). Ο κανόνας για να υπολόγιζουμε οποιοδήποτε δεκαδικό ψηφίο υπάρχει. Σ' αυτή την περίπτωση βέβαια και με τα σημερινά δεδομένα το d θα είναι πάντα μηδέν.

To d γράφεται ως (συγκλίνουσα) σειρά (βλ. σε προηγούμενό μου μήνυμα τον κώδικα για το maxima ) επομένως μπορείς να το βάλεις με αυτήν την μορφή σε ένα CAS. Σε κάθε περίπτωση η σχέση τον αλγορίθμων με τους πραγματικούς αριθμούς δεν σταματάει στο...floating point! Παρεμπιπτόντως, είναι ατυχής η επιλογή του ονόματος "πραγματικές" για τον ομώνυμο τύπο δεδομένων της Γλώσσας, αφού πρόκειται ουσιαστικά για ρητό τύπο δεδομένων.

[gbougioukas]

Η αναπαράσταση στον υπολογιστή πρέπει να γίνεται όχι μόνο σε πεπερασμένο χώρο, αλλά και σε πεπερασμένο χρόνο. Εάν χρειάζεσαι απειροσειρά/άπειρο χρόνο εκτέλεσης για τον υπολογισμό ενός αριθμού ή μιας βασικής πράξης ή μιας σύγκρισης, τότε πλέον δεν μιλάς για αλγορίθμους.

Συνεχίζοντας το παράδειγμα με τις προσθέσεις, έστω ότι ορίζω τον αριθμό α=0.99999 (περίοδος) και θέλω να τον προσθέσω με το "d". Ποιο θα είναι το πρώτο ψηφίο του αποτελέσματος; 1 ή 0;
Μήπως τώρα και η πρόσθεση δύο πραγματικών έγινε μη επιλύσιμη;

Η "απειροσειρά" (εξ' ορισμού η σειρά είναι άπειρη) περιγράφεται πεπερασμένα τόσο χωρικά όσο και χρονικά από μια πεπερασμένη συμβολοσειρά (βλ. τον κώδικα για maxima σε προηγούμενο μήνυμά μου της σειράς με την οποία εκφράζεται το d).

Μια χαρά επιλύσιμη παραμένει η πρόσθεση:
α=0.9999(περίοδος) = 1

Άρα η πραγματική σταθερά d+α είναι η εξής (ο παρακάτω αλγόριθμος είναι μια πεπερασμένη συμβολοσειρά):

Ακέραιο μέρος ίσο με 1 και:
1ο δεκαδικό ψηφίο: 0 αν αριθμός 4 γράφεται ως άθροισμα δύο πρώτων, αλλιώς 1
2ο δεκαδικό ψηφίο: 0 αν αριθμός 6 γράφεται ως άθροισμα δύο πρώτων, αλλιώς 1
3ο δεκαδικό ψηφίο: 0 αν αριθμός 8 γράφεται ως άθροισμα δύο πρώτων, αλλιώς 1
...

[alkisg]

Έχω αντίρρηση στο 0.99999=1, αλλά για να μην φάμε την ώρα μας με αυτό, ας αλλάξω λίγο την εκφώνηση.

Κάνε το ίδιο με το 1-d.

Ακέραιο μέρος = πόσο;
1ο δεκαδικό ψηφίο = πόσο;

Αν δεν μπορείς καν να υπολογίσεις το πρώτο ψηφίο αυτού του αριθμού, μήπως η αφαίρεση πραγματικών είναι μη επιλύσιμο πρόβλημα;