forum.math.uoa.gr

Forum του Τμήματος Μαθηματικών
Ημερομηνία 24 Νοέμ 2017, 09:05

Όλοι οι χρόνοι είναι UTC + 2 ώρες [ DST ]




Δημιουργία νέου θέματος Απάντηση στο θέμα  [ 11 δημοσιεύσεις ] 
Συγγραφέας Μήνυμα
 Θέμα δημοσίευσης: Αλγόριθμος παραγωγής αλγορίθμων
ΔημοσίευσηΔημοσιεύτηκε: 29 Ιαν 2010, 12:56 
Χωρίς σύνδεση

Εγγραφη: 10 Ιαν 2010, 19:14
Δημοσ.: 51
Στην πληροφορική υπάρχει μια πρόταση που λέει ότι δεν υπάρχει αλγόριθμος παραγωγής αλγορίθμων.Είναι αξίωμα ή κάτι άλλο;Μπορεί κάποιος να παραθέσει την απόδειξη σε κοινά ελληνικά γιατί δεν γνωρίζω σχεδόν τίποτα από θεωρητική πληροφορική;H τουλάχιστον την κεντρική ιδέα και όχι κατ'αναγκην μια αυστηρή απόδειξη.Ευχαριστώ εκ των προτέρων για τον χρόνο σας.


Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης: Re: Αλγόριθμος παραγωγής αλγορίθμων
ΔημοσίευσηΔημοσιεύτηκε: 14 Φεβ 2010, 19:10 
Χωρίς σύνδεση
Regular Forumer

Εγγραφη: 30 Ιαν 2008, 15:49
Δημοσ.: 253
χωρις να εχω καμια σχεση με το θεμα, για να φτιαξεις οποιουδηποτε ειδους αλγοριθμο πρεπει προτα να αναλυσεις το προβλημα που θελεις να λυσεις. αρα πως ενας αλγοριθμος θα δεχτει σαν εισοδο το "προβλημα" για να το αναλυσει τη στιγμη που ακομα και να μπορεις να το εκφρασεις με τροπο που να το "καταλαβαινει" δε μπορει να "σκεφτει" για να κανει την αναλυση. νομιζω οτι η παραγωγη ενος αλγοριθμου χρειαζεται ανθρωπινο μυαλλο. ξαναλεω δεν εχω επαφη με το αντικειμενο αυτο ειναι απλα μια σκεψη που μου ηρθε τωρα

_________________
"Believe nothing. No matter where you read it,Or who said it, Even if I have said it, Unless it agrees with your own reason And your own common sense."

~ Buddha quotes from The Dhammapada


Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης: Re: Αλγόριθμος παραγωγής αλγορίθμων
ΔημοσίευσηΔημοσιεύτηκε: 16 Φεβ 2010, 11:59 
Χωρίς σύνδεση

Εγγραφη: 10 Ιαν 2010, 19:14
Δημοσ.: 51
Κατ'αρχάς ευχαριστώ που έκατσες και έγραψες τη σκέψη σου καθώς αυτό το thread ήταν αδρανές για κάμποσο καιρό.Αν ο Η/Υ είχε ανθρώπινο μυαλό προφανώς θα μπορούσε να λύσει τα προβλήματα που λύνει ο άνθρωπος.Άρα η πρώτη συνθήκη είναι ικανή για την ισχύ της δεύτερης,το αντίστροφό όμως δεν συμβαίνει κατ'ανάγκην.Μια άλλη ικανή συνθήκη θα μπορούσε να ήταν η εξής:Οι θεωρητικοί πληροροφορικάριοι,μέσα από μια βαθιά κατανόηση της δομής των προβλημάτων που μπορούν να λύσουν,κατασκευάζουν έναν αλγόριθμο που δέχεται ένα εκφωνημένο πρόβλημα,εξάγει,από τα συστατικά του στοιχεία, τη δομή του και κατασκευάζει,βάσει κάποιων γενικών κανόνων γνωστών στους προγραμματιστές,έναν αλγόριθμο που να το επιλύει ή δίνει τις εξόδους σε έναν άλλον αλγόριθμο που να κατασκευάζει τον αλγόριθμο που το επιλύει.Φαινομενικά αυτό θα μπορούσε να συμβαίνει αλλά η διαίσθηση (ειδικά αυτή η απλοϊκή) συχνά κάνει λάθη γι'αυτό ζητάω και την απόδειξη.
Ο αρχικός λόγος που ζήτησα την απόδειξη ήταν ωστόσο το να δω αν μπορώ να αποδείξω την μη ύπαρξη ενός αλγορίθμου που να δέχεται ως είσοδο το πρόβλημα και να εξάγει μόνο τις πληροφορίες που ενέχονται σε κάποιου είδους εκφώνηση του και αφορούν άμεσα την λύση του.Αυτό θα μπορούσε να προκύψει από τον τρόπο απόδειξης της πρότασης :"Δεν υπάρχει αλγόριθμος παραγωγής αλγορίθμων".


Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης: Re: Αλγόριθμος παραγωγής αλγορίθμων
ΔημοσίευσηΔημοσιεύτηκε: 16 Φεβ 2010, 14:14 
Χωρίς σύνδεση
Regular Forumer

Εγγραφη: 30 Ιαν 2008, 15:49
Δημοσ.: 253
αν δεχεται καποιο συγκεκριμενο προβλημα ως εισοδο τοτε πιθανοτατα μπορει να υπαρξει αλγοριθμοςΑ που θα φτιαξει αλγοριθμοΒ που θα το λυνει αλλα απο τη στιγμη που το προβλημα ειναι συγκεκριμενο τοτε ο αλγοριθμος Α δεν ειναι αλγοριθμος παραγωγης αλγοριθμων αλλα λυσης του προβληματος (σε συνδιασμο με τον Β)

_________________
"Believe nothing. No matter where you read it,Or who said it, Even if I have said it, Unless it agrees with your own reason And your own common sense."

~ Buddha quotes from The Dhammapada


Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης: Re: Αλγόριθμος παραγωγής αλγορίθμων
ΔημοσίευσηΔημοσιεύτηκε: 16 Φεβ 2010, 21:28 
Χωρίς σύνδεση

Εγγραφη: 10 Ιαν 2010, 19:14
Δημοσ.: 51
Σίγουρα,αλλά αυτό δεν απαντάει στην ερώτηση.Αν φτιάξεις έναν αλγόριθμο που κατασκευάζει αλγορίθμους λύσης προφανώς από μία άποψη αυτός σου λύνει το πρόβλημα.Η χρησιμότητα αυτού του αλγορίθμου ωστόσο έγκειται στο ότι δεν θα απασχολήσει κάποιον άνθρωπο για να λύσει το πρόβλημα.Έχε κατά νου ότι δεν μιλάμε για ένα συγκεκριμένο(δεδομένο) πρόβλημα.Ρωτάω για την ύπαρξη ενός αλγορίθμου που μπορεί να λύσει κάθε πρόβλημα.


Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης: Re: Αλγόριθμος παραγωγής αλγορίθμων
ΔημοσίευσηΔημοσιεύτηκε: 17 Φεβ 2010, 01:34 
Χωρίς σύνδεση
Regular Forumer

Εγγραφη: 15 Σεπ 2007, 17:12
Δημοσ.: 174
Τοποθεσια: Ν.Σμυρνη
Καλησπερα,στην Θεωρητικη Πληροφορικη ειναι προφανες οτι δεν υπαρχει αλγοριθμος που να λυνει καθε προβλημα,εδω δεν υπαρχει αλγοριθμος που να λυνει συγκεκριμενα προβληματα..Δες εδω και εδω.


Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης: Re: Αλγόριθμος παραγωγής αλγορίθμων
ΔημοσίευσηΔημοσιεύτηκε: 17 Φεβ 2010, 13:33 
Χωρίς σύνδεση

Εγγραφη: 10 Ιαν 2010, 19:14
Δημοσ.: 51
Εννοούσα κάθε πρόβλημα που μπορεί να λύσει ο άνθρωπος.Σίγουρα υπάρχουν και σοβαρές αντενδείξεις για αυτό,όπως η εικασία Chruch-Turing(πράγμα που δεν είχα σκεφτεί όταν αρχικά έκανα την ερώτηση).Διότι,αν δεχτούμε πως μόνο πολυονιμικής πολυπλοκότητας αλγόριθμοι επιλύονται στον Η/, καθώς,προφανώς,υπάρχουν αλγόριθμοι κατασκευάσιμοι από άνθρωπο που δεν είναι πολυωνιμικής πολυπλοκότητας,θα υπάρχουν αλγόριθμοι που δεν μπορεί να κατασκευάσει ο Η/Υ ενώ μπορεί ο άνθρωπος.Αυτά όμως αν δεχτούμε την αλήθειά της εικασίας.Όμως,με ενδιαφέρει να δω την ακριβή απόδειξη,αν υπάρχει,για να συμπεράνω αν εξασφαλίζει την αδυναμία δημιουργίας αλγορίθμου,ο οποίος θα δέχεται ένα εκφωνημένο πρόβλημα,σε όποια γλώσσα είναι καταλληλότερη για τον Η/Υ,και θα εξάγει σε μας μόνο τις εισόδους(δεδομένα του προβλήματος) που αφορούν την λύση του.Μπορεί λοιπόν κανείς να απαντήσει στην ανωτέρω ερώτηση,έστω και με κάποιες στέρεες ενδείξεις;Επειδή,θα μπορούσε εύλογα να ρωτήσει κανείς γιατί δεν έκανα ευθέως αυτήν την ερώτηση,απαντώ.Αρχικά ίσως να ήθελα να το λύσω κατά το δυνατόν μόνος αυτό το πρόβλημα.Σε κάθε περίπτωση όμως αυτή η αντιμετώπιση ίσως να είναι πιο παραγωγική.Ευχαριστώ για τον χρόνο που αφιερώσατε


Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης: Re: Αλγόριθμος παραγωγής αλγορίθμων
ΔημοσίευσηΔημοσιεύτηκε: 17 Φεβ 2010, 17:12 
Χωρίς σύνδεση
Regular Forumer

Εγγραφη: 30 Ιαν 2008, 15:49
Δημοσ.: 253
μα δε νομιζω οτι το προβλημα ειναι να εξαγει τις εισοδους. αυτο γινεται.

το προβλημα ειναι να "σκεφτει" ο υπολογιστεις ποια βηματα απαιτουνται για να παρεις το αποτελεσμα που θες. εκει κολαει το θεμα.

_________________
"Believe nothing. No matter where you read it,Or who said it, Even if I have said it, Unless it agrees with your own reason And your own common sense."

~ Buddha quotes from The Dhammapada


Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης: Αλγόριθμος παραγωγής αλγορίθμων
ΔημοσίευσηΔημοσιεύτηκε: 18 Φεβ 2010, 09:38 
Χωρίς σύνδεση
Regular Forumer

Εγγραφη: 11 Φεβ 2007, 21:13
Δημοσ.: 630
Κάθε σημερινός υπολογιστής είναι ουσιαστικά μιά «μηχανή Turing»...Ισχύει:

«Κάθε μαθηματική συνάρτηση, που είναι δυνατόν να υπολογιστεί, είναι δυνατόν να υπολογιστεί απο μιά μηχανή Turing»

Ισχύει και το αντίστροφο:

«Ό,τι ΔΕΝ μπορεί να υπολογίσει μιά μηχανή Turing, ΔΕΝ μπορεί να το υπολογίσει κανένας»

Ο Alonzo Church ανέπτυξε μια φορμαλιστική γλώσσα , τόν λ-Λογισμό, πάνω στην οποία βασίζεται και η μοντέρνα γλώσσα προγραμματισμού LISP. Αυτός λοιπόν θεμελίωσε τήν εξής πρόταση:

«Κάθε μαθηματική συνάρτηση που μπορεί να υπολογιστεί μπορεί να οριστεί με όρους τού λ-Λογισμού»»

Κατέδειξε ακόμη :

«Άν υπάρχει κάποια αυνάρτηση που ΔΕΝ μπορεί να υπολογιστεί με τον λ-Λογισμό, τότε ΔΕΝ υπάρχει, γενικά, μέθοδος που να μάς επιτρέπει να αποφανθούμε για το άν μιά μαθηματική πρόταση αποδεικνύεται ή ακόμη για το άν είναι αληθής»

Οι Turing και Church δεν έδωσαν (απ’ ό,τι ξέρω) παραδείγματα προβλημάτων που δεν επιλύονται. Το πρώτο γνωστό παράδειγμα το έδωσε ο Ούγγρος μαθηματικός Tibor Rado και είναι τό «Busy Beaver Problem» ή Πρόβλημα τού εργατικού Κάστωρα :

http://delab.csd.auth.gr/~tsichlas/Complexity/Busy_beaver_report.pdf

Άν το διαβάσεις θα δείς, ως συμπέρασμα, ότι δεν υπάρχει μηχανή Turing Ν καταστάσεων που να υπολογίζει τό σ(Ν²)
Αυτό μάλιστα ισχύει και για τό σ(Ν)
Έτσι καταλήξαμε σε διαχωρισμό τών μηχανών Turing σε ντετερμινιστικές και μή ντετερμινιστικές και τών προβλημάτων σέ τάξεις πολυπλοκότητας (ως σήμερα άλυτο πρόβλημα) P-NP
Οι πρώτες σταματούν (ο αλγόριθμος περατώνεται) οι δεύτερες όχι.
Το σύνολο όλων τών «Γλωσσών» (όλα ό,τι εισάγουμε σε έναν αλγόριθμο) που επιλύεται απο μια ντετερμινιστική μηχανή Turing (ντερτεμινιστικός αλγόριθμος) σε Πολυωνυμικό χρόνο χαρακτηρίζεται P (απο το polynomial)
NP είναι το σύνολο όλων τών Γλωσσών που επιλύεται σε πολυωνυμικό χρόνο απο μια μη ντετερμινιστική μηχανή Turing (το Ν απο το Νot deterministic)
Οι ντετερμινιστικές μηχανές επιλύουν τα προβλήματα τής τάξεως Ρ, ενώ οι μή ντετερμινιστικές «μαντεύουν» θα λέγαμε και μετα επαληθεύουν την απάντηση που έδωσαν.

Το P-NP πρόβλημα είναι σήμερα το πιό σημαντικό πρόβλημα τής θεωρίας Πολυπλοκότητας

Αποκαλυπτικός


Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης: Re: Αλγόριθμος παραγωγής αλγορίθμων
ΔημοσίευσηΔημοσιεύτηκε: 19 Φεβ 2010, 19:32 
Χωρίς σύνδεση
Regular Forumer
Άβαταρ μέλους

Εγγραφη: 30 Μάιος 2006, 18:52
Δημοσ.: 1754
Τοποθεσια: Ν.Σμύρνη
Εχω μια εντυπωση οτι το ολο προβλημα δεν γινεται να επιλυθει κυριως επειδη ειναι αλυτο το πρoβλημα του τερματισμου...μια μηχανη Turing ειναι δυνατον να παρει ως εισοδο ενα προβλημα , ακομα και μια αλλη μηχανη Turing αν θελουμε,αλλα δεν μπορουμε να φτιαξουμε καμια τετοια μηχανη που να δεχεται καποιο προβλημα και να σου λεει αν επιλυεται.αν γινοταν,δεν θα ισχυε το θεωρημα του Goedel νομιζω :oops: :oops: Ας με διορθωσει καποιος αν κανω λαθος :oops:

_________________
Μην ξεχνάτε...στην νέα τάξη πραγμάτων,τα πράγματα είμαστε εμείς...


Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης: Αλγόριθμος παραγωγής αλγορίθμων
ΔημοσίευσηΔημοσιεύτηκε: 19 Φεβ 2010, 23:00 
Χωρίς σύνδεση
Regular Forumer

Εγγραφη: 11 Φεβ 2007, 21:13
Δημοσ.: 630
Και ναί και όχι..δεν απαντάται έτσι εύκολα...εξαρτάται απο το σύστημα...Οι προτάσεις τού Goedel αφορούν την ολότητα....Ένα μικρό αντιπαράδειγμα..

Το 1929 κατάφερε ένας μαθητής τού Tarsky, ο Mojzesz Presburger να αποδείξει ότι η αριθμητική του (presburger arithmetic) είναι καί πλήρης και αποκρίσιμη και μή αντιφατική. Η αριθμητική αυτή ασχολείται με τούς φυσικούς αριθμούς και την πρόσθεσή τους, όχι όμως με τον πολλαπλασιασμό τους. Οι πρώτοι αριθμοί δεν ορίζονται πχ. σ’ αυτήν.

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

Το μειονέκτημα είναι αυτό που απέδειξε ο Rabin τήν δεκαετία τού 70 :

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

Υπάρχουν και άλλα παραδείγματα....

Αυτό που θέλω να πώ είναι ότι το θεώρημα τού Goedel ισχύει για φορμαλιστικά συστήματα φυσικών αριθμών, στα οποία ισχύει το represantation theorem. Το σύστημα πρέπει δλδ να είναι γερό... δυνατό πολύ... ώστε να μπορέσει να εκφράσει κάθε τι το υπολογίσιμο...Σάν το σύστημα Peano πχ.
Ο Presburger το αποδυνάμωσε βγάζοντας τον πολ/σμό...Ο Robinson σκέφτηκε..τί χρειάζομαι το επαγωγικό αξίωμα ;..Δεν θέλω να υπολογίσω γιά ΟΛΟΥΣ τους φυσικούς...μου αρκεί για πεπερασμένο πλήθος...και έκανε την Robinson arithmetic…κλπ κλπ..

Αποκαλυπτικός


Κορυφή
 Προφίλ  
 
Τελευταίες δημοσιεύσεις:  Ταξινόμηση κατά  
Δημιουργία νέου θέματος Απάντηση στο θέμα  [ 11 δημοσιεύσεις ] 

Όλοι οι χρόνοι είναι UTC + 2 ώρες [ DST ]


Μελη σε συνδεση

Μέλη σε αυτή την Δ. Συζήτηση : Δεν υπάρχουν εγγεγραμμένα μέλη και 1 επισκέπτης


Δεν μπορείτε να δημοσιεύετε νέα θέματα σε αυτή τη Δ. Συζήτηση
Δεν μπορείτε να απαντάτε σε θέματα σε αυτή τη Δ. Συζήτηση
Δεν μπορείτε να επεξεργάζεστε τις δημοσιεύσεις σας σε αυτή τη Δ. Συζήτηση
Δεν μπορείτε να διαγράφετε τις δημοσιεύσεις σας σε αυτή τη Δ. Συζήτηση

Αναζήτηση για:
Μετάβαση σε:  
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group