Μπορείς να βρεις τον κρυμμένο αριθμό;

Πρόβλημα 1

Μία/Ένας φίλ-η/ος σας σας προτείνει το ακόλουθο παιχνίδι:

«Έχω γράψει έναν φυσικό αριθμό σ’ ένα χαρτί. Μπορείς να βρεις τον αριθμό κάνοντας όσες ερωτήσεις θέλεις της μορφής «είναι ο αριθμός k;», όπου k οποιοσδήποτε φυσικός αριθμός; Εννοείται θα απαντήσω ειλικρινά σε κάθε ερώτησή σου».

Περιγράψτε έναν αλγόριθμο ο οποίος σύμφωνα με τις παραπάνω υποθέσεις βρίσκει (οπωσδήποτε) τον κρυμμένο αριθμό.

Λύση

Είναι ο αριθμός 0;

Είναι ο αριθμός 1;

Είναι ο αριθμός 2;

Πρόβλημα 2

Θεωρείστε το Πρόβλημα 1 με τη διαφορά ότι αντί για φυσικό αριθμό ο κρυμμένος αριθμός είναι ακέραιος.

Λύση

Είναι ο αριθμός 0;

Είναι ο αριθμός 1;

Είναι ο αριθμός -1;

Είναι ο αριθμός 2;

Είναι ο αριθμός -2;

Ασκήσεις για εμβάθυνση

1) Θεωρείστε το Πρόβλημα 1 με τη διαφορά ότι αντί για φυσικό αριθμό ο κρυμμένος αριθμός είναι ρητός. Θεωρείστε ότι ένας ρητός αριθμός είναι ένα κλάσμα όπου ο αριθμητής είναι ακέραιος και ο παρονομαστής μη-μηδενικός ακέραιος. Αφού περιγράψετε τον αλγόριθμο, υλοποιήστε τον σε Γλώσσα, έτσι ώστε ο/η φίλ-ος/η σας να μπορεί να παίξει το παιχνίδι με το πρόγραμμά σας στον υπολογιστή.

2) Αποδεικνύεται ότι ισχύει το παρακάτω θεώρημα:

«Δεν υπάρχει αλγόριθμος παρόμοιος με τους παραπάνω (δηλαδή ο οποίος να απαριθμεί τους αριθμούς του συνόλου στο οποίο ανήκει ο κρυμμένος αριθμός) που να λύνει το αντίστοιχο του προβλήματος 1, εάν ο κρυμμένος αριθμός είναι πραγματικός»

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

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

download pdf

last update: 10/24/2016

Σημείωση: το παρακάτω να μην ληφθεί υπόψη από τους υποψήφιους για το μάθημα της Πληροφορικής στις Πανελλαδικές εξετάσεις. Αυτή η εργασία απαιτεί πληροφορικό και μαθηματικό υπόβαθρο το οποίο δεν καλύπτεται από τα σχολικά βιβλία.

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

Giorgos Bougioukas, 2016

georgebougioukas@yahoo.com

Abstract

This paper proves that the problem of the equality of two real constants is undecidable and as a consequence there exists no algorithm for solving the (univariate) quadratic equation with real coefficients neither in ℝ nor in ℂ.

1. Definitions and assumptions

a) An algorithm is a Turing machine.

b) Assume that an algorithm (A1) for solving the quadratic equation with real coefficients in ℝ necessarily gives an output that implies the decidability of the decision problem “is there a real solution for the given equation?” (P1), e.g:

a list, empty if there exists no real solution for the given equation, with up to two (distinct) elements, otherwise.

c) Assume that an algorithm (A2) for solving the quadratic equation with real coefficients in ℂ necessarily gives an output that implies the decidability of the decision problem “has the given equation exactly one solution?” (P2), e.g:

a list, with one element if the given equation has exactly one solution, with two elements, if the given equation has exactly two (distinct) solutions.

2. The problem of the equality of two real constants is undecidable (Thm1)

Proof

Let C(TM) be a string that encodes a Turing machine TM. For every Turing machine TM and for every input string (on the input alphabet of TM) x consider the following series:

p1

The series above converges in ℝ as 10-khC(TM),x(k)≤10-k holds for every natural number k1 and the series of the sequence 10-k converges as geometric series with common ratio 10-1 for which it holds that |10-1|<1. Therefore, for every Turing machine TM and for every input string (on the input alphabet of TM) x the following lemma holds:

p2

Obviously, for every Turing machine TM and for every input string (on the input alphabet of TM) x the following lemma also holds:

p3

Consider a Turing machine TM1 on input (on the input alphabet of TM1) x1. Assuming there exists an algorithm (A3) that decides whether or not two real constants are equal,  it follows that there exists another algorithm (A4) that:

a) simulating the algorithm A3 decides whether or not it holds that (the first member of the equality below is a real constant by L1):

p

b) via the previous result and L2 decides whether or not the Turing machine TM1 on input x1 halts.

In other words, the algorithm A4 decides the halting problem, a result that contradicts Turing’s “halting theorem” (Halatsis, 2003). We reached a contradiction because we assumed that there exists an algorithm such A3. Therefore, there exists no such algorithm.

3. There exists no algorithm such A1

Proof

Assuming that there exists an algorithm such A1, via the assumption b) in section 1, it follows that there exists another algorithm (A5) that simulating the former, given any quadratic equation with real coefficients, decides the decision problem P1. If the form of output of the algorithm A1 is identical with the one in the example of the assumption b) in section 1, then the algorithm A5 decides P1 as follows:

– If the algorithm A1 gives as output a non-empty list – i.e there exists a real solution for the given equation – then gives as output “True”.

– Otherwise, if the algorithm A1 gives as output an empty list – i.e there exists no real solution for the given equation – then gives as output “False”.

Let r,s be real constants and d=|s-r|. Consider the following quadratic equation with real coefficients:

p6

Given an instance of the problem P1 consisting of E1, the algorithm A5 gives the following output:

– Either “True”, i.e there exists a real solution for E1 – therefore, letting Δ be the discriminant of E1:

p7

– Or “False”, i.e there exists no real solution for E1 – therefore, letting Δ be the discriminant of E1:

p8

The real constants r and s have no particular properties. The same is true for the algorithm A5, except that it uses the output of the algorithm A1, which has also no particular properties, except the assumed form of its output. Therefore, for all constants s, r ∈ ℝ the equation E1 can be constructed and given as input to the algorithm A5 whose output then implies that either s=r or s≠r, which contradicts with Thm1. We reached a contradiction because we assumed that there exists an algorithm such A1. Therefore, there exists no such algorithm. ▪

4. There exists no algorithm such A2

Proof

Assuming that there exists an algorithm such A2, via the assumption c) in section 1, it follows that there exists another algorithm (A6) that simulating the former, given any quadratic equation with real coefficients, decides the decision problem P2. If the form of output of the algorithm A2 is identical with the one in the example of the assumption c) in section 1, then the algorithm A6 decides P2 as follows:

– If the algorithm A2 gives as output a list with one element, then gives as output “True”.

– Otherwise, if the algorithm A2 gives as output a list with two elements, then gives as output “False”.

Let r,s be real constants and d=|s-r|. Consider the quadratic equation with real coefficients E1.

Given an instance of the problem P2 consisting of E1, the algorithm A6 gives the following output:

– Either “True”, i.e there exists exactly one complex solution for E1 in ℂ– therefore, letting Δ be the discriminant of E1:

p9

– Or “False”, i.e there exist exactly two (distinct) complex solutions for E1 in – therefore, letting Δ be the discriminant of E1:

p10

The real constants r and s have no particular properties. The same is true for the algorithm A6, except that it uses the output of the algorithm A2, which has also no particular properties, except the assumed form of its output. Therefore, for all constants s, r ∈ ℝ the equation E1 can be constructed and given as input to the algorithm A6 whose output then implies that either s=r or s≠r, which contradicts with Thm1. We reached a contradiction because we assumed that there exists an algorithm such A2. Therefore, there exists no such algorithm. ▪

References

Halatsis C. (2003). Themeleioseis Epistimis I/Υ, Volume II – Theoria Ypologismou. Patras, Hellenic Open University.

Περικοπή στα ν δεκαδικά ψηφία

Πρόβλημα

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

Λύση

perikopi1

(Η απόδειξη ορθότητας παραλείπεται ως άσκηση)

Σχόλιο

Η συνάρτηση Α_Τ χρησιμοποιείται παραπάνω στην περίπτωση της αρνητικής πραγματικής παραμέτρου, διότι από τα αναφερόμενα στο σχολικό βιβλίο προκύπτει ασάφεια για την συνάρτηση Α_Μ όταν η παράμετρος είναι αρνητική.

 Άσκηση για εμβάθυνση

Χρησιμοποιώντας την λογική του αλγορίθμου της παραπάνω λύσης, γράψτε μια συνάρτηση που να στρογγυλοποιεί έναν δεδομένο πραγματικό αριθμό σε δεδομένο πλήθος δεκαδικών ψηφίων σύμφωνα με την μέθοδο «μισό-πάνω» (half -(round)up).

Πίνακας προτεραιότητας (ιεραρχίας) τελεστών Γλώσσας*

prec

*Σύμφωνα με τις Οδηγίες Μελέτης Μαθητή (σελ.10 και σελ. 12). Το βιβλίο μαθητή της ΑΕΠΠ δεν καθορίζει προτεραιότητα μεταξύ των λογικών τελεστών.

Ταληράκια

Γράψτε ένα πρόγραμμα σε Γλώσσα το οποίο να επιλύει το ακόλουθο πρόβλημα:

Θεωρείστε δύο (ίσως φανταστικούς) τύπους κερμάτων αξίας α1 και α2 λεπτών, όπου α1 και α2 είναι οποιοιδήποτε θετικοί ακέραιοι με τον περιορισμό α1α2. Θεωρείστε ακόμη έναν μη-αρνητικό ακέραιο c. Υπάρχει τρόπος επιλέγοντας κάποια ποσότητα (ίσως 0) από το ένα κέρμα και κάποια ποσότητα (ίσως 0) από το άλλο, το άθροισμα των αξιών αυτών των κερμάτων να είναι ίσο με c;

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

Παράδειγμα:

Για αξίες κερμάτων 5 και 7 υπάρχει τρόπος να σχηματιστεί το ποσό 17, αλλά δεν υπάρχει τρόπος να σχηματιστεί το ποσό 23.

Λύση

psila

Η απόδειξη ορθότητας παραλείπεται ως άσκηση.

Ιστορικό σημείωμα

Το παραπάνω πρόβλημα στην γενική του μορφή, δηλαδή όχι μόνο για δύο τύπους κερμάτων, αλλά για οποιοδήποτε πεπερασμένο (θετικό ακέραιο) πλήθος κερμάτων (ανά δύο με άνισες αξίες) είναι γνωστό ως εκδοχή εφικτότητας του προβλήματος “κάνω ψιλά” (Change Making Problem – CMP). Ο καλύτερος αλγόριθμος ο οποίος έχει βρεθεί μέχρι τώρα για το τελευταίο αυτό πρόβλημα είναι πολύ αργός για την ανθρώπινη κλίμακα χρόνου για είναι χρήσιμος. Αν καταφέρνατε να βρείτε έναν «γρήγορο» αλγόριθμο γι’ αυτό το πρόβλημα, θα κερδίζατε το βραβείο του ενός εκατομμυρίου δολαρίων του Ινστιτούτου Μαθηματικών Clay, καθώς θα είχατε λύσει το μεγαλύτερο (ίσως) πρόβλημα πληροφορικής/μαθηματικών της εποχής μας και (ίσως) όλων των εποχών: το πρόβλημα “P versus NP”.

Άσκηση για εμβάθυνση

Θεωρείστε το παραπάνω πρόβλημα με τρεις (αντί για δύο) τύπους κερμάτων (με αξίες ανά δύο άνισες). Γράψτε ένα πρόγραμμα σε Γλώσσα για την επίλυση αυτού του προβλήματος.

Το κόσκινο του Ερατοσθένη

Τελευταία ενημέρωση: 5/10/2016

Πρόβλημα

Το κόσκινο του Ερατοσθένη είναι ένας αλγόριθμος για την ανεύρεση όλων των πρώτων αριθμών οι οποίοι είναι μικρότεροι ή ίσοι από κάποιον δεδομένο φυσικό αριθμό – σημειώνεται ότι δεν υπάρχει πρώτος αριθμός μικρότερος του 2. Ο αλγόριθμος αυτός για χαρτί και μολύβι, δεδομένου ενός φυσικού αριθμού n για τον οποίο ζητείται να βρεθούν όλοι οι πρώτοι οι οποίοι είναι μικρότεροι ή ίσοι από αυτόν, είναι ο εξής:

1. Αν n<2 τερμάτισε – δεν υπάρχει πρώτος αριθμός μικρότερος του 2.

2. Γράψε κατά αύξουσα σειρά διάταξης όλους τους φυσικούς αριθμούς οι οποίοι είναι μεγαλύτεροι ή ίσοι του 2 και μικρότεροι ή ίσοι του n.

3. Διάγραψε όλα τα πολλαπλάσια του 2 (πχ επισημαίνοντάς τα με μια διαγώνια μολυβιά) τα οποία είναι μεγαλύτερα από το 2.

4.Βρες τον πρώτο (όσο αφορά την διάταξη) αριθμό που είναι μεγαλύτερος του 2 και δεν έχει διαγραφτεί – αν δεν υπάρχει τέτοιος αριθμός πήγαινε στο βήμα 5. Πήγαινε στο βήμα 3 και εκτέλεσέ το, αυτό και το επόμενο (το 4, δηλαδή το τρέχον), θεωρώντας αντί για τον αριθμό 2, τον αριθμό που βρήκες στην αρχή αυτού του βήματος.

5. Οι πρώτοι αριθμοί οι οποίοι είναι μικρότεροι ή ίσοι από τον n είναι οι αριθμοί που δεν είναι διαγραμμένοι.

Γράψτε ένα πρόγραμμα σε Γλώσσα το οποίο με εφαρμογή του παραπάνω αλγόριθμου εμφανίζει στην οθόνη όλους τους πρώτους αριθμούς οι οποίοι είναι μικρότεροι ή ίσοι από κάποιον φυσικό αριθμό n ≥ 2.

Λύση

eratosth

Η απόδειξη ορθότητας παραλείπεται ως άσκηση.

Ασκήσεις για εμβάθυνση

1) Γιατί θεωρείτε ότι ο παραπάνω αλγόριθμος ονομάζεται «κόσκινο»;

2) Τροποποιείστε το παραπάνω πρόγραμμα θεωρώντας ως δεδομένο ότι στο βήμα 3 του αλγόριθμου ο οποίος αναφέρεται στην διατύπωση του προβλήματος αρκεί να διαγραφτούν τα πολλαπλάσια του τρέχοντος αριθμού τα οποία είναι μεγαλύτερα ή ίσα από το τετράγωνο του τρέχοντος αριθμού, διότι τα υπόλοιπα έχουν ήδη διαγραφτεί πριν ο αλγόριθμος φτάσει σ’ αυτό το σημείο. Αν το τετράγωνο του τρέχοντος αριθμού είναι μεγαλύτερο από τον αριθμό n, ο αλγόριθμος πρέπει να μεταβαίνει στο βήμα 5.

Βίντεο

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

Σημείωση: το παρακάτω να μην ληφθεί υπόψη από τους υποψήφιους για το μάθημα της Πληροφορικής στις Πανελλαδικές εξετάσεις. Αυτή η εργασία απαιτεί πληροφορικό και μαθηματικό υπόβαθρο το οποίο δεν καλύπτεται από τα σχολικά βιβλία.

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

Γιώργος Μπουγιούκας, 2016

georgebougioukas@yahoo.com

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

1. Ορισμοί-Υποθέσεις

α)  Ένας αλγόριθμος είναι μια μηχανή Turing. Σημειώστε ότι μέχρι αυτή την στιγμή δεν έχει βρεθεί «αλγόριθμος» ο οποίος να επιλύει οποιοδήποτε μαθηματικό πρόβλημα με οποιοδήποτε τρόπο (πχ με χαρτί και μολύβι) και να μην μπορεί να προσομοιωθεί από μια μηχανή Turing ή «ισοδύναμα» από ένα πρόγραμμα σ’ έναν σύγχρονο ηλεκτρονικό υπολογιστή – αν συνέβαινε κάτι τέτοιο, τα μαθηματικά πιθανότατα δεν θα ήταν όπως τα ξέρουμε σήμερα.

β) Υποθέτουμε ότι ένας αλγόριθμος (A1) για την επίλυση της δευτεροβάθμιας εξίσωσης με πραγματικούς συντελεστές στο ℝ δίνει αναγκαστικά ένα αποτέλεσμα το οποίο συνεπάγεται την αποφασισιμότητα του προβλήματος απόφασης υπάρχει πραγματική λύση για την δοσμένη εξίσωση;” (Π1), για παράδειγμα:

Μια λίστα, κενή αν η δοσμένη εξίσωση δεν έχει καμία πραγματική λύση, με το πολύ δύο στοιχεία (ανά δύο άνισα), διαφορετικά.

2. Απόδειξη

Θα αποδείξουμε το παρακάτω θεώρημα:

Το πρόβλημα της ισότητας δύο πραγματικών σταθερών είναι μη-αποφασίσιμο (Θ1).

Έστω C(TM) η κωδικοποίηση σε συμβολοσειρά μιας μηχανής Turing TM. Για κάθε μηχανή Turing και κάθε συμβολοσειρά εισόδου (επί του αλφάβητου της TM) x, θεωρούμε την σειρά:

p21

Η σειρά αυτή είναι συγκλίνουσα στο ℝ, αφού για k≥1 είναι προφανώς 10-khC(TM),x(k)≤10-k και η σειρά της ακολουθίας 10-k είναι συγκλίνουσα, αφού η ακολουθία 10-k είναι γεωμετρική με λόγο 10-1  και ισχύει |10-1| < 1Επομένως, για κάθε μηχανή Turing TM και συμβολοσειρά εισόδου (επί του αλφάβητου εισόδου της TM) x ισχύει το παρακάτω λήμμα:

p22

Προφανώς,  για κάθε μηχανή Turing TM και κάθε συμβολοσειρά εισόδου (επί του αλφάβητου της TM) x ισχύει και το παρακάτω λήμμα:

p23

Θεωρούμε μια (οποιαδήποτε) μηχανή Turing TM1 με είσοδο μια (οποιαδήποτε επί του αλφάβητου εισόδου της TM1) συμβολοσειρά x1. Υποθέτοντας ότι υπάρχει αλγόριθμος (Α3) ο οποίος αποφασίζει αν δύο πραγματικές σταθερές είναι ίσες, συνεπάγεται ότι υπάρχει ένας άλλος αλγόριθμος (Α4) ο οποίος:

α) Προσομοιώνοντας τον αλγόριθμο Α3 αποφασίζει αν ισχύει ή όχι ότι (το πρώτο μέλος της παρακάτω ισότητας είναι πραγματική σταθερή με βάση το Λ1):

p

β) Με βάση το προηγούμενο αποτέλεσμα και το Λ2 αποφασίζει αν η μηχανή Turing TM1 με είσοδο x1 τερματίζει.

Με άλλα λόγια ο αλγόριθμος Α4 αποφασίζει το πρόβλημα του τερματισμού, αποτέλεσμα το οποίο έρχεται σε αντίφαση με το θεμελιώδες “θεώρημα του τερματισμού” του Alan Turing (Χαλάτσης, 2003, σ. 107). Καταλήξαμε σε αντίφαση γιατί θεωρήσαμε ότι ο αλγόριθμος Α3 υπάρχει. Επομένως, ένας τέτοιος αλγόριθμος δεν υπάρχει. ▪

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

– Αν ο αλγόριθμος Α1 δώσει ως αποτέλεσμα μια μη-κενή λίστα – δηλαδή υπάρχει πραγματική λύση για την δοσμένη εξίσωση – δίνει ως αποτέλεσμα “Αληθές”.

– Αλλιώς, αν ο αλγόριθμος Α1 δώσει ως αποτέλεσμα μια κενή λίστα – δηλαδή δεν υπάρχει πραγματική λύση για την δοσμένη εξίσωση – δίνει ως αποτέλεσμα “Ψευδές”.

Έστω r, s πραγματικές σταθερές και d = |s – r|. Θεωρούμε την ακόλουθη  δευτεροβάθμια εξίσωση με πραγματικούς συντελεστές:

p26

Δοσμένου ενός στιγμιότυπου του Π1 αποτελούμενου από την Ε1, ο αλγόριθμος Α2 δίνει το ακόλουθο αποτέλεσμα:

– Είτε “Αληθές”, που σημαίνει ότι η Ε1 έχει τουλάχιστον μία πραγματική λύση – οπότε αν Δ η διακρίνουσα της Ε1:

p27

– Είτε “Ψευδές”, που σημαίνει ότι η Ε1 δεν έχει πραγματικές λύσεις – οπότε αν Δ η διακρίνουσα της Ε1:

p28

Οι πραγματικές σταθερές s και r δεν έχουν κάποια ιδιαίτερη ιδιότητα. Το ίδιο ισχύει και για τον αλγόριθμο Α2, εκτός από το ότι χρησιμοποιεί το αποτέλεσμα του αλγόριθμου Α1, ο οποίος επίσης δεν έχει κάποια ιδιαίτερη ιδιότητα, εκτός από την υποτιθέμενη μορφή του αποτελέσματος που εξάγει. Επομένως, για κάθε s, r ∈ ℝ μπορεί να κατασκευαστεί η εξίσωση Ε1 και να δοθεί ως είσοδος στον αλγόριθμο Α2, του οποίου το αποτέλεσμα τότε συνεπάγεται ότι είτε s=r είτε sr, δηλαδή το πρόβλημα της ισότητας δύο πραγματικών σταθερών είναι αποφασίσιμο, το οποίο έρχεται σε αντίφαση με το Θ1. Καταλήξαμε σε αντίφαση γιατί υποθέσαμε ότι ο αλγόριθμος Α1 υπάρχει. Επομένως, τέτοιος αλγόριθμος δεν υπάρχει.

Βιβλιογραφικές αναφορές

Χαλάτσης Κ. (2003). Θεμελιώσεις Επιστήμης Η/Υ, Τόμος Β’- Θεωρία Υπολογισμού. Πάτρα, Ελληνικό Ανοικτό Πανεπιστήμιο.