Студопедия

Главная страница Случайная страница

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

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






  • Доказано.






    4. Доказано. Постройте программу машины Тьюринга, вычисляющую функцию f(x)=x-3

    Пусть внешним алфавитом данной МТ является множество A = {0, 1}. Число x на ленте машины записывать в виде набора из x единиц:

     
     


    Программа МТ выглядит следующим образом:

    q11→ 1Пq1; … q10→ 0Лq1; q10→ 0Лq1; q10→ 0Лq0.

    согласно которой для любой начальной конфигурации, когда считывающая головка обозревает одну из единиц, в каждый момент эта единица остается на месте, и головка сдвигается вправо на одну ячейку. Этот процесс продолжается до тех пор, пока головка не выйдет на пустую ячейку. Тогда в головка смещается влево и записывает 0, производит еще 2 такие операции. Машина перейдет в состояние q0.

    Стоит учесть, что если вводные данные меньше трех машина зацикливается и переходит в состояние q0.

    5. Суперпозиция (сложная функция) — это функция, полученная из некоторого множества функций путем подстановки одной функции в другую или отождествления переменных.

    Способы получения суперпозиций Рассмотрим две булевы функции: функцию от аргументов и функцию от аргументов .
    Тогда мы можем получить новую функцию из имеющихся двумя способами:

    · Подстановкой одной функции в качестве некоторого аргумента для другой;

    · Отождествлением аргументов функций.






    © 2023 :: MyLektsii.ru :: Мои Лекции
    Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.
    Копирование текстов разрешено только с указанием индексируемой ссылки на источник.