Конспекты лекций по математической логике

  • Вид работы:
    Реферат
  • Предмет:
    Математика
  • Язык:
    Русский
    ,
    Формат файла:
    MS Word
    266,07 kb
  • Опубликовано:
    2009-01-12
Вы можете узнать стоимость помощи в написании студенческой работы.
Помощь в написании работы, которую точно примут!

Конспекты лекций по математической логике

Конспекты лекций по математической логике 1.Теория алгоритмов 1.1 Различные подходы к определению алгоритма:

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) (остановка программы).

Похожие работы на - Конспекты лекций по математической логике

 

Не нашел материал для своей работы?
Поможем написать качественную работу
Без плагиата!