Информатика -продвинутый курс


         

Соответствующая схема МТ может иметь


Соответствующая схема МТ может иметь вид



































































































































аi



qi



q1



q2



0



0Пq1



1Cq2



1



1Пq1



2Cq2



2



2Пq1



3Cq2



3



3Пq1



4Cq2



4



4Пq1



5Cq2



5



5Пq1



6Cq2



6



6Пq1



7Cq2



7



7Пq1



8Cq2



8



8Пq1



9Cq2



9



9Пq1



0Cq2



-



-Лq1



1Cq2



2. Алгоритм записи числа в десятичной системе счисления.

Дана конечная последовательность меток, записанных в клетки ленты подряд, без пропусков. Требуется записать в десятичной системе число этих меток пересчитать метки).

Суть алгоритма может состоять в том, что к числу 0, записанному на ленте в начале работы машины, машина добавляет 1, стирая метку за меткой, так что вместо нуля возникает число 0 + k.

Легко могут быть построены алгоритмы сложения чисел, их перемножения, нападения наибольшего общего делителя и т.д. Однако, главная цель введения машин Поста и Тьюринга не программирование для них, а изучение свойств алгоритмов и проблемы алгоритмической разрешимости задач.

В зависимости от числа используемых лент, их назначения и числа состояний устройства управления можно рассматривать различные модификации машин Тьюринга.

Предположим, мы расширили определение МТ, добавив определенное состояние q. устройства управления машины. Будем говорить, что если устройство управления переходит в состояние q0 для заданного входного слова х, то машина допускает х; если устройство переходит в состояние qx, то машина запрещает х. Такую машину будем называть машиной Тьюринга с двумя выходами. Могут быть рассмотрены многочисленные варианты машины Тьюринга, имеющие некоторое конечное число лент. В каждой клетке этих лент может находиться один из символов внешнего алфавита А = {a0, a1, ..., аn}. Устройство управления машиной в каждый момент времени находится в одном из конечного множества состояний Q

= {q0, q1, ..., qm}. Для K-ленточной машины конфигурация ее в i-й момент времени описывается системой k-слов вида:


Содержание  Назад  Вперед