Машина Тьюринга - Поста.

Имеется устройство просматривающее бесконечную ленту, где есть ячейки содержащие элементы алфавита: , где- пустой символ (пустое слово), который может принадлежать и не принадлежатьА. Также существует управляющая головка (устройство) (УУ)/(УГ), которая в начальный момент расположена в определенном месте, в состоянии . Также существуют внутренние состояния машины:

Слово в данном алфавите - любая конечная упорядоченная последовательность букв данного алфавита, притом длина слова это количество букв в нем (у пустого слова длина 0).

Допустимые команды:

1) ,где. 2) (остановка программы).

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

39.

Тип машины перерабатывающий слова, в которой существует некий алфавит , для которогоW - множество всех слов.

Допустимые команды: (Для машин этого типа важна последовательность команд.)

где	Пример: Программа:

40.

Вычислимая функция от нескольких натуральных переменных

( f – может быть не всюду определенной )

f – называется вычислимой, если такая машина Тьюринга, которая её вычисляет.

- разрешимое множество, если характеристическая функция

- является вычислимой.

Множество называется перечислимым, еслитакая вычислимая функция

М - разрешимо М и N \M перечислимы.

М – перечислимо М – область определения некоторой вычислимой функции.

Множество всех формул F – некоторое разрешимое подмножество V.

Т – счетное множество, если его биективное отображение наV.

- обозначение счетного множества. (- алеф-нуль)

Если и зафиксировано биективное и вычислимое отображение(вычис.),

то L – ансамбль.

V – ансамбль (слова лексикографически упорядочены и занумерованы)

41.

Время — основной параметр, характеризующий быстродействие алгоритма. Называется также вычислительной сложностью. Для упорядочения важны худшее, среднее и лучшее поведение алгоритма в терминах размера списка (n). Для типичного алгоритма хорошее поведение — это O(n log n) и плохое поведение — это O(n²). Идеальное поведение для упорядочения — O(n). Алгоритмы сортировки, использующие только абстрактную операцию сравнения ключей всегда нуждаются по меньшей мере в O(n log n) сравнениях в среднем;

42.

Символическая нечеткая логика

Символическая нечеткая логика основывается на понятии t-нормы. После выбора некоторой t-нормы (а её можно ввести несколькими разными способами) появляется возможность определить основные операции над пропозициональными переменными: конъюнкцию, дизъюнкцию, импликацию, отрицание и другие. Нетрудно доказать теорему о том, что дистрибутивность, присутствующая в классической логике, выполняется только в случае, когда в качестве t-нормы выбирается t-норма Гёделя. Кроме того, в силу определенных причин, в качестве импликации чаще всего выбирают операцию, называемую residium (она, вообще говоря, также зависит от выбора t-нормы). Определение основных операций, перечисленных выше, приводит к формальному определению базисной нечеткой логики, которая имеет много общего с классической булевозначной логикой (точнее, с исчислением высказываний). Существуют три основных базисных нечетких логики: логика Лукасевича, логика Гёделя и вероятностная логика (Product logic). Интересно, что объединение любых двух из трех перечисленных выше логик приводит к классической булевозначной логике.