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

[gbougioukas]

Στην σελίδα 26 του σχολικού βιβλίου αναφέρεται το πρόβλημα της επίλυσης της δευτεροβάθμιας εξίσωσης ως παράδειγμα “δομημένου” προβλήματος, δηλαδή ενός προβλήματος του οποίου η  “επίλυση προέρχεται από μια αυτοματοποιημένη διαδικασία”. Αν και το συγκεκριμένο κεφάλαιο είναι εκτός ύλης φέτος όπως και πέρυσι, πρόπερσι ήταν εντός και δεν αποκλείεται να είναι εντός και του χρόνου. Σε κάθε περίπτωση, υπάρχει μέσα στο σχολικό βιβλίο και επομένως μπορεί να κριθεί για την επιστημονική ορθότητά του. Ισχυρίζομαι, λοιπόν, ότι το δεδομένο πρόβλημα στην περίπτωση που οι συντελεστές είναι πραγματικοί και η λίστα των λύσεων αναζητείται στο ℝ, δεν είναι ούτε επιλύσιμο, ούτε πολύ περισσότερο δομημένο. Αυτό ισχύει αν οι συντελεστές είναι ακέραιοι ή ρητοί. Ωστόσο, η αναφορά στην συγκεκριμένη σελίδα του σχολικού βιβλίου δεν περιορίζει το πρόβλημα στους ρητούς συντελεστές. Στον παρακάτω σύνδεσμο παρουσιάζω την απόδειξη του ισχυρισμού μου (ανάγοντας το “πρόβλημα του τερματισμού” στο πρόβλημα της επίλυσης της δευτεροβάθμιας εξίσωσης με πραγματικούς συντελεστές στο ℝ):

Δεν υπάρχει αλγόριθμος για την επίλυση της δευτεροβάθμιας εξίσωσης με πραγματικούς συντελεστές στο ℝ

Με παρόμοιο τρόπο επεκτείνω την απόδειξη μη-επιλυσιμότητας του προβλήματος και στην περίπτωση που η λίστα των λύσεων αναζητείται στο ℂ (αυτή η εργασία είναι στα αγγλικά):

There exists no algorithm for solving the quadratic equation with real coefficients neither in ℝ nor in ℂ

[pgrontas]

Πολύ ενδιαφέρον (και το site σου):
Θα τολμήσω δύο γρήγορες παρατηρήσεις  με τον κίνδυνο να κάνω λάθος:
Oι μηχανές Turing δεν αφορούν τους πραγματικούς αριθμούς δηλαδή το R, αλλά ένα υποσύνολο τους - τους υπολογίσιμους αριθμούς ("On computable numbers with an application to the Entscheidungs problem") οι οποίο εξ ορισμού είναι αυτοί που μπορούν να υπολογιστούν από αλγόριθμο (χωρίς περατότητα).
Τελικά μήπως στον υπολογιστή πρακτικά ασχολούμαστε μόνο με τους ρητούς (λόγω της πεπερασμένης αποθήκευσης);

[alkisg]

@gbougioukas, με πολύ γρήγορη ανάγνωση, μια ερώτηση, εκεί που λες ότι:
"Με άλλα λόγια ο αλγόριθμος Α4 αποφασίζει το πρόβλημα του τερματισμού, αποτέλεσμα το οποίο έρχεται σε αντίφαση με το θεμελιώδες “θεώρημα του τερματισμού”

...λέει κανείς ότι για συγκεκριμένο αλγόριθμο, δεν μπορεί να υπάρξει άλλος αλγόριθμος που να αποφασίζει αν τερματίζει;
Να ένας αλγόριθμος:
  Γράψε "Hello world"
Να και ο αλγόριθμος που αποφασίζει αν ο προηγούμενος αλγόριθμος τερματίζει:
  Γράψε "Ναι πάντα τερματίζει"

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

Τελικά μήπως στον υπολογιστή πρακτικά ασχολούμαστε μόνο με τους ρητούς (λόγω της πεπερασμένης αποθήκευσης);

Δεν νομίζω. Νομίζω ότι ασχολούμαστε με οτιδήποτε μπορούμε να αναπαραστήσουμε ψηφιακά.
Ας μην ξεχνάμε ότι και ο άρρητος "Ρίζα(3)" είναι πεπερασμένος σαν πληροφορία. Είναι ένα string από 7 chars. Δεν μας υποχρεώνει κανείς να τον μετατρέψουμε σε δεκαδικό αριθμό για να τον αποθηκεύσουμε στον υπολογιστή, μπορούμε π.χ. να τον αναπαραστήσουμε ως record: { function="Ρίζα", parameter="3" }.
Δεν έχω δουλέψει Matlab αλλά νομίζω ότι υποστηρίζει τέτοια πράγματα και έτσι μπορεί να κάνει πράξεις με ρίζες κλπ χωρίς να χάνεται καθόλου πληροφορία με στρογγυλοποιήσεις αριθμών. Είναι λίγο πρόκληση το πώς θα υλοποιηθούν όλα αυτά (π.χ. το τετράγωνο της ρίζας να δίνει τον αρχικό αριθμό χωρίς απώλειες) αλλά σίγουρα μπορούμε σε ορισμένες περιπτώσεις να ασχολούμαστε και με άρρητους, και με μιγαδικούς και με οτιδήποτε άλλο θέλουμε, χωρίς απώλεια στην πληροφορία και με πεπερασμένο χώρο αποθήκευσης.

[gbougioukas]

@pgrontas

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

Οι μη-υπολογίσιμοι πραγματικοί είναι όμως ορίσιμοι (definable) σε κάποια τυπική μαθηματική θεωρία (formal theory) η οποία εκφράζεται με κάποια τυπική γλώσσα (formal language). Για κάθε τέτοια γλώσσα υπάρχει μια μηχανή Turing που την αναγνωρίζει. Επομένως, μ' αυτήν την έννοια βεβαίως και οι μηχανές Turing αφορούν κάθε πραγματικό αριθμό, αλλά και κάθε μαθηματική θεωρία. Το entscheidungsproblem είναι μη-αποφασίσιμο όπως απέδειξε ο Turing, υπάρχει ένα άλλο πρόβλημα όμως το οποίο είναι αποφασίσιμο και με πολύ ενδιαφέρουσες προεκτάσεις: βλ. σχετικά την επιστολή του Kurt Godel στον John von Neumann.

Φυσικά και στον υπολογιστή δεν ασχολούμαστε μόνο με ρητούς, αφού ασχολούμαστε ακόμα και με μη-υπολογίσιμους πραγματικούς σύμφωνα με την προηγούμενη παράγραφο. Βλ. σχετικά Symbolic Computation και C.A.S (Computer Algebra System). 'Ενα κλασσικό παράδειγμα (επίλυση δευτεροβάθμιας με συντελεστές που συμπεριλαμβάνουν τον υπερβατικό (και υπολογίσιμο πραγματικό) π): https://www.wolframalpha.com/input/?i=solve+x%5E2%2B%CF%80x%2B-2

[gbougioukas]

@alkisg

Ο αλγόριθμος Α4 δέχεται ως είσοδο την κωδικοποίηση σε συμβολοσειρά μιας οποιασδήποτε μηχανής Turing (ΤΜ₁) και μιας οποιασδήποτε εισόδου  (επί του αλφαβήτου εισόδου της ΤΜ₁ ) x₁ και όχι μιας συγκεκριμένης μηχανής Turing. Επομένως, φυσικά και υπάρχει αντίφαση με το θεώρημα του τερματισμού το οποίο αποδεικνύει ότι δεν υπάρχει μηχανή Turing η οποία με είσοδο την κωδικοποίηση μιας οποιασδήποτε μηχανής Turing και μιας οποιασδήποτε εισόδου της αποφασίζει αν η μηχανή τερματίζει ή όχι. Σίγουρα αυτό δεν σημαίνει ότι δεν μπορείς να αποφασίσεις για κάποια συγκεκριμένα προγράμματα όπως αυτό που παρουσιάζεις, αλλά αυτό δεν καταρρίπτει την εν λόγω απόδειξη. Ακόμα κι αν κάποιος δεν είναι ενήμερος για το θεώρημα του τερματισμού, είναι εύκολο να διαπιστώσει διαισθητικά την δυσκολία του προβλήματος, για παράδειγμα προσπαθώντας να αποφασίσει αν το  παρακάτω πρόγραμμα τερματίζει ή όχι (θεωρούμε ΕΙΝΑΙ_ΑΘΡΟΙΣΜΑ_ΔΥΟ_ΠΡΩΤΩΝ συνάρτηση που αποφασίζει αν η παράμετρος γράφεται ως άθροισμα δύο πρώτων αριθμών):

ν<- 4
ΟΣΟ ΕΙΝΑΙ_ΑΘΡΟΙΣΜΑ_ΔΥΟ_ΠΡΩΤΩΝ(ν) ΕΠΑΝΑΛΑΒΕ
     ν <- ν + 2
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

(προφανώς, αποφασίζοντας αν το παραπάνω πρόγραμμα τερματίζει αποφασίζουμε και την εικασία του Goldbach)

[pgrontas]

Φυσικά και στον υπολογιστή δεν ασχολούμαστε μόνο με ρητούς, αφού ασχολούμαστε ακόμα και με μη-υπολογίσιμους πραγματικούς σύμφωνα με την προηγούμενη παράγραφο. Βλ. σχετικά Symbolic Computation και C.A.S (Computer Algebra System). 'Ενα κλασσικό παράδειγμα (επίλυση δευτεροβάθμιας με συντελεστές που συμπεριλαμβάνουν τον υπερβατικό (και υπολογίσιμο πραγματικό) π): https://www.wolframalpha.com/input/?i=solve+x%5E2%2B%CF%80x%2B-2

Δεν νομίζω. Νομίζω ότι ασχολούμαστε με οτιδήποτε μπορούμε να αναπαραστήσουμε ψηφιακά.
Ας μην ξεχνάμε ότι και ο άρρητος "Ρίζα(3)" είναι πεπερασμένος σαν πληροφορία. Είναι ένα string από 7 chars. Δεν μας υποχρεώνει κανείς να τον μετατρέψουμε σε δεκαδικό αριθμό για να τον αποθηκεύσουμε στον υπολογιστή, μπορούμε π.χ. να τον αναπαραστήσουμε ως record: { function="Ρίζα", parameter="3" }.
Δεν έχω δουλέψει Matlab αλλά νομίζω ότι υποστηρίζει τέτοια πράγματα και έτσι μπορεί να κάνει πράξεις με ρίζες κλπ χωρίς να χάνεται καθόλου πληροφορία με στρογγυλοποιήσεις αριθμών. Είναι λίγο πρόκληση το πώς θα υλοποιηθούν όλα αυτά (π.χ. το τετράγωνο της ρίζας να δίνει τον αρχικό αριθμό χωρίς απώλειες) αλλά σίγουρα μπορούμε σε ορισμένες περιπτώσεις να ασχολούμαστε και με άρρητους, και με μιγαδικούς και με οτιδήποτε άλλο θέλουμε, χωρίς απώλεια στην πληροφορία και με πεπερασμένο χώρο αποθήκευσης.

Παραδέχομαι ότι λόγω κεκτημένης ταχύτητας το ρήμα "ασχολούμαστε" που χρησιμοποίησα ήταν υπερβολικά γενικό και άρα λάθος.
Αυτό που εννοούσα είναι ότι λογω της πεπερασμένης αποθήκευσης, τελικά αποθηκεύουμε πρωτογενώς μόνο ρητούς, δηλαδή στους πραγματικούς μέχρι κάποιο σημείο.
Δεν αναφερόμουν σε συστήματα συμβολικής επεξεργασίας τα οποία ναι μεν υποστηρίζουν (συμβολικές) πράξεις με άρρητους, αλλά αν κάποια στιγμή τις εξαντλήσεις και ζητήσεις το ριζα(3) θα πάρεις κάποια πεπερασμένη αναπαράσταση του (η οποία θα έχει περισσότερη ακρίβεια είναι αλήθεια από το αν την είχες χρησιμοποιήσει στις πράξεις αντί για το συμβολισμό).
To ίδιο βέβαια ισχύει και για τους πολύ μεγάλους ακέραιους στις γλώσσες με lazy evaluation, όπου αυτό που παίρνεις είναι μια υπόσχεση υπολογισμού και αν έχεις αρκετό χρόνο και χώρο θα πάρεις και την ακριβή τιμή.

Οι μη-υπολογίσιμοι πραγματικοί είναι όμως ορίσιμοι (definable) σε κάποια τυπική μαθηματική θεωρία (formal theory) η οποία εκφράζεται με κάποια τυπική γλώσσα (formal language). Για κάθε τέτοια γλώσσα υπάρχει μια μηχανή Turing που την αναγνωρίζει. Επομένως, μ' αυτήν την έννοια βεβαίως και οι μηχανές Turing αφορούν κάθε πραγματικό αριθμό, αλλά και κάθε μαθηματική θεωρία. [/url].

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

[gbougioukas]

@pgrontas

Οι μη-υπολογίσιμοι πραγματικοί είναι όμως ορίσιμοι (definable) σε κάποια τυπική μαθηματική θεωρία (formal theory) η οποία εκφράζεται με κάποια τυπική γλώσσα (formal language). Για κάθε τέτοια γλώσσα υπάρχει μια μηχανή Turing που την αναγνωρίζει. Επομένως, μ' αυτήν την έννοια βεβαίως και οι μηχανές Turing αφορούν κάθε πραγματικό αριθμό, αλλά και κάθε μαθηματική θεωρία.

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

Όσον αφορά τους πραγματικούς αριθμούς:

A definable number which cannot be approximated algorithmically

CAUCHY’S CONSTRUCTION OF ℝ

Όσον αφορά τα μαθηματικά γενικότερα:

Κάθε μαθηματική θεωρία είναι ένα σύνολο από αξιώματα (ή αξιωματικά σχήματα), δηλαδή συμβολοσειρές,  ένα σύνολο αποδεκτών ονομάτων μεταβλητών,  και ένα σύνολο κανόνων (προσωμοιώσιμων από μια μηχανή Turing, όσο δεν καταρρίπτεται η θέση Church-Turing, πχ modus ponens) μέσω των οποίων εξάγονται νέες συμβολοσειρές ("θεωρήματα"). Κάθε μαθηματική θεωρία είναι δηλαδή μια τυπική γλώσσα (formal language). Δεν υπάρχει αλγόριθμος ο οποίος να αποφασίζει αν ένα (οποιοδήποτε) θεώρημα ισχύει σε μια (οποιαδήποτε) θεωρία (entscheidungsproblem). Υπάρχει όμως αλγόριθμος ο οποίος αποφασίζει το ακόλουθο (NP-πλήρες, ευτυχώς ή δυστυχώς) πρόβλημα απόφασης για οποιοδήποτε θεώρημα και οποιαδήποτε πρωτοβάθμια θεωρία:
υπάρχει απόδειξη (η "απόδειξη"είναι μια συμβολοσειρά με βάση τα παραπάνω) για κάποιο θεώρημα σε κάποια θεωρία μήκους το πολύ k συμβόλων (k θετικός ακέραιος); Το πρόβλημα αυτό, μάλιστα ως προς την δυνατή ταχύτητα υπολογισμού ("πολυπλοκότητα", αν και δεν υπήρχε η έννοια την χρονική στιγμή της επιστολής), τέθηκε για πρώτη (μάλλον) φορά από τον Godel σε μια επιστολή του στον John von Neumann, και πρόκειται ουσιαστικά για μια πρώιμη διατύπωση του προβλήματος P versus NP.

υγ
Όλα αυτά βέβαια επιβεβαιώνουν το μοτό σου, το οποίο είναι και δικό μου.

[pgrontas]

υγ
Όλα αυτά βέβαια επιβεβαιώνουν το μοτό σου, το οποίο είναι και δικό μου.

Του Παπαδημητρίου είναι απλά εγώ έχω βάλει την έμφαση 

[gbougioukas]

Του Παπαδημητρίου είναι απλά εγώ έχω βάλει την έμφαση 

Creative Commons! Θα μπορούσε να είναι και θέμα επιστημονικής εργασίας...

[gbougioukas]

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

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

[apoldem]

Η επίλυση του τριωνύμου με πραγματικούς συντελεστές είναι ασφαλώς επιλύσιμο. Η λύση του είναι οι γνωστοί τύποι με τις ρίζες του τριωνύμου.

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

Η όλη διαδικασία (με τον υπολογισμό και τον έλεγχο της διακρίνουσας κτλ) είναι ο αλγόριθμος επίλυσης του τριωνύμου, ο οποίος και φυσικά πάντα τερματίζει.

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

[gbougioukas]

@apoldem

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

Δηλαδή θεωρείς ότι έχεις λύσει την εξίσωση Ε1 στο ℝ χωρίς να έχεις απαντήσει καν στο ερώτημα αν έχει πραγματικές λύσεις; Κάτι τέτοιο θεωρούνταν "λύση" στα μαθηματικά πριν από 300-400 χρόνια όταν δεν είχαν ιδέα τι είναι μ-Αναδρομική συνάρτηση και ποια η σημασία της, πχ στην κατασκευή κλάσεων ισοδυναμίας ακολουθιών Cauchy, δηλαδή έναν στάνταρ τρόπο κατασκευής του ℝ. Δεν μπορείς εν έτει 2016 να επικαλείσαι παρωχημένους ορισμούς 300-400 ετών και μάλιστα αντιφατικούς ως προς τις σύγχρονες κατακτήσεις και εξελίξεις των μαθηματικών.

[apoldem]

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

[gbougioukas]

@apoldem

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

Φιλοσοφία είναι να ισχυρίζεσαι ότι μπορείς να λύσεις την εξίσωση Ε1 στο ℝ χωρίς να μπορείς καν να απαντήσεις στο ερώτημα αν η Ε1 έχει πραγματικές λύσεις. Οπότε μάλλον εσύ βρίσκεσαι σε λάθος φόρουμ.

[apoldem]

Μπορώ πολύ εύκολα να σου απαντήσω αν η (Ε1) έχει πραγματικές λύσεις.

Αν το d είναι μηδέν τότε έχει πραγματική λύση το μηδέν.
Αν το d δεν είναι μηδέν τότε δεν έχει πραγματική λύση.

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