ΤΙΤΛΟΣ ΜΕΤΑΠΤΥΧΙΑΚΟΥ:Θεωρητική Πληροφορική και Θεωρία Συστημάτων και Ελέγχου//////Μηχανές Turing και Αποφασισιμότητα
Creators: name: Νταουντάκης, Εμμανουήλ Χρήστου
Publisher: name: Aristotle University of Thessaloniki
Year: 2023
Subjects: Μηχανές Turing Αποφασισιμότητα
Μη Αποφασισιμότητα
Αναδρομικές Γλώσσες
Αναδρομικά Απαριθμίσιμες Γλώσσες
Μη αναδρομικά Απαριθμίσιμες γλώσσες
Το πρόβλημα του τερματισμού
Αναγωγή
Το πρόβλημα της αντιστοιχίας του Post
Πολυπλοκότητα Θεώρημα των Cook-Levin
Θεώρημα του Rice
Δεύτερο θεώρημα του (Θεώρημα των Rice Rice-Shapiro)
Θεώρημα αναδρομής
Θεώρημα σταθερού σημείου Μηχανές Turing με μαντείο Πλακίδια Wang
Σύνολο του Robinson
Το πρόβλημα της πλακόστρωσης
Turing Machines
Decidability
Non decidability
Recursive languages
Recursive Enumerable languages
Non Recursive Enumerable languages
Halting Problem
Reduction
Post correspondence problem
Complexity
Cook-Levin theorem
Rice’s theorem
Second theorem of Rice (Rice-Shapiro theorem)
Recursion theorem
Fixed point theorem
Oracle Turing Machines
Wang tiles
The set of Robinson
Tilling problem
Domino problem

description: Στην παρούσα εργασία μελετώνται θέματα και προβλήματα από την θεωρία της αποφασισιμότητας. Για να μελετήσουμε την θεωρία της αποφασισιμότητας θα χρησιμοποιησούμε τις μηχανές Turing ως μοντέλο υπολογισμού. Στο πρώτο κεφάλαιο ορίζουμε την μηχανή Turing και παρουσιάζουμε κάποιες χαρακτηριστικές τους ιδιότητες. Στο δεύτερο κεφάλαιο χωρίζουμε τις γλώσσες ή αλλίως προβλήματα στις αναδρομικές, αναδρομικά απαριθμήσιμες και όχι αναδρομικά απαριθμήσιμες. Kατ'επέκταση διακρίνουμε τα προβλήματα σε αποφασίσιμα και μη αποφασίσιμα. Δίνουμε παράδειγμα από μία γλώσσα που δεν είναι αναδρομικά απαριθμήσιμη, την διαγωνοποιήσιμη γλώσσα και στην συνέχεια ορίζουμε το πρόβλημα τερματισμού που εισήγαγε ο A. M. Turing, το οποίο θα είναι ένα πρόβλημα αυστηρά αναδρομικά απαριθμήσιμο και όχι αναδρομικό. Το τρίτο κεφάλαιο ορίζουμε την αναγωγή και με την βοήθεια της αποδεικνύουμε ότι το πρόβλημα του Post είναι μη αποφασίσιμο. Επίσης αποδεικνύουμε το πρώτο θεώρημα του Rice. Το τέταρτο κεφάλαιο αφιερώνεται σε μία μικρή εισαγωγή στην θεωρία πολυπλοκότητας και τελειώνει με το θεώρημα των Cook- Levin. Έπειτα στο κεφάλαιο πέντε μελετάμε τα θεωρήματα της αναδρομής, θεώρημα αυτοαναφοράς και το θεώρημα Rice- Shapiro και ορίζουμε τις μηχανές Turing με μαντείο. Στο έκτο κεφάλαιο μελετάμε τα πλακίδια Wang και ένα μη αποφασίσιμο πρόβλημα, το πρόβλημα της πλακόστρωσης, ακολουθώντας την απόδειξη του Robinson.
description: In this Master thesis we study topics and problems from the field of decidability theory. To study decidability theory we will use Turing machines as a computing model. In the first chapter we define the Turing machine model and present some of their characteristics. In the second chapter we divide the languages or problems in recursive, recursive enumerable problems and not recursive enumerable problems, hence what is decidable and what is not. In the last section of second chapter, we give an example of a language that is not recursively enumerable, diagonal language , and then we define the Halting Problem introduced by A. M. Turing,which will show to be a strictly recursively enumerable and not recursive problem.In the third chapter we define reduction and with its help we prove that Post's problem is undecidable. We also prove the first theoremof Rice. Chapter four is devoted to a short introduction to complexity theory and the intractable problems and ends with the Cook-Levin theorem. In chapter five we study the fixed point theorem, self-reference theorem and theorem Rice's-Shapiro. In the last part of chapter five we define oracle Turing machines and an hierarchy of problems. In the sixth chapter we study Wang tilings and the domino problem, which is non-decidable. Our proof follows the proof of Robinson.