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

gbougioukas

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

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

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

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

pgrontas

  • Ομάδα διαγωνισμάτων 2016
  • *
  • Μηνύματα: 1315
  • There are always possibilities...
Πολύ ενδιαφέρον (και το site σου):
Θα τολμήσω δύο γρήγορες παρατηρήσεις  με τον κίνδυνο να κάνω λάθος:
Oι μηχανές Turing δεν αφορούν τους πραγματικούς αριθμούς δηλαδή το R, αλλά ένα υποσύνολο τους - τους υπολογίσιμους αριθμούς ("On computable numbers with an application to the Entscheidungs problem") οι οποίο εξ ορισμού είναι αυτοί που μπορούν να υπολογιστούν από αλγόριθμο (χωρίς περατότητα).
Τελικά μήπως στον υπολογιστή πρακτικά ασχολούμαστε μόνο με τους ρητούς (λόγω της πεπερασμένης αποθήκευσης);
A man provided with paper, pencil, and rubber, and subject to strict discipline is in effect a universal machine - Alan Turing

alkisg

  • Τεχνικός / καθαρίστρια
  • *****
  • Μηνύματα: 4879
    • alkisg@im.sch.gr
    • Ο Διερμηνευτής της ΓΛΩΣΣΑΣ
@gbougioukas, με πολύ γρήγορη ανάγνωση, μια ερώτηση, εκεί που λες ότι:
"Με άλλα λόγια ο αλγόριθμος Α4 αποφασίζει το πρόβλημα του τερματισμού, αποτέλεσμα το οποίο έρχεται σε αντίφαση με το θεμελιώδες “θεώρημα του τερματισμού”

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

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


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

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

gbougioukas

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 176
@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

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 176
@alkisg

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

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

(προφανώς, αποφασίζοντας αν το παραπάνω πρόγραμμα τερματίζει αποφασίζουμε και την εικασία του Goldbach)
« Τελευταία τροποποίηση: 19 Νοέ 2016, 06:39:40 μμ από gbougioukas »

pgrontas

  • Ομάδα διαγωνισμάτων 2016
  • *
  • Μηνύματα: 1315
  • There are always possibilities...
Φυσικά και στον υπολογιστή δεν ασχολούμαστε μόνο με ρητούς, αφού ασχολούμαστε ακόμα και με μη-υπολογίσιμους πραγματικούς σύμφωνα με την προηγούμενη παράγραφο. Βλ. σχετικά 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].
Αυτό πραγματικά πρώτη φορά το ακούω και θα ήθελα αν σου είναι εύκολο ένα σύνδεσμο για περαιτέρω μελέτη.

A man provided with paper, pencil, and rubber, and subject to strict discipline is in effect a universal machine - Alan Turing

gbougioukas

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 176
@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.

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

« Τελευταία τροποποίηση: 21 Μάρ 2017, 01:25:07 πμ από gbougioukas »

pgrontas

  • Ομάδα διαγωνισμάτων 2016
  • *
  • Μηνύματα: 1315
  • There are always possibilities...
υγ
Όλα αυτά βέβαια επιβεβαιώνουν το μοτό σου, το οποίο είναι και δικό μου.
Του Παπαδημητρίου είναι απλά εγώ έχω βάλει την έμφαση  ;)
A man provided with paper, pencil, and rubber, and subject to strict discipline is in effect a universal machine - Alan Turing

gbougioukas

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 176
Του Παπαδημητρίου είναι απλά εγώ έχω βάλει την έμφαση  ;)

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


gbougioukas

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

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





apoldem

  • Βετεράνος
  • ****
  • Μηνύματα: 86
Η επίλυση του τριωνύμου με πραγματικούς συντελεστές είναι ασφαλώς επιλύσιμο. Η λύση του είναι οι γνωστοί τύποι με τις ρίζες του τριωνύμου.

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

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

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

gbougioukas

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 176
@apoldem



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

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

apoldem

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

gbougioukas

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 176
@apoldem


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

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

apoldem

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

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

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

gbougioukas

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 176
@apoldem

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

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





alkisg

  • Τεχνικός / καθαρίστρια
  • *****
  • Μηνύματα: 4879
    • alkisg@im.sch.gr
    • Ο Διερμηνευτής της ΓΛΩΣΣΑΣ
Η είσοδος δεν είναι μέρος του αλγορίθμου.
Άρα ο υπολογισμός της εισόδου και η εικασία του Goldbach και δεν έχουν σχέση με τον αλγόριθμο της δευτεροβάθμιας.

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

gbougioukas

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 176
@alkisg


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

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

alkisg

  • Τεχνικός / καθαρίστρια
  • *****
  • Μηνύματα: 4879
    • alkisg@im.sch.gr
    • Ο Διερμηνευτής της ΓΛΩΣΣΑΣ
Ο υπολογισμός του d είναι ισοδύναμο πρόβλημα με τον υπολογισμό του d+1.
Αυτό δεν σημαίνει ότι η πρόσθεση δύο αριθμών είναι ανοικτό πρόβλημα.

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

gbougioukas

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 176
Πέρα από την απόδειξη που παρουσιάζω, αν το δεδομένο πρόβλημα είναι επιλύσιμο και μάλιστα δομημένο όπως ισχυρίζεται το βιβλίο χωρίς να περιορίζει τους συντελεστές στο σύνολο των ρητών αριθμών, τότε θα πρέπει κάποιος να γνωρίζει τον αλγόριθμο. Παρακαλείται λοιπόν όποιος τον γνωρίζει να παραθέσει την χρήση αυτού του αλγορίθμου για την επίλυση της παρακάτω εξίσωσης (Ε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

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

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

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

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

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

evry

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 3145
  • to Iterate is human to Recurse divine
Τελευταία χρησιμοποιώ Type 2 Turing Machines. Τα πάνε πολύ καλά με τους πραγματικούς αριθμούς  :D

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



What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr

gbougioukas

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

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

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

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

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

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







gbougioukas

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 176
@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", δεν το είχα υπόψη μου.
« Τελευταία τροποποίηση: 20 Νοέ 2016, 05:30:52 μμ από gbougioukas »

evry

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 3145
  • to Iterate is human to Recurse divine
Γιώργο στο πρόβλημα που περιγράφεις ο αριθμός d = 1/9.
Θα μου πεις που το ξέρεις έχεις αποδείξει την εικασία? προφανώς όχι (ή μάλλον όχι ακόμα ;))
αλλά νομίζω μπορούμε να φτιάξουμε μια συνάρτηση (προγραμματιστική) η οποία θα δέχεται έναν αριθμό και θα επιστρέφει ναι αν μπορεί να γραφτεί ως άθροισμα πρώτων και όχι αν δεν μπορεί να γραφτεί. Το πρόβλημα αυτό είναι μια χαρά υπολογίσιμο για κάθε αριθμό Ν που μπορεί να αναπαραστήσει ο υπολογιστής.
Έτσι για κάθε ψηφίο που θέλεις μπορώ να καλέσω αυτή τη συνάρτηση και να πάρω το 1.
Πάλι το πρόβλημα της μη υπολογισιμότητας ανάγεται στο πρόβλημα της αναπαράστασης ενός αριθμού στον υπολογιστή και όχι σε κάτι άλλο όπως το halting problem.
What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr

gbougioukas

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 176
@evry

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

evry

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 3145
  • to Iterate is human to Recurse divine
ωχ έχεις δίκιο, το είδα ανάποδα, ότι είχες βάλει 1 για να ισχύει η εικασία, λέω και εγώ τι δουλειά έχει το 0.1111
οκ 0 τότε ή για να είμαι πιο ακριβής 0.000????;)
What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr

gbougioukas

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

evry

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 3145
  • to Iterate is human to Recurse divine
Θεωρώ ότι υπολογίζω το d με την ακρίβεια που μου επιτρέπει το υπολογιστικό σύστημα που έχω.
Το υπολογίζω όπως θα υπολόγιζα και το π ή το e με τις αντίστοιχες σειρές.
What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr

gbougioukas

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

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

CAUCHY’S CONSTRUCTION OF ℝ

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













gbougioukas

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 176
@apoldem

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


evry

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 3145
  • to Iterate is human to Recurse divine
ο ορισμός για την πραγματική σταθερά 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) η οποία συγκλίνει. Αυτό όμως δεν σημαίνει ότι την υπολογίσαμε κιόλας.
What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr

gbougioukas

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

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

alkisg

  • Τεχνικός / καθαρίστρια
  • *****
  • Μηνύματα: 4879
    • alkisg@im.sch.gr
    • Ο Διερμηνευτής της ΓΛΩΣΣΑΣ
@gbougioukas, για να απλοποιήσουμε τη συζήτηση, τελικά πιστεύεις ότι η πρόσθεση δύο οποιωνδήποτε πραγματικών αριθμών είναι επιλύσιμο πρόβλημα ή όχι;

gbougioukas

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

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

alkisg

  • Τεχνικός / καθαρίστρια
  • *****
  • Μηνύματα: 4879
    • alkisg@im.sch.gr
    • Ο Διερμηνευτής της ΓΛΩΣΣΑΣ
Άρα το d+d είναι επιλύσιμο, ενώ η δευτεροβάθμια που έχει ως συντελεστή το d δεν είναι;

evry

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 3145
  • to Iterate is human to Recurse divine
Άλκη το πρόβλημα δεν είναι οι βασικές πράξεις αν κατάλαβα καλά αλλά η ρίζα η οποία υπολογίζεται προσεγγιστικά

Άρα το d+d είναι επιλύσιμο, ενώ η δευτεροβάθμια που έχει ως συντελεστή το d δεν είναι;
What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr

gbougioukas

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 176
Άρα το 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

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

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

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

alkisg

  • Τεχνικός / καθαρίστρια
  • *****
  • Μηνύματα: 4879
    • alkisg@im.sch.gr
    • Ο Διερμηνευτής της ΓΛΩΣΣΑΣ
Η αναπαράσταση στον υπολογιστή πρέπει να γίνεται όχι μόνο σε πεπερασμένο χώρο, αλλά και σε πεπερασμένο χρόνο. Εάν χρειάζεσαι απειροσειρά/άπειρο χρόνο εκτέλεσης για τον υπολογισμό ενός αριθμού ή μιας βασικής πράξης ή μιας σύγκρισης, τότε πλέον δεν μιλάς για αλγορίθμους.

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

apoldem

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

gbougioukas

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

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

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

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

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

gbougioukas

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

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

gbougioukas

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

Συνεχίζοντας το παράδειγμα με τις προσθέσεις, έστω ότι ορίζω τον αριθμό α=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

  • Τεχνικός / καθαρίστρια
  • *****
  • Μηνύματα: 4879
    • alkisg@im.sch.gr
    • Ο Διερμηνευτής της ΓΛΩΣΣΑΣ
Έχω αντίρρηση στο 0.99999=1, αλλά για να μην φάμε την ώρα μας με αυτό, ας αλλάξω λίγο την εκφώνηση.

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

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

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

gbougioukas

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

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

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

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

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


α=0.99999 (περίοδος) γράφεις, καταλαβαίνω ακέραιο μέρος 0 και άπειρα εννιάρια. Αυτό είναι ίσο με 1 (χωρίς αμφιβολία - για μια απλή μέθοδο απόδειξης βλ. βιβλίο μαθηματικών 1ης Γυμνασίου, σελ. 136 - αν επιμένεις να το αποδείξω).

Παραμένει επιλύσιμο πρόβλημα η αφαίρεση πραγματικών αριθμών:

Ισχύει 1 = 0.999...    ("..." σημαίνει άπειρα εννιάρια)

Άρα 1-d = 0.999... - d, το οποίο είναι ίσο με:

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



alkisg

  • Τεχνικός / καθαρίστρια
  • *****
  • Μηνύματα: 4879
    • alkisg@im.sch.gr
    • Ο Διερμηνευτής της ΓΛΩΣΣΑΣ
Ισχύει 1 = 0.999...    ("..." σημαίνει άπειρα εννιάρια)
....
Ακέραιο μέρος ίσο με 0 και

Δηλαδή το ακέραιο μέρος του 1 είναι το 0; ?!?!?!

Εγώ όμως ξέρω ότι το ακέραιο μέρος του 1 είναι το 1, άρα μόλις απέδειξες ότι 0=1; ?!?!?!

Δεν μπορείς να μιλάς προσεγγιστικά για το ακέραιο μέρος ενός αριθμού, έχει μια πολύ συγκεκριμένη ακέραια τιμή. Δεν μπορεί να είναι και 1 και 0 ταυτόχρονα.

gbougioukas

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 176
Δηλαδή το ακέραιο μέρος του 1 είναι το 0; ?!?!?!

Εγώ όμως ξέρω ότι το ακέραιο μέρος του 1 είναι το 1, άρα μόλις απέδειξες ότι 0=1; ?!?!?!

Δεν μπορείς να μιλάς προσεγγιστικά για το ακέραιο μέρος ενός αριθμού, έχει μια πολύ συγκεκριμένη ακέραια τιμή. Δεν μπορεί να είναι και 1 και 0 ταυτόχρονα.

Οι πραγματικοί αριθμοί δεν ορίζονται μονοσήμαντα ως ακολουθίες δεκαδικών ψηφίων (για αυτό άλλωστε μιλάμε για "κλάσεις ισοδυναμίας" ακολουθιών Cauchy και όχι για "ακολουθίες Cauchy"). Ο αριθμός 1.0000 είναι ίσος με με τον 0.9999...Είναι δύο διαφορετικές μορφές αναπαράστασης του ίδιου αριθμού. Αυτή είναι κλασσικά μια διαφορά των πραγματικών αριθμών από τους ακέραιους. Δες την μέθοδο απόδειξης αυτού στο βιβλίο μαθηματικών 1ης Γυμνασίου σελ 136.

gbougioukas

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 176
@alkisg

Αν δεν έχεις πρόχειρο το βιβλίο μαθηματικών της 1ης γυμνασίου google it:

https://www.google.gr/#q=1+%3D+0.999...

https://en.wikipedia.org/wiki/0.999...

gbougioukas

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 176
@alkisg

Παραθέτω μια απόδειξη:


alkisg

  • Τεχνικός / καθαρίστρια
  • *****
  • Μηνύματα: 4879
    • alkisg@im.sch.gr
    • Ο Διερμηνευτής της ΓΛΩΣΣΑΣ
@gbougioukas, δεν διαφωνώ ότι 0.9999...=1 σε μερικά συστήματα αρίθμησης των μαθηματικών (δες το λινκ για κάποια που δεν ισχύει), αλλά όπως βλέπεις και παραπάνω στην απόδειξή σου, αυτό προϋποθέτει άπειρα δεκαδικά ψηφία, που στον υπολογιστή δεν τα έχουμε (γιατί αλλιώς 10χ=9.999990, με μηδέν στο όσο-μεγάλο-θέλουμε-αλλά-περιορισμένου-μεγέθους δεκαδικό μέρος). Ισοδύναμα, στις κλασσικές αναπαραστάσεις πραγματικών αριθμών στον υπολογιστή υπάρχει πάντα ο "επόμενος πραγματικός αριθμός", ενώ στα μαθηματικά δεν υπάρχει. Αυτά δεν είναι άσχετες συζητήσεις με το αρχικό θέμα, αλλά ήθελα να τις αποφύγω γιατί είναι απόρροιες της αναπαράστασης και όχι αίτια.

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

gbougioukas

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 176
@gbougioukas, δεν διαφωνώ ότι 0.9999...=1 σε μερικά συστήματα αρίθμησης των μαθηματικών (δες το λινκ για κάποια που δεν ισχύει), αλλά όπως βλέπεις και παραπάνω στην απόδειξή σου, αυτό προϋποθέτει άπειρα δεκαδικά ψηφία, που στον υπολογιστή δεν τα έχουμε (γιατί αλλιώς 10χ=9.999990, με μηδέν στο όσο-μεγάλο-θέλουμε-αλλά-περιορισμένου-μεγέθους δεκαδικό μέρος). Ισοδύναμα, στις κλασσικές αναπαραστάσεις πραγματικών αριθμών στον υπολογιστή υπάρχει πάντα ο "επόμενος πραγματικός αριθμός", ενώ στα μαθηματικά δεν υπάρχει. Αυτά δεν είναι άσχετες συζητήσεις με το αρχικό θέμα, αλλά ήθελα να τις αποφύγω γιατί είναι απόρροιες της αναπαράστασης και όχι αίτια.

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

Σε ποια αριθμητικά συστήματα ακριβώς δεν ισχύει, γιατί το λινκ που δίνεις λέει ακριβώς το αντίθετο:

"Second, a comparable theorem applies in each radix or base. For example, in base 2 (the binary numeral system) 0.111… equals 1".

Όσο για το ποιες αναπαραστάσεις είναι κατάλληλες για υπολογιστές, είναι οι πεπερασμένες φυσικά:

Κάθε μαθηματικός ορισμός (εξ' ορισμού) είναι μια πεπερασμένη συμβολοσειρά. Άρα μπορεί να χρησιμοποιηθεί μια χαρά στον υπολογιστή. Σ' ένα σύνηθες 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);
« Τελευταία τροποποίηση: 22 Νοέ 2016, 08:44:10 μμ από gbougioukas »

alkisg

  • Τεχνικός / καθαρίστρια
  • *****
  • Μηνύματα: 4879
    • alkisg@im.sch.gr
    • Ο Διερμηνευτής της ΓΛΩΣΣΑΣ
Στην τρίτη παράγραφο το λέει, "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."

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

evry

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 3145
  • to Iterate is human to Recurse divine
Κάποιες παρατηρήσεις, αν και δεν έχω καθόλου χρόνο, αλλά το θέμα έχει ενδιαφέρον

@alkisg

Παραθέτω μια απόδειξη:


1η παρατήρηση
Η παραπάνω απόδειξη δεν θα έλεγα ότι είναι ακριβώς αυστηρή για να μην πάω στο άλλο άκρο και πω ότι είναι λάθος.
Το λέω αυτό διότι στα μαθηματικά δεν υπάρχει το σύμβολο "τελίτσες" .......
(το ότι είναι μέσα στο σχολικό βιβλίο δεν μου λέει τίποτα)
Το πρόβλημα είναι ο πολλαπλασιασμός που κάνεις ο οποίος δεν έχει οριστεί πριν γιατί άλλο να πολλαπλασιάζεις γνωστούς αριθμούς και άλλο τους συγκεκριμένους με το "τελίτσα"-notation. (π.χ. πόσο κάνει 0.9999999999... + 0.00000000000...1 ? ή πόσο κάνει 0.999999... x 9?)
π.χ. εγώ γράφω τον αριθμό 0.0000...1 με άπειρα ψηφία 0 και το τελευταίο 1. Πως ορίζεται?

Ουσιαστικά οι τελείες κρύβουν μια απειροσειρά ή για να είμαι πιο ακριβής ένα όριο μιας σειράς.

Το ότι ο συγκεκριμένος συμβολισμός 0.9999.. είναι προβληματικός φαίνεται και από κάτι άλλο. Ότι εδώ έχουμε τον ίδιο αριθμό να έχει δυο διαφορετικές δεκαδικές αναπαραστάσεις όπως είπες και εσύ προηγουμένως. Σίγουρα κάτι δεν πάει καλά λοιπόν. (Αλήθεια κατά πόσο ορίζεται αυστηρά η δεκαδική αναπαράσταση αριθμού με άπειρα ψηφία?? Λογικά αυτό είναι το πρόβλημα που ανέφερε ο Άλκης παραπάνω με τα αριθμητικά συστήματα.)
Αυτό που δεν πάει καλά είναι ο συμβολισμός με τις τελείες που ξεγελάει και σε κάνει να νομίζεις ότι πρόκειται για έναν αριθμό με τα ψηφία αυτά. Στην πραγματικότητα κάνοντας πράξεις με αυτόν τον αριθμό είναι σαν να κάνουμε πράξεις με το άπειρο.

Το ότι η αναπαράσταση αυτή έχει πρόβλημα δεν το λέω μόνο εγώ αλλά και άλλοι. π.χ. η παρακάτω εργασία παρουσιάζει ενδιαφέρον
When is .999... less than 1?

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++
  1. Goldbach = True
  2. for (i=2; Goldbach ; i+=2)
  3.    Goldbach = False
  4.    for (j=2; j<i; i++)
  5.          if (j is prime and i–j is prime)
  6.                  Goldbach = True
  7.    if not Goldbach  return False;
  8. return Goldbach;
  9.  

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

ΥΓ. Για την ιστορία η εικασία του Goldbach ισχύει για όλους τους αριθμούς μέχρι τον 4 × 1018 οπότε στον "πραγματικό" κόσμο μάλλον ισχύει
What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr

gbougioukas

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 176
Στην τρίτη παράγραφο το λέει, "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."

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

Η ισότητα 0.999...=1 ισχύει στο σύνολο των πραγματικών αριθμών. Για πραγματικούς αριθμούς μιλάμε τόση ώρα, όχι για...υπερπραγματικούς. "Στους υπολογιστές" δεν "χρησιμοποιούμε" γενικά πραγματικούς αριθμούς περιορισμένης ακριβείας, διότι στους υπολογιστές υπάρχει και το CAS (Computer Algebra System) και το  ATP (Automated Theorem Proving) και πολλά άλλα. Αν η δική σου επαφή με τους υπολογιστές έχει να κάνει μόνο με πραγματικούς περιορισμένης ακριβείας, καλό είναι να μην γενικεύεις έτσι αυθαίρετα  :)

gbougioukas

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 176
@Evry
Θα μπορούσε αντί για την σημειογραφία της ακολουθίας δεκαδικών ψηφίων για τους πραγματικούς αριθμούς, να χρησιμοποιώ ακολουθίες Cauchy, ο λόγος που δεν το κάνω είναι για επικοινωνιακούς λόγους, εφόσον αντιλαμβάνομαι ότι οι συνομιλητές μου δεν είναι εξοικειωμένοι με το αντικείμενο. Ωστόσο, δεν υπάρχει καμιά αντίφαση ανάμεσα στις δύο σημειογραφίες, είναι σχεδόν ισοδύναμες. Η σημειογραφία της ακολουθίας ψηφίων εγείρει αντιρρήσεις γιατί δεν συνοδεύεται από την μαθηματική αυστηρότητα που χαρακτηρίζει τις ακολουθίες Cauchy. Αυτή είναι και η προβληματική της εργασίας στην οποία παραπέμπεις. Οι αντιρρήσεις που παρουσιάζεις εσύ, είναι ανεξάρτητες σημειογραφίας*, δηλαδή αμφισβητείς και την αυστηρά ορισμένη κατασκευή των πραγματικών ως κλάσεις ισοδυναμίας ακολουθιών Cauchy με τον ορισμό των πράξεων της πρόσθεσης και του πολλαπλασιασμού και το ότι πολλές ακολουθίες Cauchy (αυτές συνιστούν μια κλάση ισοδυναμίας) αντιστοιχούν σε έναν πραγματικό αριθμό. Είναι δικαίωμά σου αν θέλεις να ορίσεις διαφορετικά τους πραγματικούς αριθμούς, από την μεριά μου έκανα αυτό το ποστ στο πλαίσιο που ορίζει με αυστηρότητα η κατασκευή των πραγματικών με κλάσεις ισοδυναμίας ακολουθιών Cauchy. Θα χαρώ πολύ να δω μια καινούργια κατασκευή των πραγματικών, όποτε την κάνεις let me know  :)

(edit)
* Για να το διατυπώσω λίγο καλύτερα:
Τόσο στην λιγότερο τυπική σημειογραφία ακολουθίας ψηφίων (οποιασδήποτε βάσης, δεκαδικό, δυαδικό κλπ) όσο και στην αυστηρότερη σημειογραφία των ακολουθιών Cauchy, έχουμε να κάνουμε τόσο με άπειρα αθροίσματα και πολλαπλασιασμούς, όσο και με πολλαπλές αναπαραστάσεις του ίδιου αριθμού.
« Τελευταία τροποποίηση: 20 Δεκ 2016, 03:18:20 μμ από gbougioukas »

evry

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 3145
  • to Iterate is human to Recurse divine
Θα χαρώ πολύ να δω μια καινούργια κατασκευή των πραγματικών, όποτε την κάνεις let me know  :)
Δεν χρειάζεται, υπάρχουν καμιά 20αριά διαφορετικές κατασκευές των πραγματικών κάποιες από τις οποίες είναι και σχετικά καινούργιες.
The Real Numbers - A Survey of Constructions
What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr

gbougioukas

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 176
@evry, @alkisg
Δεν χρειάζεται, υπάρχουν καμιά 20αριά διαφορετικές κατασκευές των πραγματικών κάποιες από τις οποίες είναι και σχετικά καινούργιες.
The Real Numbers - A Survey of Constructions

Και υπάρχει κάποια από αυτές θεωρείς η οποία έρχεται σε αντίφαση με το ότι 0.999... = 1; Ή μήπως σε κάποια από αυτές η πρόσθεση και ο πολλαπλασιασμός έχουν... "πεπερασμένο" χαρακτήρα; Πως θα γινόταν άραγε αυτό, μήπως με την άρνηση του αξιώματος του ελάχιστου άνω φράγματος (Least Upper Bound); Μα, τότε δεν θα μιλούσαμε για πραγματικούς, αλλά για ρητούς. Η αποδεκτή από σένα (και του @alkisg) αριθμητική, από όσο καταλαβαίνω από τα λεγόμενά σας (αν κάνω λάθος διόρθώστε με), είναι η αριθμητική μεταξύ ρητών. Τότε, όμως γιατί να μην τους λέμε με το όνομά τους; Γιατί αυτό το μπέρδεμα;

gbougioukas

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 176
@evry

Όσον αφορά τις πολλαπλές αναπαραστάσεις του ίδιου αριθμού, ειλικρινά δεν καταλαβαίνω γιατί σου προκαλούν τόση εντύπωση και γιατί είναι πρόβλημα. Συμβαίνει και στους ρητούς αριθμούς: 1/2 = 2/4.

gbougioukas

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 176

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++
  1. Goldbach = True
  2. for (i=2; Goldbach ; i+=2)
  3.    Goldbach = False
  4.    for (j=2; j<i; i++)
  5.          if (j is prime and i–j is prime)
  6.                  Goldbach = True
  7.    if not Goldbach  return False;
  8. return Goldbach;
  9.  

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

ΥΓ. Για την ιστορία η εικασία του Goldbach ισχύει για όλους τους αριθμούς μέχρι τον 4 × 1018 οπότε στον "πραγματικό" κόσμο μάλλον ισχύει

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

ένας πραγματικός αριθμός είναι μια κλάση ισοδυναμίας ακολουθιών (ρητών αριθμών) Cauchy και ο αριθμός μπορεί να αναπαρασταθεί με ένα μέλος της κλάσης. Για παράδειγμα, ο αριθμός π μπορεί να αναπαρασταθεί με την ακόλουθη ρητή ακολουθία Cauchy:

3,   3.1,   3.14 ,  3.141,   3.1415,  3.14159,  ....

Υπάρχει αλγόριθμος που παράγει τον νιοστό όρο της ακολουθίας, ο οποίος είναι μια πεπερασμένη συμβολοσειρά. Ο αλγόριθμος αυτός είναι εξ' ορισμού η ακολουθία, άρα είναι εξ' ορισμού μια μορφή αναπαράστασης του  πραγματικού αριθμού. Αν ο πραγματικός αριθμός δεν είναι υπολογίσιμος, είναι ορίσιμος, που σημαίνει ότι ορίζεται σε κάποια μαθηματική θεωρία. Ο πραγματικός αριθμός αυτός τότε είναι η πεπερασμένη συμβολοσειρά του ορισμού του στην μαθηματική θεωρία στην οποία ορίζεται. That's it. Δεν υπάρχει κάτι άλλο για να υπολογίσεις, αυτό που λες εσύ "υπολογισμό πραγματικού αριθμού" λέγεται κοινώς ρητή προσέγγιση, αλλά άπαξ και κάνεις κάτι τέτοιο δεν είσαι πια στο σύμπαν των πραγματικών, αλλά των ρητών.

Πως ορίζεται η πρόσθεση και ο πολλαπλασιασμός πραγματικών:

Ο πραγματικός αριθμός e αναπαριστάνεται με τη ρητή ακολουθία Cauchy:

2,   2.7,   2.71,   2.718,   2.7182,   2.71828, ...

Ο πραγματικός αριθμός π+e ορίζεται ως εξής:

2+3,   3.1 + 2.7,   3.14 + 2.71,   3.141 + 2.718, 3.1415 + 2.7182, 3.14159 + 2.71828, ...

Ο αλγόριθμος που κάνει το παραπάνω είναι ο πραγματικός αριθμός π+e. That's it.

Αναλόγως ορίζεται ο πολλαπλασιασμός πραγματικών.

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

Για την εικασία του Goldbach:

Ο αλγόριθμος που παρουσιάζεις δεν πρόκειται να φτάσει ποτέ στην γραμμή 8. Είτε θα επιστρέψει false στην γραμμή 7, είτε δεν θα τερματίσει. Για να είναι αλγόριθμος που αποφασίζει την εικασία του Goldbach θα πρέπει να μπορεί να επιστρέψει και true (just in case). Η άρνηση της εικασίας του Goldbach είναι ημι-αποφασίσιμη, αλλά δεν είναι αποδειγμένα αποφασίσιμη, αυτό είναι το πρόβλημα και το πρόβλημα δεν είναι η λύση.

υγ
"Ιn mathematics you don't understand things. You just get used to them"- John von Neumann

« Τελευταία τροποποίηση: 21 Μάρ 2017, 01:54:57 πμ από gbougioukas »