Головна

Програма машини Тьюринга (Р) - сукупність всіх команд, програма представляється у вигляді таблиці і називається Тьюрінговой функціональною схемою

  1.  AnvSoft Photo Flash Maker Professional-програма для створення анімованих слайдшоу з супроводом з вашої улюбленої музики: http://depositfiles.com/files/t7m8xqaff
  2.  FE 70 ПРОГРАМА ПІДТРИМКИ НАВЧАЛЬНИХ ЗАКЛАДІВ
  3.  II. 5. Умови виконання робіт. Вибір ведучої машини
  4.  II.1. Зведена програма психологічного вивчення професійної компетентності вчителя
  5.  III. Порядок діяльності функціональної підсистеми
  6.  III. програма дій
  7.  IV. Статистичні таблиці
a0 a1 a2
q1 а0Пq1 a1Пq1 a2Лq2
q2 а1Пq2 a2НQ0 a0НQ0

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

 (4.9)

Робота машини Тьюринга:

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

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

ПРИКЛАД

Побудувати машину Тьюринга, яка буде прати останню одиницю в послідовності одиниць.

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

 

Перевіримо працездатність машини Тьюринга:

1.

2.

3.

4.

5.

Теза А. Черча. якщо функція здійсненна, То вона завжди може бути представлена ??у вигляді машини Тьюринга.




 Алгоритм Магу для визначення безлічі зовнішньої стійкості. |  Безліч шляхів у графі |  Алгоритм фронту хвилі. Пошук мінімального шляху в графі. |  Алгоритм фронту хвилі. |  Алгоритм приведення графа до ярусно-паралельній формі. |  Дерева і ліси |  Алгоритм отримання дерева з графа |  ТЕОРІЯ АЛГОРИТМІВ |  Функція-проекція |  Правило примітивної рекурсії |

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