Порядок записи элементов множества не является существенным в отличие от записи элементов векторов, где порядок важен

1. Основные понятия теории множеств (множество, пустое множество, универсальное множество, подмножество, булеан). Мощность множества, равномощные множества. Конечные, бесконечные и счётные множества. Способы задания множеств.

Множество - это совокупность определённых различаемых объектов, причём таких, что для каждого можно установить, принадлежит этот объект данному множеству или нет.

Множества обычно обозначаются заглавными латинскими буквами, а элементы множества - строчными. Элементами множеств могут быть любые объекты, например, числа, символы, слова, объекты реального мира. В частности, элементами множества могут быть другие множества.

Например:

A = { a, b, c } - множество A состоящее из 3 элементов

N = { 1, 2, 3, … } - множество N целых чисел

Элементы множества являются уникальными, то есть, один и тот же элемент не может включаться в множество несколько раз (в отличие от векторов и мультимножеств). Считается, что при добавлении в множество элемента, который в нем уже присутствует, множество не меняется.

Порядок записи элементов множества не является существенным (в отличие от записи элементов векторов, где порядок важен).

Таким образом, множества считаются равными, если они состоят из одних и тех же элементов.

Если некоторый объект является элементом множества , то этот факт записывается следующим образом: и читается «x принадлежит А». Аналогично, если элемент не является элементом множества , используется запись («y не принадлежит А»).

Пустое множество – это множество, не содержащее элементов. Пустое множество может быть обозначено с использованием фигурных скобок: = { }. Однако, множество B = {} не является пустым: это множество, содержащее один элемент, который является пустым множеством.

Универсальное множество Е – множество всех объектов, рассматриваемых в данной задаче.

Конечные и бесконечные множества.Если количество элементов множества конечно (то есть существует натуральное число, равное количеству элементов множества), то такое множество называется конечным.В противном случае множество называется бесконечным.

Мощность множества или кардинальное число |A| (иногда card(A)). Мощность множества является обобщением понятия количества элементов на бесконечные множества. Для конечных множеств мощность равна количеству элементов множества.

Мощность пустого множества по определению равна нулю: .

Равномощные множества – это множества, между элементами которых можно установить взаимно однозначное соответствие.

Счётное множество – множество, равномощное множеству натуральных чисел.

Множество А называют подмножеством множества B (обозначается либо ) если все элементы, которые принадлежат множеству A, так же принадлежат и множеству B.

 

В этом случае B называют надмножеством A

Пустое множество является подмножеством любого множества.

Любое множество является подмножеством самого себя:

Любое множество является подмножеством универсального множества:

Два множества A и B равны тогда и только тогда, когда A является подмножеством B и B является подмножеством A.

Если множество A является подмножеством множества B, но A и B не равны, то в этом случае говорят что А является собственным подмножеством B (обозначается ).

Некоторые специальные множества: (Натуральные числа), (целые числа), (вещественные числа), (рациональные числа),

Способы задания множеств

Списком: Элементы множества записываются через запятую и обрамляются фигурными скобками.

 

Иногда, список может содержать многоточие: , однако такая запись не является строгой и может быть использована только там, где смысл её ясен. Более строго следовало бы записать .

Так же, для записи элементов с индексами иногда используется упрощенная запись

Описанием свойств элементов (или характеристическим предикатом): В фигурных скобках записывается обозначение элемента множества, от которого вертикально чертой отделяется логическая функция (предикат), определяющий принадлежность элементов множеству.

 

Такая запись читается «A – это множество таких x, что для них верно H(x)»

Например, множество четных чисел может быть задано в виде: (читается «A – множество таких натуральных чисел, которые делятся на 2»)

При задании подмножеств может использоваться сокращенная запись:

 

(«А – множество таких x, принадлежащих B, что x делится на 2»)

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

Например, множество четных чисел может быть задано в виде

 

Множество степеней двойки:

Словестным описанием. Описание должно быть точным и недвусмысленным, объективным.

Например: А = множество чётных чисел. B = множество белых ворон.

Множество хорошей музыки – не катит, т.к. воспринимается каждым по-своему.

Графическое. (Диаграммы Эйлера – Венна). Круг Эйлера - ограничивает множество. Рамка - универсальное множество.

Операции над множествами (объединение, пересечение, дополнение, разность, симметрическая разность, декартово произведение). Законы алгебры множеств. Способы доказательства законов алгебры множеств. Характеристические функции.

Операции над множествами (алгебра множеств)

Основные операции: объединение , пересечение , разность (), симметрическая разность , дополнение.

Объединение множеств – это множество, состоящее из элементов входящих в любое из множеств A или B:

 

Например, для множеств и результатом объединения будет:

 

Операция объединения может быть использована для объединения нескольких множеств:

Пересечение множеств – множество, содержащее элементы, входящие в оба множества одновременно:

 

Для множеств, приведенных выше:

Разность множеств – это подмножество элементов множества A, не входящих в B:

 

Для множеств, приведенных выше:

Разности AB и BA в общем случае не совпадают:

Симметрическая разность – состоит из элементов входящих либо в A либо в B, но не в оба множества сразу.

 

Для множеств, приведенных выше:

Дополнение до универсального множества - подмножество универсального множества, элементы которого не содержатся в A.

 

Для того что бы выписать элементы дополнения не достаточно знать только элементы множества A, необходимо так же задать элементы универсального множества E.

 

Графическое отображение операций на множествах: а, б) – исходные множества А и В, в) объединение г) пересечение д) разность AB, е) симметрическая разность, ж) дополнение A

 

Декартово (прямое) произведение множеств

Называется множество всех векторов (a,b), таких что и :

 

 

Мощность прямого произведения n множеств равна произведению мощностей соответствующих множеств.

Доказательство…. (Метод мат. индукции)

Характеристическая функция

Характеристическая функция пустого множества Характеристическая функция универсального множества

Способы доказательства тождеств на множествах

Графическое доказательство

Например, докажем тождество

С использованием характеристических функций

Докажем что

1) Характеристическая функции левой части:

 

2) Характеристическая функции правой части:

 

3) , следовательно

Кортежи. Декартово произведение множеств. Отношения, свойства отношений (рефлексивность, симметричность, транзитивность, антисимметричность). Операции на отношениях. Отношения эквивалентности и порядка.

Кортеж (вектор) – упорядоченная последовательность элементов. Элементы вектора – координаты или компоненты. Число компонент – размерность вектора.

Обозначение – в круглых скобках (иногда – в треугольных).

Проекция вектора на ось i – его i-й компонент.

Декартово (прямое) произведение множеств

Называется множество всех векторов (a,b), таких что и :

 

 

Мощность прямого произведения n множеств равна произведению мощностей соответствующих множеств.

Доказательство…. (Метод мат. индукции)

Отношения.

Если множества совпадают, то говорят что задаёт n-арные отношения. При n = 2 отношение называется бинарным. Далее будем рассматривать только бинарные отношения определенные на А.

Пустое отношение.

Пересечение Объединение Произведение

Понятие высказывания, основные операции с высказываниями, алгебра логики. Формулы алгебры логики. Значения формул и таблицы истинности. Классификация формул.

Высказывание — термин математической логики, обозначающий формализованную структурированную запись мысли с помощью буквенных символов и логических связок, рассматриваемую с точки зрения истинностных значений. Это утверждение, для которого оценивается логическое значение: ложь или истина. Логическое высказывание принято обозначать заглавными латинскими буквами. Является основным объектом логики высказываний.

Алгебра логики

Алгебраическая система (алгебра) – пара <G, M>, где G - это множество элементов (носитель), а M – множество операций, заданных на G… (n-арная операция на G задаёт отображение на G)  

Формулы алгебры логики.

Формулой является строка (знакосочетание), которая является пропозициональной переменной либо совпадает с одной из строк ( ), , ( , ( , ( … Для сокращения числа скобок в формуле принято опускать скобки, не влияющие на… Соглашение о порядке выполнения (приоритете, силе связывания) операций, позволяет отбросить скобки, связывающие разные…

Таблицы истинности.

Пример. x1=1, x2=1, x3=0. Определить значение формулы Если же ставится задача определить все возможные значения формулы, строится…

Пример.

Для формулы построить таблицу истинности.

В нашем примере 2²=4.

 

Равносильность формул. Основные тождества алгебры логики. Двойственные функции.

Равносильные формулы

Обозначение: А=В, читается А равносильно В. Примеры: x=xÙx, xÙ0=0, xÚØx=1. Легко видеть, что если А=В, то ØА=ØВ. Отношение равносильности обладает следующими свойствами:

Основные тождества (равносильные формулы) алгебры логики.

  Все тождества можно доказать, составив таблицы истинности. Если в тождестве заменить знак = на <-> то получится тавтология.

Правило отрицания

Для получения отрицания некоторого выражения достаточно заменить в нем знаки дизъюнкции знаками конъюнкции, знаки конъюнкции знаками дизъюнкции, а все аргументы – их отрицаниями. Если в выражении имеются константы их тоже надо заменить противоположными значениями.

Правило свертки

xÚØx Ùy=xÚy

xÙ(ØxÚy)=xÙy

Правило обобщенного склеивания (теорема П.С.Порецкого)

xyÚØyzÚxz=xyÚØyz

(xÚy)(ØyÚz)(xÚz)=(xÚy)(ØyÚz)

Преобразование импликации

x®y= ØxÚy;

Ø (x®y)= xÙØy

 

Двойственные функции

Пример (x & y)* = ¬(¬x & ¬y) = x Ú y. Теорема:Функция, двойственная к двойственной функции f равна самой функции… Доказательство. f*(x1,...,xn)* = (¬f(¬x1,...,¬xn))* = ¬¬f(¬¬x1,...,¬¬xn) = f(x1,...,xn)

Принцип двойственности.

Функция, двойственная к суперпозиции функций, равна суперпозиции двойственных функций. Точнее:

f₀(f₁,...,f_m)^* = f₀^*(f₁^*,...,f_m^*)

Полнота системы логических функций. Примеры полных систем. Классы логичиских функций и критерий Поста. Сигнатура алгебры логики.

Двойственные функции

Пример (x & y)* = ¬(¬x & ¬y) = x Ú y. Теорема:Функция, двойственная к двойственной функции f равна самой функции… Доказательство. f*(x1,...,xn)* = (¬f(¬x1,...,¬xn))* = ¬¬f(¬¬x1,...,¬¬xn) = f(x1,...,xn)

Принцип двойственности.

Функция, двойственная к суперпозиции функций, равна суперпозиции двойственных функций. Точнее:

f₀(f₁,...,f_m)^* = f₀^*(f₁^*,...,f_m^*)

Полные системы функций (связок).

Система {¬,∨,∧,→,↔} является полной. Система {¬,∨,∧} является полной. Именно она и составляет сигнатуру… Системы {¬,→}, {|} (штрих шеффера), так же полны.

Конъюнктивные и дизъюнктивные нормальные формы. Алгоритмы построения КНФ и ДНФ. Теоремы о тождественной ложности и тождественной истинности формул.

Дизъюнктивные и конъюнктивные нормальные формы.

Например: Элементарной дизъюнкциейназывается дизъюнкция переменных высказываний и (или)… Например:

Теорема о тождественной истинности формулы алгебры логики.

Доказательство. Пусть каждая элементарная дизъюнкция КНФ, равносильной исходной формуле,… Пусть исходная формула является тождественно истиной. Рассмотрим КНФ ей равносильную и предположим, что в некоторой…

Теорема о тождественной ложности формулы алгебры логики

Доказательство аналогично доказательству предыдущей теоремы.   Формула алгебры логики f называется логическим следствиемформулf1,f2,…,fm,если для любых наборов значений переменных,…

Совершенные КНФ и ДНФ. Способы построения совершенных нормальных форм. Разложение логических функций по переменным.

Совершенные нормальные формы.

Элементарная конъюнкция называется правильной,если в неё каждая переменная входит не более одного раза, включая её вхождение и под знаком… Элементарная конъюнкция называется полной относительно набора переменных если… Совершенной дизъюнктивной нормальной формой (СДНФ) называется дизъюнктивная нормальная форма, в которой нет одинаковых…

Построения СДНФ и СКНФ.

Построение СДНФ: 1. Преобразование исходной формулы в ДНФ (см выше): Шаг 1.

Преобразование ДНФ в СДНФ.

Если в ДНФ есть несколько одинаковых элементарных конъюнкций, то оставляем только одну - это преобразование приводит к равносильной формуле , т.к.… Шаг 4. Делаем все элементарные конъюнкции правильными с помощью следующих двух преобразований:

Алгоритм построения СКНФ.

Преобразование исходной формулы в КНФ.

Шаг 1.

Преобразовать исходную формулу к равносильному ей виду, в котором есть лишь операции конъюнкции, дизъюнкции и отрицания (перейти в сигнатуру алгебры логики), причём отрицания могут стоять лишь над элементарными переменными высказываниями.

Шаг 2.

Преобразовать полученную формулу к равносильному ей виду, в котором все дизъюнкции выполняются раньше, чем конъюнкции (применить дистрибутивный закон), т.е. построить КНФ для исходной формулы.

Преобразование КНФ в СКНФ.

Если в КНФ есть несколько одинаковых элементарных дизъюнкций , то оставляем только одну - это преобразование приводит к равносильной формуле ,т.к.… Шаг 4. Делаем все элементарные дизъюнкции правильными с помощью следующих двух преобразований:

Построение совершенных нормальных форм с помощью таблиц истинности

Для построения СДНФ отметим в таблице истинности те наборы значений переменных, на которых функция равна 1. Для каждого такого набора построим… Для построения СКНФ отметим в таблице истинности те наборы значений…  

Построение совершенных нормальных форм, используя принцип двойственности.

Построение совершенной конъюнктивной нормальной формы.

Построение совершенной дизъюнктивной нормальной формы.

Рассмотрим вместо исходной функции её отрицание и построим для полученной формулы алгебры логики её совершенную конъюнктивную нормальную форму. Взяв затем отрицания от левой и правой частей полученного выражения и применив, если это необходимо. закон де Моргана, а так же возможно упростив полученное выражение, получим совершенную дизъюнктивную нормальную форму для исходной функции.

 

Разложение функций алгебры логики по к переменным.

Теорема. Всякую логическую функцию f(x)=f(x1,x2,x3,…,xn) можно представить в виде (Знак конъюнкции со списком переменных под ним обозначает, что берётся конъюнкция выражения при всех возможных…

Проблема разрешимости в алгебре логики. Логическое следствие. Основные схемы доказательств.

Тавтологии и противоречия. Проблема разрешимости в алгебре логики. Логические следствия.

Формула алгебры логики называется тождественно истиной, общезначимой или тавтологией,если она принимает значение 1 при всех значениях входящих в неё… Будем обозначать тавтологию F, где F - тождественно истинная формула, а… Примеры тавтологий: xÚØx и x®(y®x).

Теорема о тождественной истинности формулы алгебры логики.

Доказательство. Пусть каждая элементарная дизъюнкция КНФ, равносильной исходной формуле,… Пусть исходная формула является тождественно истиной. Рассмотрим КНФ ей равносильную и предположим, что в некоторой…

Теорема о тождественной ложности формулы алгебры логики

Доказательство аналогично доказательству предыдущей теоремы.   Формула алгебры логики f называется логическим следствиемформулf1,f2,…,fm,если для любых наборов значений переменных,…

Теорема о логическом следствии

Доказательство. Пусть n - количество различных переменныхf, входящих в формулы g и f,и а n -… Пусть gf ,покажем что .

Теорема о противоречивости множества формул алгебры логики

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

Для доказательства теоремы используется теорема 4 и определение операции импликации.

 

Теорема о тождественной истинности формулы алгебры логики

,если в качестве логического следствия из и можно вывести противоречие.

 

Основные схемы доказательств

Доказательство теорем типа “если x, то y”. Схема доказательства основана на следующем логическом следствии: .

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

Каноническая задача минимизации - минимизировать число букв в нормальной форме. Таблица 1 – Табличное задание ФАЛ № наб. x2 x1 …  

Методы минимизации

1. Расчетный метод (метод непосредственных преобразований). 2. Расчетно-табличный метод (метод Квайна-МакКласки). 3. Метод Петрика (развитие метода Квайна-МакКласки).

Этапы минимизации

1 этап - переход от СДНФ к сокращенной ДНФ (СокрДНФ). СокрДНФ - это форма ФАЛ, членами которой являются изолированные (несклеивающиеся) элементарные… 2 этап - переход от СокрДНФ к тупиковой ДНФ (ТДНФ). ТДНФ - это форма ФАЛ,… 3 этап - переход от ТДНФ к минимальной форме. Этот этап основывается на использовании групповых инверсий и скобочных…

Формальные системы. Алфавит, формулы, аксиомы, правила вывода. Разрешимость формальной системы. Интерпретация формальной системы.

     

Исчисление высказываний как формальная система. Правила вывода. Язык и интерпретация исчисления высказываний. Общезначимость, выполнимость, следование. Полнота и непротиворечивость исчисления высказываний.

 

 

Исчисление высказываний:

Формальная система, в которой выводятся общезначимые формулы логики высказываний и только они.

Позволяет выводить все общезначимые формулы из аксиом, не рассматривая их интерпретации.

Интерпретация языка высказываний:

 

Правила вывода см. вопрос 11.

 

 

 

Связь между логикой и исчислением высказываний. Способы доказательства общезначимости формул логики высказываний и выводимости формул в исчислении высказываний. Метод резолюций в исчислении высказываний.

Доказательство общезначимости:

Семантические методы:

Связь между алгеброй логики и исчислением высказываний:

Формулы исчисления высказываний можно интерпретировать как формулы алгебры логики.

Теорема. Каждая формула, доказуемая в исчислении высказываний является тавтологией в алгебре логики.

Обратная теорема. Каждая тождественно истинная формула (тавтология) алгебры логики доказуема в исчислении высказываний.

 

Понятие предиката. Область определения и множество истинности предикатов. Интерпретация исчисления предикатов и значение формул логики предикатов. Общезначимость и выполнимость формул логики предикатов. Чистая и прикладная логика предикатов.

Предика́т (n-местный, или n-арный) — это функция с множеством значений (или «ложь» и «истина»), определённая на множестве . Таким образом, каждый набор элементов множества M характеризуется либо как «истинный», либо как «ложный».

Предикат называют тождественно-истинным и пишут:

 

если на любом наборе аргументов он принимает значение 1.

Предикат называют тождественно-ложным и пишут:

 

если на любом наборе аргументов он принимает значение 0.

Предикат называют выполнимым, если хотя бы на одном наборе аргументов он принимает значение 1.

Так как предикаты принимают только два значения, то к ним применимы все операции булевой алгебры, например: отрицание, импликация, конъюнкция, дизъюнкция и т. д.

 

Множество М, на котором определен предикат Р(x), называется областью определения предиката Р(x).

Множество всех элементов , при которых предикат принимает значения “истина” (1), называется множеством (областью) истинности предиката Р(x), т.е. множество истинности предиката Р(х)- это множество или иначе: или так: Так, например, предикат Р(x) – “x – простое число” определен на множестве N, а множество истинности I_P для него есть множество всех простых чисел.

Предикат Q(x) – “sinx=0” определен на множестве R, а его множеством истинности является

 

 

Исчисление предикатов

Алфавит ИППП состоит из: · предметных переменных , , , ... (для их обозначения используются… · предметных констант , , , ... (для их обозначения используются строчные буквы из начала латинского…

Значение формулы логики предикатов.

При конкретных значениях каждого из трех видов переменных формула логики предикатов становится высказыванием, имеющим истинное или ложное… В качестве примера рассмотрим формулу , (1) в которой двухместный предикат… В формулу (1) входит переменный предикат P(x,y), предметные переменные x,y,z, две из которых y и z – связанные…

Кванторы существования и всеобщности. Логические суждения с кванторами. Область действия кванторов, связанные и свободные переменные. Эквивалентные отношения в логике предикатов.

В предикатной логике, квантор существования (экзистенциальный квантификатор) — это предикат свойства или отношения для, по крайней мере, одного элемента области определения. Он обозначается как символ логического оператора ∃ (произносится как «существует» или «для некоторого»). Квантор существования отличается от квантора всеобщности, который утверждает, что свойство или отношение выполняется для всех элементов области.

Квантор всеобщности (обозначения: , ∀) — это условие, которое верно для всех обозначенных элементов, в отличие от квантора существования, где условие верно только для каких-то отдельных из указанных чисел. Формально говоря, это квантор, используемый для обозначения того, что множество целиком лежит в области истинности указанного предиката. Читается как: «для всех…», «для каждого…» или «каждый…», «любой…», «для любого…».

 

Эквивалентные отношения в логике предикатов см. тетрадь.

Понятие алгоритма. Неформальное (интуитивное) определение алгоритма. Примеры алгоритмов. Основные свойства алгоритмов. Роль алгоритмов в информатике. Алгоритмические проблемы. Машина Тьюринга - описание и примеры. Рекурсивные функции.

Алгори́тм — набор инструкций, описывающих порядок действий исполнителя для достижения результата решения задачи за конечное число действий.

Рассмотрим пример алгоритма для нахождения середины отрезка при помощи циркуля и линейки.
Алгоритм деления отрезка АВ пополам:
1) поставить ножку циркуля в точку А;
2) установить раствор циркуля равным длине отрезка АВ;
3) провести окружность;
4) поставить ножку циркуля в точку В;
5) провести окружность;
6) через точки пересечения окружностей провести прямую;
7) отметить точку пересечения этой прямой с отрезком АВ.

Основными свойствами алгоритма являются:

1. детерминированность (определенность). Предполагает получение однозначного результата вычислительного процecca при заданных исходных данных. Благодаря этому свойству процесс выполнения алгоритма носит механический характер;

2. результативность. Указывает на наличие таких исходных данных, для которых реализуемый по заданному алгоритму вычислительный процесс должен через конечное число шагов остановиться и выдать искомый результат;

3. массовость. Это свойство предполагает, что алгоритм должен быть пригоден для решения всех задач данного типа;

4. дискретность. Означает расчлененность определяемого алгоритмом вычислительного процесса на отдельные этапы, возможность выполнения которых исполнителем (компьютером) не вызывает сомнений.

 

Понятие алгоритма — одно из основных в программировании и информатике. Это последовательность команд, предназначенная исполнителю, в результате выполнения которой он должен решить поставленную задачу. Алгоритм должен описываться на формальном языке, исключающем неоднозначность толкования. Запись алгоритма на формальном языке называется программой. Иногда само понятие алгоритма отождествляется с его записью, так что слова «алгоритм» и «программа» — почти синонимы. Небольшое различие заключается в том, что под алгоритмом, как правило, понимают основную идею его построения. Программа же всегда связана с записью алгоритма на конкретном формальном языке.

 

 

Пе­ре­чис­лим не­ко­то­рые важ­ные ал­го­рит­ми­че­с­кие про­бле­мы.

1. Про­бле­ма са­мо­при­ме­ни­мо­сти. Су­ще­ст­ву­ет ли ал­го­ритм, по­зво­ля­ющий по про­из­во­ль­но­му на­ту­ра­ль­но­му чис­лу x от­ве­чать на во­прос: "схо­ди­т­ся ли j_x(x)?". Со­глас­но те­зи­су Чёр­ча-Кли­ни эту про­бле­му мож­но пе­ре­фор­му­ли­ро­вать в сле­ду­ющей эк­ви­ва­ле­нт­ной фор­ме: "су­ще­ст­ву­ет ли об­ще­ре­кур­сив­ная фун­кция g₀ та­кая, что g₀«1, ес­ли j_x(x) схо­ди­т­ся и g₀«0, ес­ли j_x(x) рас­хо­ди­т­ся?".

2. Про­бле­ма оста­но­вки [Род­жерс,1972,с.43]. Су­ще­ст­ву­ет ли ал­го­ритм, по­зво­ля­ющий по про­из­во­ль­ной па­ре на­ту­ра­ль­ных чи­сел (x,y) от­ве­чать на во­прос: "Схо­ди­т­ся ли j_x(y)?". Со­глас­но те­зи­су Чёр­ча-Кли­ни эту про­бле­му мож­но пе­ре­фор­му­ли­ро­вать в сле­ду­ющей эк­ви­ва­ле­нт­ной фор­ме: "су­ще­ст­ву­ет ли об­ще­ре­кур­сив­ная фун­кция g от двух пе­ре­мен­ных та­кая, что g(x,y)«1, ес­ли j_x(y) рас­хо­ди­т­ся и g(x,y)«0, ес­ли j_x(y) рас­хо­ди­т­ся?".

3. Про­бле­ма об­ще­ре­кур­сив­но­сти [Род­жерс,1972,с.45]. Су­ще­ст­ву­ет ли ал­го­ритм, по­зво­ля­ющий по про­из­во­ль­но­му на­ту­ра­ль­но­му чис­лу x от­ве­чать на во­прос: "Яв­ля­ет­ся ли n-мес­тная фун­кция j_x об­ще­ре­кур­сив­ной?". Со­глас­но те­зи­су Чёр­ча-Кли­ни эту про­бле­му мож­но пе­ре­фор­му­ли­ро­вать в сле­ду­ющей эк­ви­ва­ле­нт­ной фор­ме: "Су­ще­ст­ву­ет ли об­ще­ре­кур­сив­ная фун­кция t(x) та­кая, что t(x)«1, ес­ли j_x - n-мес­тная об­ще­ре­кур­сив­ная фун­кция и t(x)«0 в про­тив­ном слу­чае?".

Машина Тьюринга:

Описание машины Тьюринга

Пример машины Тьюринга

Приведём пример МТ для умножения чисел в унарной системе счисления. Машина работает по следующему набору правил:

Набор правил	Набор правил
q0*→q0*R	q4a→q4aR
q01→q01R	q4=→q4=R
q0×→q1×R	q41→q41R
q11→q2aR	q4*→q51R
q21→q21L	q5 →q2*L
q2a→q2aL	q6a→q61R
q2=→q2=L	q6×→q7×R
q2×→q3×L	q7a→q7aR
q31 → q4aR	q71→q2aR
q3a→q3aL	q7=→q8=L
q3*→q6*R	q8a→q81L
q4×→q4×R	q8×→q9×N

Умножим с помощью МТ 3 на 2 в единичной системе:

 

В протоколе указаны начальное и конечное состояния МТ, начальная конфигурация на ленте и расположение головки машины (подчёркнутый символ).

Рекурси́вная фу́нкция (от лат. recursio — возвращение) — это числовая функция числового аргумента, которая в своей записи содержит себя же. Такая запись позволяет вычислять значения на основе значений , подобно рассуждению по индукции. Чтобы вычисление завершалось для любого , необходимо, чтобы для некоторых функция была определена нерекурсивно (например, для ).

Примеры

Пример рекурсивной функции, дающей n-ое число Фибоначчи:

 

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