 |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
Пример машины Тьюринга
|
|
Приведём пример МТ для умножения чисел в унарной системе счисления. Машина работает по следующему набору правил:
| Набор правил | Набор правил |
| q0*→q0*R | q4a→q4aR |
| q01→q01R | q4=→q4=R |
| q0×→q1×R | q41→q41R |
| q11→q2aR | q4*→q51R |
| q21→q21L | q5 →q2*L |
| q2a→q2aL | q6a→q61R |
| q2=→q2=L | q6×→q7×R |
| q2×→q3×L | q7a→q7aR |
| q31 → q4aR | q71→q2aR |
| q3a→q3aL | q7=→q8=L |
| q3*→q6*R | q8a→q81L |
| q4×→q4×R | q8×→q9×N |
Умножим с помощью МТ 3 на 2 в единичной системе:
В протоколе указаны начальное и конечное состояния МТ, начальная конфигурация на ленте и расположение головки машины (подчёркнутый символ).
Рекурси́вная фу́нкция (от лат. recursio — возвращение) — это числовая функция 
числового аргумента, которая в своей записи содержит себя же. Такая запись позволяет вычислять значения на основе значений 
, подобно рассуждению по индукции. Чтобы вычисление завершалось для любого 
, необходимо, чтобы для некоторых функция была определена нерекурсивно (например, для 
).
Дата публикования: 2014-11-03; Прочитано: 712 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!
