Студопедия

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

КАТЕГОРИИ:

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






Доказано.






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. Суперпозиция (сложная функция) — это функция, полученная из некоторого множества функций путем подстановки одной функции в другую или отождествления переменных.

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

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

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


Поделиться с друзьями:

mylektsii.su - Мои Лекции - 2015-2024 год. (0.006 сек.)Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав Пожаловаться на материал