↑ Вгору

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

Машина Поста


читати

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

зберегти

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

друкувати

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

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

Машина Поста

Машина Поста складається з необмеженої в обидва боки стрічки,
розділеної на гнізда, послідовно пронумеровані цілими числами, як
позитивними, так і негативними. У кожнім гнізді стрічки стоїть ознака
того, що в гнізді записана мітка або гніздо порожнє. Стан стрічки — це
дані, які гнізда зайняті, а які порожні.

Крім стрічки є головка читання/запису, який: уміє рухатися вперед, назад
і стояти на місці; уміє читати вміст, стирати й записувати мітку;
управляється програмою, у яку можуть входити в будь-якій комбінації й
будь-якій кількості шість команд:

1) вправо;

2) уліво;

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

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

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

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

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

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

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

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

Машина Поста й машина Тьюринга еквівалентні по своїх можливостях.
Розроблені практично в те саме час (в 1936 р.) незалежно друг від друга.


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

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


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