Студопедия.Орг Главная | Случайная страница | Контакты | Мы поможем в написании вашей работы!  
 

Пример машины Тьюринга



Приведём пример МТ для умножения чисел в унарной системе счисления. Машина работает по следующему набору правил:

Набор правил Набор правил
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; Прочитано: 690 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!



studopedia.org - Студопедия.Орг - 2014-2024 год. Студопедия не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования (0.009 с)...