UkrReferat.com
найбільша колекція україномовних рефератів

Всього в базі: 75838
останнє поновлення: 2016-12-03
за 7 днів додано 15

Реферати на українській
Реферати на російській
Українські підручники

$ Робота на замовлення
Реклама на сайті
Зворотній зв'язок

 

ПОШУК:   

реферати, курсові, дипломні:

Українські рефератиРусские рефератыКниги
НазваМашина Тьюринга (реферат)
Авторukrreferat.com
РозділІнформатика, компютерні науки
ФорматWord Doc
Тип документуРеферат
Продивилось2127
Скачало391
Опис
ЗАКАЧКА
Замовити оригінальну роботу

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

 

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

 

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

розділеної на гнізда, послідовно пронумеровані цілими числами, як

позитивними, так і негативними.

 

У кожнім гнізді стрічки може стояти будь-який символ із заданого

алфавіту, у якім виділений «порожній» символ — ознака того, що гніздо

порожнє.

 

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

починається робота машини) і кінцевий стан, потрапивши в яке машина

припиняє роботу.

 

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

і стояти на місці; уміє читати вміст, стирати й записувати символи з

даного алфавіту; управляється програмою.

 

Програма — це таблиця, у якій у кожній клітці записана команда. Кожна

клітка визначається двома параметрами — символом алфавіту й станом

машини. Команда — ця вказівка, куди пересунути головку читання/запису з

поточного стану, який символ записати в поточне гніздо й у який стан

перейде машина.

 

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

 

в

 

д

 

R

 

T

 

д

 

T

 

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

проблему: якщо для рішення завдання можна побудувати машину Тьюринга,

вона алгоритмічно розв'язна.

 

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

 

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

 

 

чи Можна будь-який алгоритм представити у формі машини Тьюринга?

Відповідь на це питання дається у вигляді так званого тези Тьюринга:

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

його неможливо довести, тому що в ньому фігурують, з одного боку,

інтуїтивне поняття «усякий алгоритм», а з іншого сторони — точне поняття

«машина Тьюринга».

 

Клас нормальних алгоритмів Маркова й клас алгоритмів, представлених у

формі машин Тьюринга, збігаються.

 

0

ЗАМОВИТИ ОРИГІНАЛЬНУ РОБОТУ