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

Всього в базі: 75843
останнє поновлення: 2016-12-04
за 7 днів додано 10

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

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

 

ПОШУК:   

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

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

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

 

Машина Поста

 

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

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

позитивними, так і негативними. У кожнім гнізді стрічки стоїть ознака

того, що в гнізді записана мітка або гніздо порожнє. Стан стрічки — це

дані, які гнізда зайняті, а які порожні.

 

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

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

управляється програмою, у яку можуть входити в будь-якій комбінації й

будь-якій кількості шість команд:

 

1) вправо;

 

2) уліво;

 

3) поставити мітку;

 

4) стерти мітку;

 

5) передача керування на один номер команди в програмі, якщо в поточнім

гнізді є мітка; якщо мітки ні, те передача керування на інший номер

команди;

 

6) припинення роботи.

 

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

 

?????????0?Машина Поста, незважаючи на зовнішню простоту, може робити

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

програму, яка ці обчислення зробить.

 

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

 

Машина одержала ім'я математика Є. Поста (США) і вирішує наступну

проблему: якщо для рішення завдання можна побудувати машину Поста, то

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

 

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

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

 

 

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

на це питання дається у вигляді так званого тези Поста: усякий алгоритм

представимо у формі машини Поста. Це теза тому, що його неможливо

довести, тому що в ньому фігурують, з одного боку, інтуїтивне поняття

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

 

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

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

 

0

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