↑ Вгору

Реферат на тему

Машина Тьюринга


читати

Переглянути реферат

зберегти

Скачати реферат

друкувати

Друкувати реферат

Реферат на тему:

Машина Тьюринга

Машина Тьюринга складається з необмеженої в обидва боки стрічки,
розділеної на гнізда, послідовно пронумеровані цілими числами, як
позитивними, так і негативними.

У кожнім гнізді стрічки може стояти будь-який символ із заданого
алфавіту, у якім виділений «порожній» символ — ознака того, що гніздо
порожнє.

Машина має кінцеву безліч внутрішніх станів, початкове (з нього
починається робота машини) і кінцевий стан, потрапивши в яке машина
припиняє роботу.

Крім стрічки є головка читання/запису, який уміє рухатися вперед, назад
і стояти на місці; уміє читати вміст, стирати й записувати символи з
даного алфавіту; управляється програмою.

Програма — це таблиця, у якій у кожній клітці записана команда. Кожна
клітка визначається двома параметрами — символом алфавіту й станом
машини. Команда — ця вказівка, куди пересунути головку читання/запису з
поточного стану, який символ записати в поточне гніздо й у який стан
перейде машина.

Машина Тьюринга — це модель комп'ютера.

в

д

R

T

д

T

Машина одержала ім'я математика А. Тьюринга (Англія) і вирішує наступну
проблему: якщо для рішення завдання можна побудувати машину Тьюринга,
вона алгоритмічно розв'язна.

І машина Тьюринга, і машина Поста еквівалентні по своїх можливостях.

Розроблені практично в те саме час (в 1936 р.) незалежно друг від друга.


чи Можна будь-який алгоритм представити у формі машини Тьюринга?
Відповідь на це питання дається у вигляді так званого тези Тьюринга:
усякий алгоритм представимо у формі машини Тьюринга. Це теза тому, що
його неможливо довести, тому що в ньому фігурують, з одного боку,
інтуїтивне поняття «усякий алгоритм», а з іншого сторони — точне поняття
«машина Тьюринга».

Клас нормальних алгоритмів Маркова й клас алгоритмів, представлених у
формі машин Тьюринга, збігаються.


© 2013 Alive-inter.net Про сайт Зворотній зв`язок Відмова від відповідальності