Головна

Машина Поста складається з (с11)

  1.  I. Постановка і стан теми
  2.  III. Постановка питання
  3.  III. Вчення про трёхіпостасном людині Діаса Валєєва
  4.  Алгоритм застосування критерію Колмогорова - Смирнова для зіставлення емпіричного і теоретичного (іншого емпіричного) розподілів
  5.  Аналіз виконання договірних зобов'язань за обсягом поставки
  6.  Аудиторських перевірок постановки бухгалтерського обліку і внутрішньобанківського контролю
  7.  Б. Інтеграційна функція полягає в регламентації, впорядкування всієї сукупності суспільних відносин, виробленню норм поведінки людей у ??всіх сферах суспільного життя.

нескінченної стрічки, Поділеної на однакові осередки (секції). Осередок може бути порожньою або містити мітку (прийнято позначати символом V),

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

Рис.1. У кожен момент часу каретка вказує на одну з осередків

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

Кареткою управляє програма, що складається з рядків команд. Всього для машини Посту існує шість типів команд. Кожна команда має наступний синтаксис:

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

Варіанти закінчення виконання програми на машині Посту:

· Останов по команді "стоп". Такий останов називається результативним і вказує на коректність алгоритму;

· Останов при виконанні неприпустимою команди. Випадки, коли головка повинна записати мітку там, де вона вже є, або стерти мітку там, де її немає, є аварійними (неприпустимими). В цьому випадку зупинка називається безрезультатним;

· Машина не зупиняється ніколи. Догляд в нескінченність, зациклення. Машина Поста в результаті роботи алгоритму може взагалі не зупинитися (ніколи не дійти до команди «стоп» і ніколи не завершитися аварійною ситуацією). У цьому і в попередньому випадку ми маємо справу з некоректним алгоритмом (програмою).

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

Елементарні дії (команди) машина Посту простіше команд машини Тьюринга. Тому програми для машини Поста мають більше число команд, ніж аналогічні програми для машини Тьюринга.

приклади:

Покажемо, як можна скористатися командою умовного переходу для організації циклічного процесу. Нехай на стрічці є запис з декількох міток поспіль, і головка знаходиться над самої крайньої міткою справа. Потрібно перевести головку вліво до першої порожній позиції. (З12)

Зупинимося на представленні чисел на стрічці машини Посту і виконанні операцій над ними.

Число k представляється на стрічці машини Посту йдуть підряд k + 1 мітками (одна мітка означає число «0»). Між двома числами робиться інтервал як мінімум з одним порожнім секції на стрічці. Потрібно збільшити число 3 на одиницю (змінити значення в пам'яті з 3 на 4). Припустимо, точно відомо, що каретка стоїть десь зліва від міток і оглядає вільну позицію. Тоді програма збільшення числа на одиницю може виглядати так: (З 13)

Gt; 2

2? 1, 3

Lt; - 4

V 5

5!

Зациклення: зона роботи для будь-якого початкового стану обмежена одним і тим же числом осередків, які залежать від обраного початкового стану стрічки:

1. -> 2

2. <- 1

 



 Машина Поста. |  Практичні завдання.

 Основи аналізу алгоритмів. |  Стратегії алгоритмів. |  Введення в теорію алгоритмів. |  Основні типи алгоритмічних моделей. (С8) |  Машина Тьюринга. |  Граф переходів |  Визначення обчислюваності по Тьюрингу. (С25) |  Приклади (С27-С29) |  Послідовна композиція МТ. (С30-С31) |  Операція розгалуження (умовний оператор). (С32-С33) |

© um.co.ua - учбові матеріали та реферати