Реферат на тему:
Машина Тьюринга
Машина Тьюринга складається з необмеженої в обидва боки стрічки,
розділеної на гнізда, послідовно пронумеровані цілими числами, як
позитивними, так і негативними.
У кожнім гнізді стрічки може стояти будь-який символ із заданого
алфавіту, у якім виділений «порожній» символ — ознака того, що гніздо
порожнє.
Машина має кінцеву безліч внутрішніх станів, початкове (з нього
починається робота машини) і кінцевий стан, потрапивши в яке машина
припиняє роботу.
Крім стрічки є головка читання/запису, який уміє рухатися вперед, назад
і стояти на місці; уміє читати вміст, стирати й записувати символи з
даного алфавіту; управляється програмою.
Програма — це таблиця, у якій у кожній клітці записана команда. Кожна
клітка визначається двома параметрами — символом алфавіту й станом
машини. Команда — ця вказівка, куди пересунути головку читання/запису з
поточного стану, який символ записати в поточне гніздо й у який стан
перейде машина.
Машина Тьюринга — це модель комп’ютера.
a
ae
R
T
ae
T
gd@[!
Машина одержала ім’я математика А. Тьюринга (Англія) і вирішує наступну
проблему: якщо для рішення завдання можна побудувати машину Тьюринга,
вона алгоритмічно розв’язна.
І машина Тьюринга, і машина Поста еквівалентні по своїх можливостях.
Розроблені практично в те саме час (в 1936 р.) незалежно друг від друга.
чи Можна будь-який алгоритм представити у формі машини Тьюринга?
Відповідь на це питання дається у вигляді так званого тези Тьюринга:
усякий алгоритм представимо у формі машини Тьюринга. Це теза тому, що
його неможливо довести, тому що в ньому фігурують, з одного боку,
інтуїтивне поняття «усякий алгоритм», а з іншого сторони — точне поняття
«машина Тьюринга».
Клас нормальних алгоритмів Маркова й клас алгоритмів, представлених у
формі машин Тьюринга, збігаються.
Нашли опечатку? Выделите и нажмите CTRL+Enter
