Рефераты | Рефераты по информатике, программированию | Формализация понятия алгоритма | страница реферата 7 | Большая Энциклопедия Рефератов от А до Я
Большая Энциклопедия Рефератов от А до Я
  • Рефераты, курсовые, шпаргалки, сочинения, изложения
  • Дипломы, диссертации, решебники, рассказы, тезисы
  • Конспекты, отчеты, доклады, контрольные работы

  • LqsЛ

    |qoЛ

    qs

    |qsЛ

    L!H

    Рис.3

    Обратите внимание, что если по ошибке в вход этой машине будет подано “пустое” слово, то она “зациклится”, т.е. будет бесконечно долго писать | . Действительно, единственно некоректной конфигурацией в начале работы будет сочетание qoL. По условию n>0. Поэтому в этом “неправильном” случае машина будет зацикливаться. Нетрудно подсчитать, что сложность этого алгоритма равна n+1.

    Пример 3. Построить Машину Тьюринга

    U((n)1)=(n)10 ,

    где n>0 и (n)10 - запись числа n в десятичной системе. Другими словами эта Машина Тьюринга приводит запись числа n из унарной формы в десятичную. Работу этой машины организуем следующим образом.

    Изначально на ленте находится слово из одних | символов и каретка находится над крайне правым | символом. Сотрем один символ |, а перед словом из символов | поставим цифру 1. Затем опять сотрем крайне правый символ | , а затем увеличим цифровую запись слева от слова из | на 1 и т.д. Обратим внимание, что стирать палочки  мы умеем, это делает Машина U2((n)1)=(n-1)1 и увеличивать десятичную запись числа на 1 тоже умеем, это делает машина U1((n)10)=(n+1)10. Программа для этой машины показана на рисунке 4.

    L

    |

    1

    2

    3

    4

    5

    6

    7

    8

    9

    0

    Нач. состояние

    Сти


    Рекомендуем скачать другие рефераты по теме: шпоры на экзамен, реферат по математике.



    Предыдущая страница реферата | 2  3  4  5  6  7  8  9  10  11  12 |




    Поделитесь этой записью или добавьте в закладки

       




    Категории:



    Разделы сайта




    •