Μηχανές Turing και Αποφασισιμότητα – Παρουσιάση Διπλωματικής
Ημέρα και ώρα: Παρασκευή 16/12 στις 19.00
Τίτλος: Μηχανές Turing και Αποφασισιμότητα
Ομιλιτής: Μεταπτυχιακός Φοιτητής Μανώλης Νταουντάκης
Περίληψη: Στην παρουσίαση αυτή αρχικά θα ορίσουμε τις μηχανές Turing ως μοντέλο υπολογισμού. Στην συνέχεια θα μελετήσουμε το Πρόβλημα Τερματισμού (Halting Problem) και θα δείξουμε ότι είναι είναι μη αποφασίσιμο πρόβλημα, αποτέλεσμα που έδειξε ο A.Turing . Τέλος θα ορίσουμε τα πλακίδια Wang και συνδιάζοντας την μη αποφασισιμότητα του Halting Problem, μέσω της αναγωγής (many-one) θα καταλήξουμε ότι το Πρόβλημα της Πλακόστρωσης (Domino Problem) του επιπέδου είναι ένα μη αποφασίσιμο Πρόβλημα. Η απόδειξη που δώσουμε στηρίζεται στον Robinson.
Η διάλεξη απευθύνεται σε μεταπτυχιακούς και προπτυχιακούς φοιτητές, είναι ανοιχτή σε όλους και θα γίνει μέσω ΖΟΟΜ.
Join Zoom Meeting
https://authgr.zoom.us/j/99575407929?pwd=TjRRSDBESFFVYWtDbzN5WDNIYjhtQT09
Meeting ID: 995 7540 7929
Passcode: 366905