Логический переход от посылок к заключению называется выводом.

Для логической правильности вывода необходимы следующие отношения:

а) если Р = «истина», то и S должна быть = «истина».

б) если Р = «ложь», то из «лжи» может следовать всё, что угодно, т.е. заключение S может быть и ложным и истинным.

Формула B называется логическим следствием формул A₁, A₂, …, A_n, если при любых значениях, входящих в них, элементарных высказываний формула B принимает значение истинно всякий раз, когда формулы A₁, A₂, …, A_nпринимают значение истинно. Обозначается A₁, A₂, …, A_n├ B.

Из определения логического следования вытекает:

1. Тавтология логически следует из любой формулы.

2. Из противоречия логически следует любая формула.

Теорема 1. Из A логически следует B тогда и только тогда, когда тавтологией является A B.

Теорема 2. A₁, A₂, …, A_n╞ B тогда и только тогда, когда является тавтологией

A₁& A₂& …& A_n B.

Теорема 3. Из формул A₁, A₂, …, A_n, B логически следует C тогда и только тогда, когда из формул A₁, A₂, …, A_nлогически следует B C.

Следствие 1. Из A и B логически следует C тогда и только тогда, когда тавтологией является

A (B C).

Следствие 2. Из формул A₁, A₂, …, A_n логически следует B тогда и только тогда, когда тавтологией является

A₁ (A₂ … (A_n B)…).

Дедуктивные умозаключения - те умозаключения, у которых между
посылками и заключениями имеется отношение логического следования.
Правила дедуктивного вывода определяются характером посылок,
которые могут быть простыми (категорическими) или сложными суждениями. В зависимости от количества посылок дедуктивные выводы из категорических суждений делятся на непосредственные, в которых заключение выводится из одной посылки, и опосредованные, в которых заключение выводится из двух посылок.

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

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

По качеству связи категорические суждения делятся на утвердительные
и отрицательные, например: S есть P, S не есть не P.

Обращением называется непосредственное умозаключение, в
котором в заключении (в новом суждении) субъектом является предикат, а
предикатом - субъекта исходного суждения, т. е. происходит перемена мест
субъекта и предиката при сохранении качества суждения. Например: S есть P -> P есть S.

Противопоставление предикату – это непосредственное умозаключение, при котором (в заключении) предикатом является субъект, субъектом - понятие, противоречащее предикату исходного суждения, и связка меняется на противоположную.

Например:

S есть P. -> не-P не есть S.

Иными словами, мы делаем таким образом:

1) вместо P берем не P;

2)меняем местами S и не-P;

3) связку меняем на противоположную.

Например, дано суждение: " Все львы - хищные животные". В результате
противопоставления предикату получим суждение: " Ни одно нехищное животное не является львом".

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

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

Категорические суждения - такие, в которых мысль утверждается или отрицается вполне определенно, без всяких условий, и которые имеют субъектно-предикатную структуру. Например: «Все адвокаты - юристы. Петров - адвокат. Петров – юрист».

Проанализируем структуру силлогизма. Понятия, входящие в состав силлогизма, называются терминами силлогизма. Различают меньший, больший и средний термины. Меньший термин - понятие, которое в заключении является субъектом (в нашем примере - понятие «Петров») и обозначается буквой «S». Больший термин - понятие, которое в заключении является предикатом («юрист») и обозначается «Р». Средний термин - понятие, которое входит в обе посылки и не входит в заключение («адвокат»), обозначается буквой «М». Схема силлогизма: «Все М есть Р. S есть М. S есть Р».

Объединенная классификация простых категорических суждений

«А» – общеутвердительные суждения. Их структура «Все S есть Р».

«I» – частноутвердительные суждения - «Некоторые S есть Р».

«Е» – общеотрицательные суждения - «Ни одно S не есть Р».

«О» – частноотрицательные суждения - «Некоторые S не есть Р».

Для иллюстрации отношений между простыми категорическими суждениями используется так называемый логический квадрат. Суждения называются совместимыми по истине, если они оба одновременно могут быть истинными. Отношения совместимости по истине: подчинение (отношения между А и I, Е и О), частичной совместимости (от-ношения между I и О). Суждения называются несовместимыми по истине, если они не могут быть одновременно истинными. Отношения несовместимости по истине: противоположность (между А и Е) и противоречие (между I и Е, и между А и О).

Закономерности по логическому квадрату:

- При отношениях подчинения действует следующая закономерность: если истинно общее (А или Е), то истинно частное (I или О); если ложно частное (I или О), то ложно общее (А или Е).

- При частичной совместимости: оба суждения могут быть одновременно истинными, но не могут быть одновременно ложными, поэтому: если одно ложное, то другое обязательно истинное.

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

Пример. Определите тип суждения «Некоторые студенты нашей группы пошли в кино» (А, Е, I, О). Сформулируйте стандартную форму данного суждения и остальных суждений с теми же субъектом и предикатом. Считая данное суждение истинным, определите истинность, ложность или неопределенность остальных суждений с теми же субъектом и предикатом по логическому квадрату.

Решение:

Суждение «Некоторые студенты нашей группы пошли в кино» - частноутвердительное ( I );

А: «Все студенты нашей группы пошли в кино» - неопределенное;

Е: «Ни один студент нашей группы не пошел в кино» - ложь.

О: «Некоторые студенты нашей группы не пошли в кино» - неопределенное.

Пример. Произведите отрицание суждения «Некоторые студенты нашей группы пошли в кино» таким образом, чтобы результат отрицания не содержал внешних знаков отрицания (с помощью логического квадрата).

Решение: Для суждения типа I противоречащим является суждение типа Е: «Ни один студент нашей группы не пошел в кино».

Индивидуальное задание

3 Запишите простой категорический силлогизм в виде формулы логики предикатов. Проверьте правильность рассуждения с помощью кругов Эйлера-Венна, методом резолюций.

3.1 Некоторые нелюбезные замечания вызывают раздражение. Ни одно критическое замечание не любезно. Значит, все критические замечания вызывают раздражение.

3.2 Я – человек. Ты – не я. Значит, ты – не человек.

3.3 Жизнь – борьба. Дзюдо – борьба. Значит, жизнь – дзюдо.

3.4 Все педагоги воспитанны. Он не педагог. Значит, он не воспитан.

3.5 Экспрессы здесь никогда не останавливаются. Ни один поезд сегодня здесь не остановился. Значит, все поезда, проходившие сегодня - экспрессы.

3.6 Большинство учителей имеет высшее образование. Иванов – учитель. Значит, Иванов имеет высшее образование.

3.7 Ни один ведущий редактор не подпишет непрочитанную рукопись. Иванов не является ведущим редактором. Значит, он подпишет непрочитанную рукопись.

3.8 Во всех городах за полярным кругом бывают белые ночи. Санкт-Петербург не находится за полярным кругом. Значит, в Санкт-Петербурге нет белых ночей.

3.9 Большая часть студентов нашей группы изучает английский язык. Петров – студент нашей группы. Значит, он изучает английский.

3.10 Все студенты нашей группы успешно сдали экзамены. Петров успешно сдал экзамен. Значит, он студент нашей группы.

3.11 Математическая логика изучает формы и законы правильного мышления. Учение о понятии есть часть математической логики. Следовательно, оно изучает законы и формы правильного мышления.

3.12 Мысль - это движение. Движение есть свойство всей материи. Значит, мысль есть свойство всей материи.

3.13 Все школьники сдают экзамены. Васильев не является школьником. Следовательно, Васильев не сдает экзамены.

3.14 Закон противоречия – закон мышления. Закон противоречия сформулирован Аристотелем. Значит, некоторые законы мышления сформулировал Аристотель.

3.15 Некоторые студенты – спортсмены. Иванов – студент. Значит, он – спортсмен.

4 В приведенных силлогизмах установите следствие, большую и меньшую посылки, проверьте достоверность вывода.

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

4.2 Ни один невиновный не должен быть привлечен к уголовной ответственности. Значит, Н. не должен быть привлечен к уголовной ответственности, так как он невиновен.

4.3 Некоторые деятели искусства – талантливые люди. Значит, некоторые писатели талантливы, ибо все писатели – деятели искусства.

4.4 Некоторые металлы не тонут в воде, так как натрий металл, а натрий не тонет в воде.

4.5 Иванов не является сильным шахматистом, поэтому он не знает теорию шахматной игры, а все сильные шахматисты знают теорию шахматной игры.

4.6 Некоторые рыбы не мечут икру, так как голомянка не мечет икру, а голомянка – рыба.

4.7 Все студенты 1 курса изучают иностранные языки, значит, Петров – студент первого курса, так как он изучает иностранные языки.

4.8 Ни одна книга не является ненужной. Некоторые учебники – книги. Значит, все учебники нужны.

4.9 Ни один человек не лишен способностей. Некоторые люди – студенты. Значит, некоторые, лишенные способностей, не студенты.

4.10 Существуют равнобедренные треугольники. Не все треугольники равносторонние. Значит, некоторые равнобедренные треугольники - равносторонние.

4.11 Некоторые параллелограммы - ромбы, все ромбы – четырехугольники, значит некоторые четырехугольники – не ромбы.

4.12 Все круглые предметы не имеют углов, значит все треугольные предметы не могут быть круглыми;

4.13 Не все треугольники - равносторонние. Значит, какие-то равнобедренные треугольники – не равносторонние.

4.14 Имеются положительные числа. Ни одно отрицательное число не является натуральным. Значит, некоторые натуральные числа положительные.

4.15 Все зайцы не хищники, некоторые хищники - волки, значит, все волки - не зайцы.

Теория алгоритмов

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

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

Машина Тьюринга представляет собой автомат, с конечным числом состояний, соединенный с внешней памятью – лентой, разбитой на ячейки, в каждой из которых записан один из символов конечного алфавита А= { a1, ... am}.

Автомат связан с лентой с помощью головки, которая в каждый момент времени обозревает одну ячейку ленты, и в зависимости от символа в этой ячейке и состояния управляющего устройства записывает в ячейку символ (совпадающий с прежним или пустой), сдвигается на ячейку вправо или влево или остается на месте. Среди состояний управляющего устройства выделим начальное состояние и заключительное состояние . В начальном состоянии машина находится перед началом работы. Попав в заключительное состояние, машина останавливается. Т. о. память машины Т – это конечное множество состояний (внутренняя память) и лента (внешняя память). Лента бесконечна в обе стороны, однако в любой момент времени лишь конечный отрезок ленты будет заполнен символами. Поэтому важна не фактическая бесконечность ленты, а ее неограниченность, т.е. возможность писать на ней сколь угодно длинные, но конечные слова.

Данные в машине Т – это слова в алфавите ленты; на ленте записываются и исходные данные и окончательные результаты. Элементарные шаги – это считывание и запись символов, сдвиг головки на ячейку влево или вправо, а также переход управляющего устройства в следующее состояние.

Детерминированность машины Т определяется следующим образом: для любого внутреннего состояния qiи символа aj однозначно заданы:

а) следующее состояние qi`;

б) символ aj`, который надо записать в ту же ячейку вместо aj(стирание – это запись пустого символа );

в) направление сдвига головки dk(L – влево, R – вправо, E – на месте).

Это задание может описываться:

− системой правил:

qiaj qi`aj`dk;

− таблицей, строкам которой соответствуют состояния, столбцам – входные символы, а на пересечении записана тройка символов:

− qi`aj`dk;

− блок-схемой (диаграммой переходов), в которой состояниям соответствуют вершины, а правилу вида: qiaj qi`aj`dk– ребро, ведущее из qi в qi`.

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

Полное состояние будем называть конфигурацией или машинным словом. Стандартной начальной конфигурацией называется конфигурация вида q1 , то есть конфигурацию, содержащую начальное состояние, в котором головка обозревает крайний левый символ слова, написанного на ленте. Аналогично, стандартной заключительной конфигурацией называется конфигурация вида . Ко всякой незаключительной конфигурации К машины Т применима ровно одна команда вида:

qiaj qi`aj`dk,

которая конфигурацию К переводит в конфигурацию К. Последовательность вида: К1 К2 К3... однозначно определяется исходной конфигурацией К1и полностью описывает работу машины Т, начиная с К1.

На примере машины Тьюринга хорошо прослеживаются свойства алгоритмов, так как машина Тьюринга обладает всеми свойствами алгоритма:

1) дискретность − машина Тьюринга может перейти к (к + 1) - му шагу только после выполнения каждого шага, т.к именно каждый шаг определяет, каким будет (к + 1) - й шаг;

2) понятность − на каждом шаге в ячейку пишется символ из алфавита, автомат делает одно движение (Л, П, Н), и машина Тьюринга переходит в одно из описанных состояний;

3) детерминированность − в каждой клетке таблицы машины Тьюринга записан лишь один вариант действия, на каждом шаге результат определен однозначно, следовательно, последовательность шагов решения задачи определена однозначно, т. е. если машине Тьюринга на вход подают одно и то же входное слово, то выходное слово каждый раз будет одним и тем же;

4) результативность − содержательно результаты каждого шага и всей последовательности шагов определены однозначно, следовательно, правильно написанная машина Тьюринга за конечное число шагов перейдет в состояние q0, т.е. за конечное число шагов будет получен ответ на вопрос задачи;

5) массовость − каждая машина Тьюринга определена над всеми допустимыми словами из алфавита, в этом и состоит свойство массовости. Каждая машина Тьюринга предназначена для решения одного класса задач, т.е. для каждой задачи пишется своя (новая) машина Тьюринга.

Если для словарной функции f (применимой к словам, заданным на входном алфавите машины Тьюринга) существует машина Т, которая ее правильно вычисляет, f называется правильно вычислимой по Тьюрингу. С другой стороны, любой правильно вычисляющей машине Т можно поставить в соответствие вычисляемую ею функцию.

Основной теоремой теории алгоритмов является тезис Тьюринга: «Всякий алгоритм может быть реализован машиной Тьюринга». Доказать тезис нельзя, поскольку само понятие алгоритма является неточным. Подтверждением тезиса являются во-первых, математическая практика, а во-вторых, то, что описание алгоритма в терминах любой другой известной алгоритмической модели может быть сведено к его описанию в виде машины Тьюринга.

В силу тезиса Тьюринга эту задачу можно сформулировать как задачу о построении машины Тьюринга. Эта задача называется проблемой остановки, в связи с чем доказана теорема: «Не существует машины Тьюринга, решающей проблему остановки для произвольной машины Тьюринга».

Рассмотрим примеры применения машины Тьюринга к словам.

Пример. Найти результат применения машины Тьюринга, заданной следующими командами: к записям на ленте:

Решение:

Пример. Построить машину Тьюринга, правильно вычисляющую функцию

Решение:

В начальном состоянии на ленте будет записан входное слово вида: , где первые единиц представляют собой число , вторые единиц – число , 0 является разделителем между числами. Необходимо сконструировать машину Тьюринга (записать команды), в результате работы которой на ленте будет записано единиц.

Команды , передвигают положение управляющей головки (обозреваемой ячейки) на одну позицию вправо, команда заменяет ноль на единицу и также передвигает положение УГ вправо на 1 позицию. Применение таких команд из начального стандартного положения (обозревается крайняя левая ячейка, МТ находится в начальном состоянии ) позволяет переместить положение УГ на крайнюю правую единицу, причем разделяющий ноль будет заменен на 1, таким образом на ленте будет записано единицы, две лишние единицы надо заменить нулями, затем можно переместить положение УГ влево до крайней левой ячейки и остановиться.

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

Упражнения

1. Найти результат применения машины Тьюринга к слову на ленте Х=0111110:

2. Найти результат применения машины Тьюринга к слову на ленте Х=011010:

3. Построить машину Тьюринга, вычисляющую функцию .

4. Построить машину Тьюринга, реализующую функцию .

5. Реализовать машину Тьюринга, приписывающую к слову P=aabbbc справа символ b.

Индивидуальное задание

1. Дана машина Тьюринга с ленточным алфавитом А = ( , 1), алфавитом внутренних состояний Q и со следующей функциональной схемой (программой):

определите, в какое слово перерабатывает машина данное входное слово, исходя из состояний:

а) начального стандартного положения;

b) обозревается крайняя правая ячейка, начальное состояние .

1.1 1111111 1;

1.2 11111 11;

1.3 1 11 111;

1.4 1 11111 1;

1.5 1111111 1;

1.6 111 11 111;

1.7 11 111111;

1.8 111111 1 1;

1.9 1 1111 111;

1.10 11 11111 1;

1.11 111111 11;

1.12 11 11111 1;

1.13 11 1111 11;

1.14 1 1111 111;

1.15 1 1111111.

2 По словесному описанию машины Тьюринга построить ее программу на указанном ленточном алфавите.

2.1 Начав работу с первой единицы массива из единиц, машина сдвигает его на две ячейки вправо, не изменяя остального содержимого ленты, и останавливается на последней единице перенесенного массива, алфавит ( , 1).

2.2 Начав двигаться влево от произвольной ячейки, головка находит первую при таком перемещении ячейку с единицей (если такая встретится на пути) и, сделав один шаг вправо, останавливается на соседней ячейке. Содержимое ленты не меняется.

2.3 Машина начинает работу с самой левой непустой ячейки и отыскивает нуль, примыкающий с левой стороны к первому справа массиву из трех единиц, окаймленному нулями. Головка останавливается на первой единице найденного массива (если такой есть). Содержимое ленты не меняется.

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

2.5 При заданном n ≥ 1 головка машины, начав работу с произвольной ячейки и двигаясь вправо, записывает подряд 2n нулей и останавливается на последнем из них.

2.6 Головка машины, двигаясь вправо от какой-либо пустой ячейки, находит первый при таком перемещении массив, содержащий не менее семи единиц, стирает в нем первые семь единиц и останавливается на самой правой из ячеек, в которых были стерты единицы. Остальное содержимое ленты не меняется.

2.7 При заданном значении n головка машины из n записанных единиц оставляет на ленте n − 2 единицы, так же записанных подряд, если n ≥ 2, и работает вечно, если n = 0 или n = 1.

2.8 Начав работу с последней единицы массива из единиц, машина сдвигает его на две ячейки влево, не изменяя остального содержимого ленты, и останавливается на последней единице перенесенного массива.

2.9 На ленту подряд вписаны два конечных набора единиц, разделенные звездочкой. Составьте программу машины Тьюринга, которая выписывала бы подряд (без разделения звездочкой) столько единиц, сколько их в обоих наборах (сложение единиц).

2.10 Дана строка из букв а и b. Разработайте машину Тьюринга, которая переместит все буквы а в левую, а буквы b в правую часть строки. Каретка находится над крайним левым символом строки.

2.11 На ленте машины Тьюринга записано число в десятичной системе счисления. Каретка находится над крайней правой цифрой. Запишите цифры этого числа в обратном порядке.

2.12 На информационной ленте машины Тьюринга находится массив, состоящий только из символов А и B. Сожмите массив, удалив из него все элементы B.

2.13 Составьте программу машины Тьюринга, которая складывала бы числа: 1 + 2.

2.14 Составьте программу машины Тьюринга, которая вычитала бы числа: 2-1.

2.15 Составьте программу машины Тьюринга, которая складывала бы числа: 2 + 2.

Рекурсивные функции

Оператором примитивной рекурсии R называются подстановки, удовлетворяющие системе уравнений:

f(x1,..., xn)= g(x1,..., xn),

f(x1,..., xn, y+1)= h(x1,..., xn, y, f(x1,..., xn, y)),

которая называется схемой примитивной рекурсии.

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

Примерами примитивно-рекурсивных функций являются:

1. ;

2. ; 0 в противном случае;

Ограниченный оператор минимизации – применяется к предикатам:

Из предиката с помощью оператора минимизации получается функция . Ограничение z в операторе дает гарантию окончания вычислений, поскольку оно оценивает сверху число вычислений предиката .

Еще один ПР-оператор – оператор одновременной рекурсии . C его помощью строится рекурсивное описание сразу нескольких функций от (n-1)-ой переменной, причем значение каждой функции в точке y+1 зависит от значения всех функций в точке y:

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

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

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

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

Если на данном наборе уравнение не имеет решения, функция считается неопределенной, среди рекурсивных функций появляются не полностью определенные, т. е. частичные функции. Частично-рекурсивная функция называется общерекурсивной, если она всюду определена.

Пример. Найти функцию, получаемую из с помощью операций примитивной рекурсии.

Решение:

Запишем операторы примитивной рекурсии для функции двух переменных :

Из рекурсивных соотношений получим значения функции на каждом шаге (при ), где у – номер шага.

Итак, выражение для рекурсивной функции - .

Пример. Найти функции, получаемые из данной функции с помощью минимизации по каждой переменной.

Решение:

Минимизируем функцию по переменной , решим уравнение:

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

0 при ,

не определен в остальных случаях.

Минимизируем функцию по переменной , решим уравнение:

0 при ,

не определен в остальных случаях.

Минимизируем функцию по переменной , решим уравнение:

при ,

не определен в остальных случаях.

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

Итак, всякий алгоритм, описанный в терминах частично-рекурсивных функций можно реализовать машиной Тьюринга и наоборот.

Множество всех алгоритмов счетно, что означает наличие взаимно-однозначного соответствия между алгоритмами и числами натурального ряда, т.е. функции типа:

: Al N.

Такая функция называется нумерацией алгоритмов, а ее значение (А) – номером алгоритма А при нумерации . Из взаимной однозначности отображения следует, что существует обратная функция -1(n)=Аn, восстанавливающая по номеру n описание алгоритма Аn. Существование нумераций позволяет работать с алгоритмами как с числами.

Все примитивно-рекурсивные функции могут быть реализованы на машине тьюринга

Пример. Реализуем функцию константу 0:

⇐ Предыдущая 1 2 3 4 567 Следующая ⇒