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

[gbougioukas]

@apoldem

Μ' αυτή την "λογική" έχεις λύσει και την εικασία του Goldbach:

Αν κάθε φυσικός άρτιος μεγαλύτερος του 2 γράφεται ως άθροισμα δύο πρώτων τότε ισχύει η εικασία.
Αν δεν ισχύει ότι κάθε φυσικός άρτιος μεγαλύτερος του 2 γράφεται ως άθροισμα δύο πρώτων τότε δεν ισχύει η εικασία.

[alkisg]

Η είσοδος δεν είναι μέρος του αλγορίθμου.
Άρα ο υπολογισμός της εισόδου και η εικασία του Goldbach και δεν έχουν σχέση με τον αλγόριθμο της δευτεροβάθμιας.

Αν θες να μπλέξεις τα δύο προβλήματα, μπορείς. Πες "θέλω έναν αλγόριθμο που να διερευνά την εικασία του Goldbach και μετά να βάζει το αποτέλεσμα σε μια δευτεροβάθμια".
Αλλά μην ισχυρίζεσαι ότι η δευτεροβάθμια δεν είναι επιλύσιμο πρόβλημα, όταν διατυπώνεις άλλο, σύνθετο πρόβλημα.

[gbougioukas]

@alkisg

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

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

[alkisg]

Ο υπολογισμός του d είναι ισοδύναμο πρόβλημα με τον υπολογισμό του d+1.
Αυτό δεν σημαίνει ότι η πρόσθεση δύο αριθμών είναι ανοικτό πρόβλημα.

Κάνεις σύνθεση δύο συναρτήσεων/αλγορίθμων, Δευτεροβάθμια(Goldbach()), και επειδή το αποτέλεσμά τους είναι ανοικτό, θεωρείς ότι και οι δύο αλγόριθμοι είναι ανοικτά προβλήματα. Δεν ισχύει ο συλλογισμός σου.
Είναι παρόμοιος με το "το π είναι άρρητος <=> το 3*π είναι άρρητος => το 3 είναι άρρητος", όπου προφανώς το τελευταίο σκέλος δεν ισχύει.
Άρα: Goldbach()=ανοικτό, Δευτεροβάθμια(Goldbach())=ανοικτό, αλλά Δευτεροβάθμια()=επιλύσιμο.

[gbougioukas]

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

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

Ο υπολογισμός του d είναι ισοδύναμο πρόβλημα με τον υπολογισμό του d+1.
Αυτό δεν σημαίνει ότι η πρόσθεση δύο αριθμών είναι ανοικτό πρόβλημα.

Κάνεις σύνθεση δύο συναρτήσεων/αλγορίθμων, Δευτεροβάθμια(Goldbach()), και επειδή το αποτέλεσμά τους είναι ανοικτό, θεωρείς ότι και οι δύο αλγόριθμοι είναι ανοικτά προβλήματα. Δεν ισχύει ο συλλογισμός σου.
Είναι παρόμοιος με το "το π είναι άρρητος <=> το 3*π είναι άρρητος => το 3 είναι άρρητος", όπου προφανώς το τελευταίο σκέλος δεν ισχύει.
Άρα: Goldbach()=ανοικτό, Δευτεροβάθμια(Goldbach())=ανοικτό, αλλά Δευτεροβάθμια()=επιλύσιμο.

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

[apoldem]

Α) Θα βοηθούσε λίγο να θυμηθούμε ποιο είναι το πρόβλημα της επίλυσης 2θμιας εξίσωσης:

«Με γνωστούς τους συντελεστές ενός τριωνύμου, ποιες είναι οι ρίζες του;»

Ο αλγόριθμος που έχουμε για την επίλυση τριωνύμου λύνει το παραπάνω πρόβλημα. Εσύ παρουσιάζεις ένα τριώνυμο στο οποίο δεν γνωρίζουμε όλους τους συντελεστές. Δεν υπάρχει αλγόριθμος που να λύνει τριώνυμο χωρίς να ξέρουμε τους συντελεστές.

Β) Η απόδειξη που παρουσιάζεις στο λινκ είναι λάθος. Το πρώτο-πρώτο θεώρημα που παρουσιάζεις, δλδ
«Το πρόβλημα της ισότητας δύο πραγματικών σταθερών είναι μη-αποφασίσιμο (Θ1).»
είναι λάθος. Το σκεπτικό σου στηρίζεται στο ότι μια μηχανή δεν μπορεί να αναπαραστήσει/χειριστεί/αποθηκεύσει τους πραγματικούς αριθμούς (ούτε και τους ρητούς μπορεί, αλλά ούτε και τους ακέραιους). Είναι ο γνωστός κανόνας στον προγραμματισμό:
«Ποτέ μην ζητάτε από τον επεξεργαστή να ελέγξει ισότητα μεταξύ πραγματικών αριθμών. Ο έλεγχος θα επιστρέφει σχεδόν πάντα ΨΕΥΔΕΣ.»
Αυτό έχει να κάνει με τον τρόπο αναπαράστασης των πραγματικών αριθμών. Δεν είναι περιορισμός της μηχανής. Η μηχανή είναι αξεπέραστη στο να συγκρίνει αν δύο σύμβολα είναι ίσα, οπότε δεν μπορούμε να λέμε ότι η σύγκριση (του οτιδήποτε αναπαριστούν τα σύμβολα) είναι μη-αποφασίσιμο πρόβλημα.
Οι υπολογιστές δεν έχουν ιδέα από μαθηματικά. Χειρίζονται σύμβολα. Εμείς αποφασίζουμε τι αναπαριστούν τα σύμβολα, ποιες πράξεις γίνονται μεταξύ των συμβόλων και τι αποτέλεσμα δίνει η κάθε πράξη. Μπορούμε να αντιστοιχίσουμε το π σε ένα σύμβολο, να του μάθουμε να κάνει πράξεις με το π και να ζητάμε όποτε θέλουμε να συγκρίνει έναν οποιοδήποτε αριθμό με το π και να παίρνουμε το σωστό αποτέλεσμα, μεγαλύτερο, μικρότερο ή ίσο.

Δες πως κάνει πράξεις με πραγματικούς αριθμούς το Maxima (open source) ή το Mathematica (commercial). Ξέχνα λιγάκι την δυαδική αναπαράσταση των αριθμών και την αριθμητική επίλυση τύπων και εξισώσεων.

[evry]

Τελευταία χρησιμοποιώ Type 2 Turing Machines. Τα πάνε πολύ καλά με τους πραγματικούς αριθμούς 

https://books.google.gr/books?id=3tejKrkWkD8C&lpg=PA114&ots=CNuz2G0rCe&dq=what%20is%20a%20type-2%20machine%20turing&hl=el&pg=PA114#v=onepage&q=what%20is%20a%20type-2%20machine%20turing&f=false

https://books.google.gr/books?id=47SKAD5HvXsC&lpg=PA135&ots=HDRLjTKCnh&dq=what%20is%20a%20type-2%20machine%20turing&hl=el&pg=PA135#v=onepage&q=what%20is%20a%20type-2%20machine%20turing&f=false

Δεν είναι κάτι καινούργιο ότι η ισότητα μεταξύ πραγματικών είναι ένα μη υπολογίσιμο πρόβλημα (βλέπε θεώρημα Richardson)
https://en.wikipedia.org/wiki/Richardson's_theorem

Ωστόσο με αυτό το σκεπτικό όλα τα προβλήματα που περιλαμβάνουν υπολογισμούς από τους οποίους μπορεί να προκύψουν πραγματικοί αριθμοί θα ήταν μη υπολογίσιμα και άρα μη επιλύσιμα ενώ όλοι ξέρουμε ότι στην πραγματικότητα λύνονται.

Γενικά όταν μιλάμε για μη υπολογισιμότητα αναφερόμαστε πιο πολύ σε προβλήματα που δεν έχουν λύση όχι λόγω της ανεπαρκούς αναπαράστασης πραγματικών αριθμών αλλά για άλλους ας μου επιτραπεί "αλγοριθμικούς" λόγους. Τέτοιο παράδειγμα είναι το halting problem.

Αυτά είναι τα όρια της θεωρίας που όμως αναγκαστικά κάποια στιγμή θα ξεπεραστούν, όπως φαίνεται στο παρακάτω άρθρο:
Continuous Turing Machine: Real Function Computability and Iteration Issues

Επίσης υπάρχει το πεδίο της computable analysis. Το παρακάτω "βιβλίο" είναι αρκετά ενδιαφέρον και επεξηγηματικό, διαβάζεται δηλαδή πιο εύκολα από άλλα.

Computable Analysis

Μια πολύ καλή εισαγωγή του ίδιου συγγραφέα φαίνεται και στο παρακάτω αρχείο που μπορείτε να κατεβάσετε και λογικά σε αυτό βασίστηκε το βιβλίο
A simple introduction to Computable Analysis

[gbougioukas]

Α) Θα βοηθούσε λίγο να θυμηθούμε ποιο είναι το πρόβλημα της επίλυσης 2θμιας εξίσωσης:

«Με γνωστούς τους συντελεστές ενός τριωνύμου, ποιες είναι οι ρίζες του;»

Ο αλγόριθμος που έχουμε για την επίλυση τριωνύμου λύνει το παραπάνω πρόβλημα. Εσύ παρουσιάζεις ένα τριώνυμο στο οποίο δεν γνωρίζουμε όλους τους συντελεστές. Δεν υπάρχει αλγόριθμος που να λύνει τριώνυμο χωρίς να ξέρουμε τους συντελεστές.

Η πραγματική σταθερά d είναι "γνωστή" όσο είναι και η πραγματική σταθερά π: είναι υπολογίσιμοι πραγματικοί (computable reals) και οι δύο. Για το πως ορίζεται μία πραγματική σταθερά βλ. την κλασσική κατασκευή του ℝ ως κλάσεις ισοδυναμίας ακολουθιών Cauchy.

Η απόδειξη που παρουσιάζεις στο λινκ είναι λάθος. Το πρώτο-πρώτο θεώρημα που παρουσιάζεις, δλδ
«Το πρόβλημα της ισότητας δύο πραγματικών σταθερών είναι μη-αποφασίσιμο (Θ1).»
είναι λάθος. Το σκεπτικό σου στηρίζεται στο ότι μια μηχανή δεν μπορεί να αναπαραστήσει/χειριστεί/αποθηκεύσει τους πραγματικούς αριθμούς ...

Οι πραγματικοί αριθμοί δεν είναι σύμβολα, αλλά κλάσεις ισοδυναμίας ακολουθιών (ρητών αριθμών) Cauchy. Μια ακολουθία ρητών αριθμών Cauchy μπορεί να κωδικοποιηθεί με μια (πεπερασμένη) συμβολοσειρά, και σ' αύτό βασίζεται το σκεπτικό μου, επομένως για να καταλάβεις το σκεπτικό μου, από το "(δεν μπορεί να) αναπαραστήσει/χειριστεί/αποθηκεύσει" κράτα μόνο το "(δεν μπορεί να) χειριστεί" (εννοείται κάθε πραγματική σταθερή) - στο  "(δεν μπορεί να) χειριστεί" συμπερίλαβε την αποφασισιμότητα του προβλήματος ισότητας δύο πραγματικών σταθερών (εννοείται για κάθε ζεύγος πραγματικών σταθερών).

[gbougioukas]

@evry

-Το θεώρημα Richardson δεν αφορά πραγματικές σταθερές αλλά εκφράσεις οι οποίες περιλαμβάνουν μεταβλητές. Δεν μ' ενδιαφέρει η πρωτοτυπία, όσο το επιχείρημα καθαυτό - κανένα πρόβλημα αν κάποιος άλλος έχει δημοσιεύσει κάτι παρόμοιο ή ακόμη και πλήρως "ισοδύναμο" πριν από μένα  . Για να είμαι ειλικρινής την απόδειξη που παρουσιάζω την θεωρώ σχεδόν τετριμμένη, οπότε (αν τελικά είναι ορθή) τυχούσα πρωτοτυπία θα δημιουργούσε άλλου τύπου προβληματισμούς (εξω-επιστημονικούς)...

-Τώρα, όσο γι' αυτό που λες, δηλαδή "ωστόσο με αυτό το σκεπτικό όλα τα προβλήματα που περιλαμβάνουν υπολογισμούς από τους οποίους μπορεί να προκύψουν πραγματικοί αριθμοί θα ήταν μη υπολογίσιμα και άρα μη επιλύσιμα ενώ όλοι ξέρουμε ότι στην πραγματικότητα λύνονται" θα σε προκαλέσω και σένα να λύσεις την εξίσωση Ε1 στο ℝ:

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

-Είμαι περίεργος ποια μαθηματικά ξεπερνάνε το halting problem. Μέχρι τώρα γνωρίζω μόνο την μη-αποδοχή της αρχής του αποκλειόμενου τρίτου (η οποία είναι βασικό χαρακτηριστικό των "διαισθητικών μαθηματικών"). Θα μελετήσω πάντως το άρθρο που προτείνεις "Continuous Turing Machine: Real Function Computability and Iteration Issues", δεν το είχα υπόψη μου.

[evry]

Γιώργο στο πρόβλημα που περιγράφεις ο αριθμός d = 1/9.
Θα μου πεις που το ξέρεις έχεις αποδείξει την εικασία? προφανώς όχι (ή μάλλον όχι ακόμα )
αλλά νομίζω μπορούμε να φτιάξουμε μια συνάρτηση (προγραμματιστική) η οποία θα δέχεται έναν αριθμό και θα επιστρέφει ναι αν μπορεί να γραφτεί ως άθροισμα πρώτων και όχι αν δεν μπορεί να γραφτεί. Το πρόβλημα αυτό είναι μια χαρά υπολογίσιμο για κάθε αριθμό Ν που μπορεί να αναπαραστήσει ο υπολογιστής.
Έτσι για κάθε ψηφίο που θέλεις μπορώ να καλέσω αυτή τη συνάρτηση και να πάρω το 1.
Πάλι το πρόβλημα της μη υπολογισιμότητας ανάγεται στο πρόβλημα της αναπαράστασης ενός αριθμού στον υπολογιστή και όχι σε κάτι άλλο όπως το halting problem.

[gbougioukas]

@evry

Για Ν = 4 πως θα πάρεις το 1 (αφού 2+2 = 4);

[evry]

ωχ έχεις δίκιο, το είδα ανάποδα, ότι είχες βάλει 1 για να ισχύει η εικασία, λέω και εγώ τι δουλειά έχει το 0.1111
οκ 0 τότε ή για να είμαι πιο ακριβής 0.000?? 

[gbougioukas]

Θεωρείς ότι μ' αυτόν τον τρόπο λύνεις την Ε1; Αν δεν την λύνεις πως γίνεται αυτό αφου..."υπάρχει αλγόριθμος που λύνει κάθε δευτεροβάθμια εξίσωση";;;

[evry]

Θεωρώ ότι υπολογίζω το d με την ακρίβεια που μου επιτρέπει το υπολογιστικό σύστημα που έχω.
Το υπολογίζω όπως θα υπολόγιζα και το π ή το e με τις αντίστοιχες σειρές.

[gbougioukas]

Θεωρώ ότι υπολογίζω το d με την ακρίβεια που μου επιτρέπει το υπολογιστικό σύστημα που έχω.
Το υπολογίζω όπως θα υπολόγιζα και το π ή το e με τις αντίστοιχες σειρές.

Δηλαδή, το υπολογιστικό σου σύστημα σου επιτρέπει να επεξεργάσεσαι μόνο ρητές προσεγγίσεις πραγματικών αριθμών, δηλαδή ουσιαστικά μόνο ρητούς αριθμούς. Κοίτα, υπάρχει πεπερασμένη(!!!) αναπαράσταση των πραγματικών αριθμών, που συμπιέζει χωρίς απώλειες όλη την πληροφορία γι' αυτούς, η οποία τυπικά είναι οι "κλάσεις ισοδυναμίας ακολουθιών ρητών αριθμών Cauchy" και είναι ο συνήθης ορισμός της πραγματικής σταθεράς:

CAUCHY'S CONSTRUCTION OF ℝ

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