Διαφορά μεταξύ των αναθεωρήσεων του «Μηχανή Τούρινγκ»

καμία σύνοψη επεξεργασίας
μ (r2.6.4) (Ρομπότ: Τροποποίηση: be-x-old:Машына Т’юрынга)
Η '''μηχανή Τούρινγκ''' (Turing machine) είναι μια βασική [[αφηρημένη μηχανή]] που μεταχειρίζεται σύμβολα, η οποία, παρ' όλη την απλότητά της, μπορεί να προσαρμοστεί έτσι ώστε να προσομοιώσει τη λογική οποιουδήποτε [[υπολογιστήςαλγόριθμος|υπολογιστήαλγορίθμου]] που μπορεί να κατασκευασθεί ποτέ. Οι μηχανές Τούρινγκ περιγράφηκαν το [[1936]] από τον [[Άλαν Τούρινγκ]]. Ενώ σχεδιάστηκαν για να είναι τεχνικά εφικτές, οι μηχανές Τούρινγκ δεν προορίζονταν να είναι πρακτική υπολογιστική τεχνολογία, αλλά ένα [[νοητό πείραμα]] για τα όρια των μηχανικών υπολογισμών. Έτσι, δεν κατασκευάστηκαν στην πραγματικότητα. Η μελέτη των αφηρημένων τους ιδιοτήτων φανερώνει πολλές αρχές της [[επιστήμη υπολογιστών|επιστήμης υπολογιστών]] και της [[θεωρία πολυπλοκότητας|θεωρίας πολυπλοκότητας]].
 
Μια μηχανή Τούρινγκ που μπορεί να προσομοιώσει μια οποιαδήποτε άλλη μηχανή Τούρινγκ λέγεται [[Καθολική Μηχανή Τούρινγκ]] (ή απλά '''καθολική μηχανή'''). Ένας πιο μαθηματικός ορισμός με παρόμοια "καθολική" φύση τέθηκε από τον [[Αλόνζο Τσερτς]], του οποίου η εργασία πάνω στο [[λογισμός λάμδα|λογισμό λάμδα]] συνυφαίνεται με αυτή του Τούρινγκ σε μια τυπική θεωρία [[υπολογισμός|υπολογισμού]] που είναι γνωστή ως η [[θέση Τσερτς-Τούρινγκ]]. Η θέση λέει ότι οι μηχανές Τούρινγκ όντως εμπεριέχουν την ανεπίσημη έννοια της αποδοτικής μεθόδου στη λογική και τα μαθηματικά, και δίνουν έναν ακριβή ορισμό ενός [[αλγόριθμος|αλγορίθμου]] ή μιας ''μηχανικής διαδικασίας''.
Ανώνυμος χρήστης