Студопедия  
Главная страница | Контакты | Случайная страница

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

Нормальные алгорифмы Маркова. Тезис Черча.

 

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

Другие способы реализации понятия алгоритма. Нормальные алгорифмы (алгоритмы) Маркова. Программная реализация нормальных алгоритмов Маркова. Понятие о машинах Поста. Тезис Черча.

1. Машина Тьюринга с внешним алфавитом А = { , 1}, где - «пустой» символ определяется следующей программой:

Остановится ли когда-нибудь эта машина, если она начнет перерабатывать следующее слово (в начальный момент, в состоянии машина обозревает ячейку, в которой записана самая левая буква перерабатываемого слова):

a) 111 1;

б) 11 11а 1;

в) 111111;

г) 1 1;

д) 11 11;

е) 1;

ж) l l l l;

з) 111;

и) l l l;

к) 11 11.

Если остановка происходит, то какое слово получается в результате, какая ячейка и в каком (перед остановкой) состоянии обозревается?

 


Дата добавления: 2015-09-12; просмотров: 22 | Нарушение авторских прав

Тема 16. Случайные величины и их числовые характеристики | Тема 17. Случайные векторы и совместные распределения случайных величин. | РАЗДЕЛ 7. Математическая статистика. | Стьюдента, Фишера, Пирсона. | Тема 22. Эйлеровы и гамильтоновы графы. Теорема Эйлера. | О максимальном потоке. | И конъюнктивная нормальные формы. | Тема 29. Теорема о полных классах булевых функций. | Истинность формул в модели. | Примеры теорий первого порядка. |


lektsii.net - Лекции.Нет - 2014-2020 год. (0.008 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав