Головна

машини Тьюринга

  1.  II. 5. Умови виконання робіт. Вибір ведучої машини
  2.  Безлика жорстокість Великий Машини
  3.  Уздовж вулиці рядами стояли припарковані машини. Альберто раптом зупинився біля однієї з них - червоного спортивного автомобіля з відкинутим верхом.
  4.  Віртуальні машини
  5.  Всі вузли машини змонтовані на станині, прикріпленою до підлоги чотирма анкерними болтами 19. Нижня частина станини 18 виконана у вигляді корита.
  6.  Газодувние машини ТЕС
  7.  Газодувние машини ТЕС

Відомі випадки побудови школярами залізних машин Тьюринга з колесами.

Але машина Тьюринга - це все-таки перш за все метод математичного моделювання.

Машина Тьюринга включає:

1. Потенційно нескінченну (вправо) стрічку, розділену на осередки.

2. зчитувально-записує головку з пристроєм управління (УУ).

3. Алфавіт внутрішніх станів {q0, q1... qn}.

4. Вхідний-вихідний алфавіт.


Визначається початкова конфігурація. Головка дивиться на якусь комірку і пристрій управління знаходиться в початковому стані q1.

Пристрій управління на підставі ліченого з осередку символу і внутрішнього стану пише в клітинку символ (можливо, той же самий), здійснює дію D і переходить в нове внутрішній стан (можливо колишнє). Це і є команда Машини Тьюринга, яку можна записати так:

aiqi ® ajDjqj.

D = {Л, П, С} - безліч дій.

Л - вліво, П - вправо, С - стояти.

Сукупність команд становить програму машини Тьюринга, яка зазвичай оформляється у вигляді таблиці.

Машина закінчує роботу, коли переходить в стан q0.

l - порожній символ.

Приклад: Побудуємо машину Т, яка в суцільний послідовності 1 стирає першу і дві останні. (L - порожній символ).

  q1 q2 q3 q4
 lПq2  1Пq2  lЛq4  lСq0
l -  lЛq3 - -

 




 алгоритм Краскала |  Завдання про 4 фарбах |  Визначення шляхів в графі |  Приведення графа до ярусно-паралельній формі |  Внутрішня стійкість графа |  ядро графа |  Побудова Кліки. |  морфізм груп |  Група Клейна четвертого ступеня |  поняття алгоритму |

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