Επιλύσιμο ή άλυτο;

Ξεκίνησε από gpapargi, 20 Σεπ 2006, 11:42:14 ΠΜ

« προηγούμενο - επόμενο »

gpapargi

Να θέσω ένα περίεργο ερώτημα:

Δίνεται το πρόβλημα:
«Να βρεθεί ένας αριθμός που αν πολλαπλασιαστεί με το 0 θα μας δώσει 3»

Ουσιαστικά το πρόβλημά μας είναι η επίλυση της εξίσωσης 0*x=3 η οποία είναι αδύνατη.

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

Αλλά πως μπορείς να πεις ότι το συγκεκριμένο επιλύσιμο πρόβλημα δεν έχει λύση; Δεν είναι αυτοαναιρούμενη η πρόταση που μόλις έγραψα;
 
Τελικά είναι επιλύσιμο ή άλυτο το πρόβλημα; Πως μπορούμε να έχουμε μια συνεπή θέση;

Για να δούμε απόψεις

evry



   Η λύση της πρωτοβάθμιας εξίσωσης  a*x = b  είναι γνωστή όταν a <> 0. Όταν a=0 δεν υπάρχει αυτοματοποιημένος τύπος αλλά παίρνουμε περιπτώσεις.

Οπότε ψηφίζω άλυτο
What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr

alkisg

Δε θα χαρακτήριζα τη λύση πρωτοβάθμιας εξίσωσης επιλύσιμο πρόβλημα... Θα έλεγα ότι είναι:
1) Επιλύσιμο ΟΤΑΝ υπάρχει λύση,
2) Άλυτο όταν ΔΕΝ υπάρχει λύση,
3) Δομημένο, αφού πάντα απαντάμε, είτε βρίσκοντας τη λύση είτε απαντώντας ότι δεν υπάρχει λύση.

Δηλαδή για τη συγκεκριμένη περίπτωση (=[2]) ψηφίζω κι εγώ «ʼλυτο».

koraki

Το πρόβλημα είναι "επιλύσιμο" και η λύση είναι :
"Δεν υπάρχει τέτοιος άριθμος"

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

alkisg

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

Παράθεση από: Ο Γκρινιάρης από τα ΣτρουμφάκιαΜου τη δίνουν τα κριτήρια...

evry

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

Παράθεση από: koraki στις 21 Σεπ 2006, 05:01:10 ΜΜ
Το πρόβλημα είναι "επιλύσιμο" και η λύση είναι :
"Δεν υπάρχει τέτοιος άριθμος"

Το πρόβλημα θα ήταν άλυτο αν δεν ήταν δυνατόν εμείς (και, κατ' επέκταση, κάποιος αλγόριθμος) να καταλήξοιυμε στην παραπάνω θέση.
What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr

gpapargi

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

Γράφω και μια άλλη πιθανότητα

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

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

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

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

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

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

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

koraki

Η πρωτοβάθμια εξίσωση είναι πρόβλημα που η ανθρώπινη διανόηση έχει λύσει. Η θέση "Δεν υπάρχει λύση στην πρωτοβάθμια εξίσωση με α = 0 και β = 3" δε σημαίνει ότι το ίδιο το πρόβλημα επίλυσης της πρωτοβάθμιας εξίσωσης δεν έχει λύση. Άλλωστε, το αν ένα πρόβλημα είναι επιλύσιμο ή όχι δεν - πρέπει - να εξαρτάται από τα δεδομένα (στην προκειμένη περίπτωση τα α και b, στην εξίσωση αx=b).

Αντιθέτως, ο τετραγωνισμός του κύκλου είναι άλυτο πρόβλημα όποια και αν είναι η ακτίνα του κύκλου.

gpapargi

Αν μας πούνε ότι ο δοσμένος κύκλος έχει ακτίνα 1/ρίζα (π) τότε το πρόβλημα λύνεται αφού το εμβαδό είναι 1. Δηλαδή με την ειδική ακτίνα "εξουδετερώνεται" η υπερβατικότητα του π.

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

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

Δεν είναι σωστό να αποφασίζεις το τι ισχύει ανάλογα με το που θα ήθελες να καταλήξεις. Άσε που καταλήγω σε κάποιο όρο που υπάρχει στην πληροφορική. Γιατί δεν το λέγαμε "μη υπολογιστικό" να τελείωνουμε; Μήπως θέλει κάτι άλλο να πει το βιβλίο; Γι αυτό δεν είμαι ικανοποιημένος.

Vangelis

Άλυτο είναι ένα πρόβλημα όταν έχει αποδειχθεί ότι δεν υπάρχει λύση.  Στον ορισμό αυτό παραλείπεται το περιβάλλον του προβλήματος.  Συνεπώς θα έπρεπε να συμπληρωθεί ότι "ʼλυτο είναι ένα πρόβλημα όταν κάτω απο ορισμένες συνθήκες (ή σε συγκεκριμένο περιβάλλον) έχει αποδειχθεί ότι δεν υπάρχει λύση.
Η πρωτοβάθμια εξίσωση που έθεσε ο/η  koraki  είναι πρόβλημα άλυτο.
Ακριβώς το ίδιο συμβαίνει με τον τετραγωνισμό του κύκλου.  Φυσικά και υπάρχει γενική λύση (με όση ακρίβεια θέλουμε) δεν υπάρχει λύση -και χαρακτηρίζεται σαν άλυτο πρόβλημα- κάτω απο ορισμένες συνθήκες.

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

gpapargi

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

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

Ωστόσο δεν μπορώ να μη προβληματιστώ. Ποτέ δεν έχω ακούσει οι αδύνατες εξισώσεις να χαρακτηρίζονται ως άλυτα προβλήματα. Και στο περίφημο τελευταίο θεώρημα του Fermat η διοφαντική αποδείχτηκε αδύνατη αλλά δεν άκουσα ποτέ το πρόβλημα να είναι άλυτο. Γενικά δεν έχω ακούσει ποτέ να χαρακτηρίζονται έτσι εξισώσεις που αποδείχτηκε ότι δεν έχουν λύσεις.

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

Ίσως το άλυτο πρόβλημα να μην έχει κάποιο αυστηρό ορισμό και να το κουβαλάμε από την αρχαιότητα. Δηλαδή να το χρησιμοποιούμε κάπως πιο «λαϊκά» σε σχέση με  τα μη υπολογίσιμα προβλήματα  που έχει ορίσει αυστηρά σήμερα η πληροφορική.

Vangelis

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

alkisg

Πάντως εμένα ο τετραγωνισμός του κύκλου με τους γνωστούς περιορισμούς, η δευτεροβάθμια με αρνητική διακρίνουσα στο R, η πρωτοβάθμια με α = 0 και β <> 0 κτλ μου φαίνεται ότι ανήκουν στην ίδια λογική κατηγορία των αδυνάτων προβλημάτων. Δηλαδή με την ορολογία του βιβλίου, στα άλυτα (btw, κι εγώ προτιμώ τη λέξη "αδύνατο").

Όλα τους είναι προβλήματα με περιορισμούς. Όλα υπό άλλες προϋποθέσεις είναι επιλύσιμα (π.χ. μιγαδικοί αριθμοί κτλ). Όλα τους μπορούν να θεωρηθούν κομμάτι ενός μεγαλύτερου προβλήματος:
* Ο τετραγωνισμός του κύκλου μπορεί να θεωρηθεί κομμάτι του προβλήματος "τετραγωνισμός σχημάτων που μπορούν να δημιουργηθούν με χάρακα και διαβήτη".
* Η δευτεροβάθμια με αρνητική διακρίνουσα, κομμάτι του γενικότερου προβλήματος "επίλυση δευτεροβάθμιας".
* Μια από τα ίδια για την πρωτοβάθμια.

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

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

Finally, χρησιμοποιώντας τη λέξη "αδύνατο" (σε αντίθεση με το "άλυτο" του βιβλίου), πώς θα χαρακτηρίζατε τη δευτεροβάθμια; Απλά "επιλύσιμο" ή "επιλύσιμο όταν Δ >= 0 και αδύνατο όταν Δ < 0;

gpapargi

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

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

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

Στον τετραγωνισμό του κύκλου το ζητούμενο τετράγωνο υπάρχει. Αυτό που δεν υπάρχει είναι η διαδικασία για να το κατασκευάσουμε με κανόνα και διαβήτη.

Δηλαδή το πραγματικό θέμα είναι το τι ζητάμε; Το τελικό αποτέλεσμα ή τη διαδικασία;

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

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

Θέλω να πω πως ο μόνος τρόπος για να είναι πρόβλημα χωρίς λύση ο τετραγωνισμός του κύκλου είναι το να ζητείται η διαδικασία κατασκευής και όχι το τετράγωνο. Και ο μόνος τρόπος για να είναι χωρίς λύση η δευτεροβάθμια, είναι το να ζητάμε τα νούμερα και όχι τη διαδικασία. Ενώ θα είναι επιλύσιμο αν ζητάμε τη διαδικασία. Νομίζω πως πρέπει να ξεκαθαρίσουμε το τι ζητάμε ακριβώς. Δηλαδή βασικά θα πρέπει να ορίσουμε αυστηρά το άλυτο πρόβλημα. Μετά θα είναι εύκολο να συγκρίνουμε και με τους όρους «αδύνατο» (από τις εξισώσεις) και «μη υπολογίσιμο».

Το βιβλίο έτσι κι αλλιώς έχει κάποια παράληψη (αφού λέει ότι η δευτεροβάθμια είναι επιλύσιμη)

nplatis

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

Δυστυχώς στο βιβλίο δεν τονίζεται αρκετά η σημασία του "περιβάλλοντος" του προβλήματος (π.χ. τετραγωνισμός με κανόνα και διαβήτη ή με απειροστικό λογισμό;) και η εξήγηση που δίνεται σε μία γραμμή για τον τετραγωνισμό του κύκλου είναι πολύ πρόχειρη και σύντομη για να είναι καθόλου ουσιαστική.