Поможем написать любую работу на аналогичную тему
Алфавит – конечное или счетное множество символов, возможно, разбитых на группы. Алфавит должен быть упорядоченным множеством.
Слово – конечная упорядоченная последовательность символов алфавита, в т.ч. пустое слово.
V – множество всех слов.
Вычислимая функция от нескольких натуральных переменных
( f – может быть не всюду определенной )
f – называется вычислимой, если такая машина Тьюринга, которая её вычисляет.
- разрешимое
множество, если характеристическая функция
- является вычислимой.
Множество называется перечислимым, если 
такая вычислимая функция
М - разрешимо 
М
и N \M перечислимы.
М – перечислимо М – область определения некоторой вычислимой функции.
Множество всех формул F – некоторое разрешимое подмножество V.
Т – счетное множество, если 
его биективное отображение на V.
- обозначение счетного множества. (
- алеф-нуль)
Если и зафиксировано биективное и вычислимое отображение 
(вычис.),
то L – ансамбль.
V – ансамбль (слова лексикографически упорядочены и занумерованы)
Определение: В произвольном формальном исчислении: 
- множество всех аксиом – разрешимое подмножество множества всех формул.
Правило вывода:
,при разрешимо. Для ИВ N=2.
Пример:
(пустое слово) , 
1 и 2 – формальные выводы.
3 – не является формальным выводом.