Машина Поста
З Вікіпедії, безкоштовно encyclopedia
Машина Поста (див.Еміль Пост) — це абстрактна (тобто така, що не існує в арсеналі техніки), але дуже проста обчислювальна машина. Машина Поста, хоча зовнішньо проста, може здійснювати різні обчислення, для чого потрібно задати початковий стан каретки і програму, яка виконає ці обчислення. Машиною ця математична конструкція названа тому, що при її побудові використовуються деякі поняття реальних машин (елемент пам'яті, команда тощо).
Машину Поста можна розглядати як спрощену модель комп'ютера. Насправді, як комп'ютер, так і машина Поста мають:
- неподільні носії інформації (комірки — біти), які можуть бути заповненими або незаповненими;
- обмежений набір елементарних дій — команд, кожна з яких виконується за один такт (крок).
Обидві машини працюють на основі програми. Проте у машині Поста інформація розташовується лінійно і читається підряд, а в комп'ютері можна читати інформацію за адресою; набір команд комп'ютера значно ширший і виразніший за команди машини Поста.