Конспекты лекций по математической логике
Категория реферата: Рефераты по математике
Теги реферата: реферат статус, изложение по русскому языку 6
Добавил(а) на сайт: Анохин.
1 2 3 4 5 6 7 8 9 10 | Следующая страница реферата
10. Неформальное понятие алгоритма (последовательность инструкций для выполнения действия).
20. Машина с неограниченными регистрами (МНР).
30 Машина Тьюринга – Поста (МТ-П).
40 Нормальные алгоритмы Маркова (НАМ).
1.1.1 Машина с неограниченными регистрами (МНР).
Имеется некое устройство, в котором счетное число ячеек памяти (регистров), в которых хранятся целые числа.
Допустимые команды:
Z(n) - обнуление регистра Rn.
S(n) - увеличение числа в регистре Rn на 1.
T(m,n) - копирует содержимое Rm в регистор Rn.
I(p,q,n) - если содержимое Rp = Rq то выполняется команда с номером n , если нет следующая.
Программа для МНР должна быть последовательностью команд Z, S, T, I с определенным порядком, выполняемые последовательно.
Тезис Черча (Churcha): Первое и второе определение алгоритма эквивалентны между собой. Любой неформальный алгоритм может быть представлен в программе для МНР.
1.1.2 Машина Тьюринга - Поста.
Имеется устройство просматривающее бесконечную ленту, где есть ячейки содержащие
элементы алфавита: 
, где 
- пустой символ (пустое слово), который может принадлежать и не принадлежать
А. Также существует управляющая головка (устройство) (УУ)/(УГ), которая
в начальный момент расположена в определенном месте, в состоянии 
.
Также существуют внутренние состояния машины: 
Слово в данном алфавите - любая конечная упорядоченная последовательность букв данного алфавита, притом длина слова это количество букв в нем (у пустого слова длина 0).
Допустимые команды:
|
1) 2) |
Последовательность команд называется программой, если в этой последовательности не встречается команд с одинаковыми левыми частями. Машина останавливается если она не находит команды с левой частью подобной текущей. |
,где 
.
(остановка программы).1.1.3 Нормальные алгоритмы Маркова.
Тип машины перерабатывающий слова, в которой существует некий алфавит 
, для которого W - множество всех слов.
Допустимые команды: (Для машин этого типа важна последовательность команд.)
|
|
1 2 3 4 5 6 7 8 9 10 | Следующая страница реферата Поделитесь этой записью или добавьте в закладкиКатегории: |
где 