Μηχανές Turing και Υπερυπολογισιμότητα:
Creators: name: Καρυδά, Άννα Νικολάου
Publisher: name: Aristotle University of Thessaloniki
Year: 2012
Subjects: Μηχανές Turing
Υπολογισιμότητα
Υπερυπολογισιμότητα
Turing Machines
Computability
Hypercomputability

description: Σε αυτή την εργασία παρουσιάζεται μια εισαγωγή στη μελέτη των μηχανών Turing σε συνδιασμό με την έννοια της κλασικής υπολογισιμότητας, καθώς και στον ταχύτητα αυξανόμενο τομέα της υπερυπολογισιμότητας, της μελέτης δηλαδή των μηχανών που μπορούν να υπολογίσουν πέρα από μια μηχανή Turing. Γίνεται μια εκτεταμένη παρουσίαση των πιο σημαντικών ιδεών σε αυτούς τους τομείς, συνθέτοντας τις διαφορετικές ιδέες και παρουσιάζοντάς τες με μια τέτοια δομή που επιτρέπει συγκρίσεις ανάμεσα στις διαφορετικές προσεγγίσεις και στα διαφορετικά αποτελέσματα. Σε αυτή τη μελέτη προστίθενται κάποιες ενδιαφέρουσες συνέπειες της υπερυπολογισιμότητας για διαφορετικούς τομείς της επιστημονικής γνώσης. Η μελέτη αυτή ξεκινά με μια συνοπτική εισαγωγή στην κλασική θεωρία υπολογισμού (που περιλαμβάνει τη μελέτη των μηχανών Turing) και τη ξεχωριστή θέση που κατέχει ανάμεσα σε κάποια από τα σημαντικότερα "αρνητικά" αποτελέσματα του 20ου αιώνα. Στη συνέχεια αναλύεται η "Θέση των Church - Turing" και το πώς έχει ενίοτε παρεξηγηθεί και παρουσιάζονται νέες θέσεις που περιγράφουν καλύτερα τα πιθανά όρια της υπολογισιμότητας. Κατόπιν, αναπτύσσονται δέκα διαφορετικά είδη υπερμηχανών και αναλύονται σε ένα βαθμό οι τρόποι με τους οποίους πραγματώνουν τις δυνατότητές τους καθώς και η φυσική αληθοφάνεια της κάθε μεθόδου. Κατόπιν, συγκρίνονται οι δυνατότητες των διαφορετικών αυτών μοντέλων χρησιμοποιώντας έναν μηχανισμό της θεωρίας των αναδρομικών συναρτήσεων. Τέλος, εξετάζονται οι συνέπειες της υπερυπολογισιμότητας στα Μαθηματικά, τη Φυσική, την Επιστήμη των Υπολογιστών και τη Φιλοσοφία. Ίσως η πιο σημαντική από αυτές τις συνέπειες είναι ότι τα "αρνητικά" αποτελέσματα των Godel, Turing και Chaitin είναι όλα εξαρτώμενα από την φύση της Φυσικής Επιστήμης. Αυτό τόσο αποδυναμώνει τα ίδια τα αποτελέσματα, όσο παρέχει ισχυρούς συνδέσμους μεταξύ των Μαθηματικών και της Φυσικής. Καταλήγοντας, αναλύεται το πώς η υπερυπολογισιμότητα έχει σοβαρό ακαδημαϊκό ενδιαφέρον για πολλούς επιστημονικούς τομείς, δίνοντας νέες προοπτικές που αγνοούνταν στο παρελθόν, λόγω των παρανοήσεων που υπήρχαν για μεγάλο χρονικό διάστημα γύρω από τα όρια της υπολογισιμότητας.
description: In this report we provide an introduction to the study of Turing machines and the classical theory of computation as well as the burgeoning field of hypercomputation - the study of machines that can compute more than Turing machines. We take an extensive survey of many of the key concepts in the field, tying together the disparate ideas and presenting them in a structure which allows comparisons of the many approaches and results. In addittion we provide several new results and draw out some interesting consequences of hypercomputation for several different disciplines. We begin with a succinct introduction to the classical theory of computation and its place among some of the negative results of the 20th Century. Then we explain how the Church - Turing Thesis is commonly misunderstood and present new theses which better describe the possible limits on computability. Following this, we give the introduction of ten different hypermachines and discuss in some depth the manners in which they attain their power and the physical plausibility of each method. In the sequel we compare the powers of the different models using a device from recursion theory. Finally, we examine the implications of hypercomputation to mathematics, physics, computer science and philosophy. Perhaps the most important of these implications is that the negative mathematical results of Godel, Turing and Chaintin are each dependent upon the nature of physics. This both weakens these results and provide strong links between mathematics and physics. We conclude that hypercomputation is of serious academic interest within many disciplines, opening new possibilities that were previously ignored because of long held misconceptions about the limits of computation.