Машина Тьюринга. Теория алгоритмов, формальных языков, грамматик и автоматов

Содержание

Слайд 2

Теория алгоритмов Восходит к Давиду Гильберту На рубеже 20 века сформулировал

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

Восходит к Давиду Гильберту
На рубеже 20 века сформулировал мировую проблему:
Можно

ли построить алгоритм, создающий необходимый алгоритм к любой, точно поставленной задаче?
Такая постановка задачи неразрешима, т.к. фактически проблема сводится к логическому парадоксу брадобрея: Он бреет тех, кто не бреется сам. Если брадобрей бреется сам, то он принадлежит множеству тех жителей города, кто бреется сам, Но в объявлении утверждается, что наш брадобрей никогда не бреет тех, кто входит в это множество. Следовательно, наш брадобрей не может брить самого себя (Бертран Рассел)
Слайд 3

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

Типы алгоритмов. История создания

Интенсивный поиск универсального уточнения алгоритма предложил примерно 20

формальных конструкций алгоритмов, которые условно можно разбить на три типа
Алгоритмические машины (АМ).
Функции, вычислимые алгоритмом.
Исчисления.
Слайд 4

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

Алгоритмические машины (АМ)

имеют единственный процессор, выполняющий небольшой набор очень примитивных действий,


простую структуру данных (структуру памяти) в виде бесконечной ленты,
простую логику (правила) управления процессором.
Слайд 5

Основные АМ Машина Тьюринга (МТ) предложена Тьюрингом в 1937 г. Машина

Основные АМ

Машина Тьюринга (МТ) предложена Тьюрингом в 1937 г.
Машина Поста (МР)

предложена Постом в 1937 г.
Нормальный алгоритм Маркова (НАМ) предложен Марковым в 1953 г.
Слайд 6

Машина Тьюринга -абстрактный исполнитель (абстрактная вычислительная машина). Была предложена Аланом Тьюрингом

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

-абстрактный исполнитель (абстрактная вычислительная машина). Была предложена Аланом Тьюрингом

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

Автор ТЬЮРИНГ Алан Матисон (Turing Alan Mathison) (1912—1954), английский математик. Основные

Автор

ТЬЮРИНГ Алан Матисон (Turing Alan Mathison) (1912—1954), английский математик. Основные труды по

математической логике, вычислительной математике.
В 1936-37 годах ввел математическое понятие абстрактного эквивалента алгоритма, или вычислимой функции, получившее затем название «машины Тьюринга».
В возрасте 24 лет Тьюринг написал работу "О вычислимых числах", которой суждено было сыграть исключительно важную роль в развитии вычислительной математики и информатики
Слайд 8

Соглашение об алгоритме

Соглашение об алгоритме

Слайд 9

Слайд 10

Структура алгоритма (составляющие алгоритма) Процессорная структура. (Исполнитель алгоритма). Во всех теоретических

Структура алгоритма (составляющие алгоритма)

Процессорная структура. (Исполнитель алгоритма).
Во всех

теоретических конструкциях алгоритмов и большинстве алгоритмических языках это единственный процессор.
Структуры данных. Структура данных это способ организация записи, хранения и извлечение данных.
Данные – это элементы множеств, которые нужно порождать или распознавать..
Слайд 11

Составляющие структуры Информационная структура алгоритма (ИСА). Структура функций есть описание конструирования

Составляющие структуры

Информационная структура алгоритма (ИСА). Структура функций есть описание конструирования функции

от функций из базовых.
Логическая структура алгоритма (ЛСА) или программы (ЛСП). ЛСА суть описание организации вычислительного процесса, который управляется состоянием памяти.
Слайд 12

Интерпретация МТ. Процессор – в МТ называется управляющей головкой (УГ). Структура

Интерпретация МТ.

Процессор – в МТ называется управляющей головкой (УГ).
Структура

данных (память процессора) бесконечная лента, разбитая на ячейки, в ячейку может быть записан только один символ
Процесс вычислений происходит по тактам
Процесс остановки (остановка) МТ.
Замечание Список правил для МТ не упорядочен
Слайд 13

МТ Тьюринг назвал свое абстрактное механическое устройство "универсальной машиной", поскольку она

МТ

Тьюринг назвал свое абстрактное механическое устройство "универсальной машиной", поскольку она должна

была справляться с любой допустимой, то есть теоретически разрешимой задачей — математической или логической.
Данные должны были вводиться в машину на бумажной ленте, поделенной на клетки — ячейки.
Каждая такая ячейка либо содержала символ, либо была пустой.
Машина могла не только обрабатывать записанные на ленте символы, но и изменять их, стирая старые и записывая новые в соответствии с инструкциями, хранимыми в ее внутренней памяти.
Слайд 14

УУ таблица Машина Тьюринга Представляет собой бесконечную ленту, разделенную на ячейки.

УУ

таблица

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

Представляет собой бесконечную ленту, разделенную на ячейки.
Имеет управляющее устройство,

которое перемещается в двух направлениях.
В управляющем устройстве содержится таблица, которая описывает порядок действий.
Слайд 15

Абстрактная модель машины Тьюринга МТ =

Абстрактная модель машины Тьюринга

МТ =


Слайд 16

МТ =

МТ =

Слайд 17

Слайд 18

Слайд 19

Машина Тьюринга состоит из трех частей: ленты, считывающе-записывающей головки и логического

Машина Тьюринга состоит из трех частей: ленты, считывающе-записывающей головки и логического

устройства

Лента выступает в качестве внешней памяти; она считается неограниченной (бесконечной)

Слайд 20

Головка неподвижна, а лента передвигается относительно нее вправо или влево. Машина

Головка неподвижна, а лента передвигается относительно нее вправо или влево.
Машина

работает в некотором произвольном конечном алфавите
A = {ε a1…a n} – этот алфавит называется внешним.
В нем выделяется специальный символ – ε, называемый пустым – его посылка в какую-либо ячейку стирает тот символ, который до этого там находился, и оставляет ячейку пустой.
Слайд 21

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

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

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

Система исполняемых головкой команд предельно проста: на каждом такте она производит

Система исполняемых головкой команд предельно проста:
на каждом такте она

производит замену символа в обозреваемой ячейке ai символом aj
При этом возможны сочетания:
j = i – это означает, что в обозреваемой ячейке символ не изменился;
i_0, j = 0 означает, что хранившийся в ячейке символ заменяется пустым, т.е. стирается;
i =0, j_ 0 означает, что пустой символ заменяется непустым (с номером j в алфавите), т.е. производится вставка символа;
i j_ 0 соответствует замене одного символа другим.
Слайд 23

Команды перемещений ленты L («Left») на ячейку влево, R («Right») на

Команды перемещений ленты

L («Left») на ячейку влево,
R («Right») на ячейку

вправо
S («Stop») остаться на месте, т.е. адрес обозреваемой ячейки в результате выполнения команды может либо измениться на 1, либо остаться неизменным.
Слайд 24

Элементарный шаг (такт) работы машины Тьюринга головка считывает символ из обозреваемой

Элементарный шаг (такт) работы машины Тьюринга

головка считывает символ из обозреваемой ячейки

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

Определение Конфигурация машины- совокупность состояний всех ячеек ленты, состояния УУ и

Определение Конфигурация машины- совокупность состояний всех ячеек ленты, состояния УУ и

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

Пример Пусть начальной является конфигурация 1q11111. Такт 1 Обозревается 1, в

Пример

Пусть начальной является конфигурация 1q11111.
Такт 1 Обозревается 1, в ЛУ

состояние q. Выходная команда q1R, что эквивалентно перемещению головки по отношению ленты на 1 шаг вправо. Следовательно, образуется промежуточная конфигурация 11q111.
Такт 2 – аналогичным образом осуществляется переход к конфигурации 111q11.
Такт 3 – переход к конфигурации 1111q1.
Такт 4 –переход к конфигурации 11111q
Такт 5 Обозревается , в ЛУ состояние q. Выходная команда z1S – вместо в ячейку записывается 1, сдвига нет, работа прекращается. Конечная конфигурация 111111z.
Задача решена.
Слайд 27

Отличия читающего автомата с выходом и МТ

Отличия читающего автомата с выходом и МТ

Слайд 28

Тезис Тьюринга Всякий алгоритм может быть задан посредством тьюринговой функциональной схемы

Тезис Тьюринга

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

и реализован в соответствующей машине Тьюринга.
Машина Тьюринга - это модель компьютера
Слайд 29

Отличия ЭВМ и машины Тьюринга Главное отличие машины Тьюринга от ЭВМ

Отличия ЭВМ и машины Тьюринга

Главное отличие машины Тьюринга от ЭВМ –

бесконечная лента
В отличие от машины Тьюринга память реальных машин всегда конечна и ее ограничения удается преодолеть путем организации циклов if – если и for – делай до тех пор пока
Слайд 30

Языки высокого уровня Вычислительная модель Вентили (булева алгебра) Микрокоманды Предметная область

Языки
высокого уровня

Вычислительная модель

Вентили
(булева алгебра)

Микрокоманды

Предметная область

Ассемблер

Аналитическая модель

Физико-технический процесс

Этапы решения задачи

Слайд 31

Представление машины Тьюринга совокупностью команд Совокупность всех команд, которые может выполнять

Представление машины Тьюринга совокупностью команд

Совокупность всех команд, которые может выполнять

машина, называется ее программой. Машина Тьюринга считается заданной, если заданы ее внешний и внутренний алфавиты, программа, начальная конфигурация и указано, какие из символов обозначают пустую ячейку и заключительное состояние.
Чтобы записать совокупность команд, нужно воспользоваться следующими правилами:
1) начальному шагу алгоритма ставится в соответствие q 0 - начальное состояние;
2) циклы реализуются так, что последнее действие цикла должно соответствовать переходу в то состояние, которое соответствует началу цикла;
3) соседним шагам алгоритма соответствует переход в смежные состояния, которые соответствуют этим пунктам;
4) последний шаг алгоритма вызывает переход в заключительное состояние.
Слайд 32

В качестве примера рассмотрим совокупность команд машины Тьюринга, которая инвертирует входную

В качестве примера рассмотрим совокупность команд машины Тьюринга, которая инвертирует входную

цепочку, записанную с использованием нулей и единиц. Пусть алфавит машины Тьюринга задан множеством A={0, 1, ε}, где символ ε соответствует пустой ячейке, а число состояний устройства управления задано в виде множества Q = {q0, q1, qz}. Если, например, начальная конфигурация имеет вид q0110011, то конечная конфигурация после завершения операции инвертирования должна иметь вид qz001100. Для решения задачи машиной будет порождена следующая совокупность команд: q01 → q00R, q10 → q10L, q00 → q01R, q11 → q11L, q0 ε → q1εL, q1ε → qzεR.
Слайд 33

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

Представление машины Тьюринга графом

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

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

Начальная и конечная вершины графа обычно выделяются; на рисунке они отмечены черным кружком. Если на очередном такте работы машины Тьюринга символ на ленте не изменяется, то в правой части команды его можно не писать (ε на ребре в состояние qz ).

Слайд 34

Представление машины Тьюринга таблицей соответствия

Представление машины Тьюринга таблицей соответствия

Слайд 35

Слайд 36

Пример 1. Построить машину Тьюринга, которая правильно вычисляет функцию f(x) =x+1

Пример 1.

Построить машину Тьюринга, которая правильно вычисляет функцию f(x) =x+1 по

правилам двоичного сложения.
Решение. Исходя из формулировки задачи, требующей вычислить функцию по правилам сложения в двоичной системе сложения, выберем входной алфавит: А ={0, 1, ε}.
Представим машины Тьюринга таблицей соответствия и графом. Таблица соответствия:
Слайд 37

Запишем программу построенной машины Тьюринга для случая, когда входная цепочка на

Запишем программу построенной машины Тьюринга для случая, когда входная цепочка на

ленте равна двоичному числу 111. Слева от каждой команды приведем представление входной цепочки на ленте до выполнения данной команды. Символ, который находится под головкой, будем помечать подчеркиванием.
1) q01 → q01R ε111ε 6) q11 → q10L ε110ε

2) q01 → q01R ε111ε 7) q11 → q10L ε100ε
3) q01 → q01R ε111ε 8) q1ε → q21L ε000ε
4) q0ε → q1εL ε111ε 9) q2 ε → qz εR ε1000ε
5) q11 → q10L ε111ε

Слайд 38

Слайд 39

Построение МТ Для того чтобы доказать вычислимость функции, а в дальнейшем

Построение МТ

Для того чтобы доказать вычислимость функции, а в дальнейшем и

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

Операции над машинами Тьюринга 1. Композиция машин Тьюринга. Пусть машины Т1

Операции над машинами Тьюринга

1. Композиция машин Тьюринга. Пусть машины Т1 и

Т2 имеют программы Р1 и Р2.
Предположим, что внутренние алфавиты этих машин не пересекаются; пусть qz1 - заключительное состояние машины Т1, а q02 - начальное состояние машины Т2. Заменим всюду в программе Р1 заключительное состояние qz1 на начальное состояние q02 машины Т2 и полученную программу объединим с программой Р2. Новая программа Р определяет машину Т, называемую композицией машин Т1 и Т2 по паре состояний (qz1, q02).
Композиция машин может быть обозначена Т1 ⋅Т2 или Т1Т2. Более подробно композиция машин записывается следующим образом:
Т = Т(Т1, Т2, (qz1, q02)), где
T1 = (Q1, A1, δ1, p01, pz1, a01, a11),
Т2= (Q2, A2, δ2, p02, pz2, a02, a12).
Слайд 41

Пусть a01 = a02 = a0 и a11 = a12 =

Пусть a01 = a02 = a0 и a11 = a12 =

a1. Внешний алфавит композиции Т1Т2 является объединением внешних алфавитов машин Т1 и Т2:

Операция композиции, выполняемая над алгоритмами, позволяет получать новые, более сложные алгоритмы из ранее известных простых алгоритмов.
2. Итерация машины Тьюринга. Эта операция применима только к одной машине.
Пусть qz - заключительное состояние машины Т, а qn - какое-либо состояние машины Т, не являющееся заключительным. Заменим всюду в программе Р машины Т состояние qz на qn . Полученная программа определяет новую машину Т′(qz, qn), которая называется итерацией машины Т по паре состояний (qz, qn). Если машина Тьюринга имеет одно заключительное состояние, то после выполнения итерации получается машина, не имеющая
заключительного состояния.

Операции над МТ

Слайд 42

Операции над МТ

Операции над МТ

Слайд 43

Алгоритмическая машина Поста (МП) — абстрактная вычислительная машина, предложенная Эмилем Леоном

Алгоритмическая машина Поста

(МП) — абстрактная вычислительная машина, предложенная Эмилем Леоном Постом

(Emil L. Post), которая отличается от машины Тьюринга большей простотой. Обе машины «эквивалентны» и были созданы для уточнения понятия «алгоритм»
Абстрактная машина Поста состоит
из бесконечной ленты, разделенной на равные секции,
считывающе-записывающей головки.
Каждая секция может быть либо пуста (т.е. в нее ничего не записано), либо заполнена (отмечена – т.е. в нее записана метка).
Состояние ленты и информация о положении головки характеризуют состояние машины Поста.
Слайд 44

За один такт (его называют шагом) головка может сдвинуться на одну

За один такт (его называют шагом) головка может сдвинуться на одну

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

Структура команды Каждая команда имеет следующую структуру xKy, x – номер

Структура команды

Каждая команда имеет следующую структуру
xKy,
x – номер исполняемой

команды;
K – указание о выполняемом действии;
y – номер следующей команды (наследника).
Слайд 46

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

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

Слайд 47

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

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

Слайд 48

Пример

Пример

Слайд 49

Комментарий к примеру Последовательное исполнение команд 1 и 2 приводит к

Комментарий к примеру
Последовательное исполнение команд 1 и 2 приводит к тому,

что головка за два такта работы машины сдвигается на одну позицию вправо.
Это передвижение продолжается до тех пор, пока после очередного сдвига под головкой не окажется пустая ячейка – тогда по команде 3 в нее будет поставлена метка
и по команде 4 машина остановится
Слайд 50

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

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

до получения запланированного результата.
В отличие от этой ситуации, остановка по команде
является результативной, т.е. она происходит после того, как результат действия алгоритма получен.
Кроме того, возможна ситуация, когда машина не останавливается никогда – это происходит, если ни одна из команд не содержит в качестве последователя номера команды остановки или программа не переходит к этой команде.
Слайд 51

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

Функции, вычислимые алгоритмом

алгоритм не определяется формально, а существует как бы

в виде «всем понятной механической процедуры».
Любая функция, вычислимая на интуитивном (содержательном) уровне, должна быть сконструирована из базовых
Слайд 52

Вычислимые функции Говорят, что машина Тьюринга вычисляет функцию f(x1, x2, ...,

Вычислимые функции

Говорят, что машина Тьюринга вычисляет функцию f(x1, x2, ..., xn),

если выполняются следующие условия:

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

Слайд 53

Слайд 54

Слайд 55

Слайд 56

Рекурсивные функции Рекурсивные функции на множестве натуральных чисел были предложены Клини

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

Рекурсивные функции на множестве натуральных чисел были предложены Клини в

1938 г.
Конструктивные механизмы рекурсивных функций очень просты, их применение в процессе построения «функции от функции» позволяет явно выстраивать структуру функции в отличие от АМ, где функция определяется процедурно, через последовательность действий.
Слайд 57

Рекурсия Пример: определение факториала. n!=1*2*3*...*n. Н.Вирт отмечает, что "...мощность рекурсии связана

Рекурсия

Пример: определение факториала.
n!=1*2*3*...*n.
Н.Вирт отмечает, что "...мощность рекурсии связана с тем,

что она позволяет определить бесконечное множество объектов с помощью конечного высказывания".
Слайд 58

Рекурсивные функции Рекурси́вная фу́нкция (от лат. recursio — возвращение) — это

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

Рекурси́вная фу́нкция (от лат. recursio — возвращение) — это числовая функция   числового аргумента, которая в

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

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

Свойства рекурсивных алгоритмов:

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

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

Примитивная рекурсия Оператор примитивной рекурсии Rn позволяет определить (n+1) - местную

Примитивная рекурсия

Оператор примитивной рекурсии Rn позволяет определить (n+1) - местную функцию

f по двум заданным функциям, одна из которых является n- местной функцией g, а другая (n+2) - местной функцией h.
Функция f(x1, x2, ..., xn, y) получается оператором примитивной рекурсии из функции g(x1, x2, ..., xn) и функции h(x1, x2, ..., xn, y, z), по схеме:
f(x1, x2, ..., xn, 0) = g(x1, x2, ..., xn);
f(x1, x2, ..., xn, y+1) = h(x1, x2, ..., xn, y, f(x1, x2, ..., xn, y)).
Независимо от числа переменных в f рекурсия ведется только по одной переменной у. Остальные n переменных x1, x2, ..., xn на момент применения схемы зафиксированы и играют роль параметров.
Слайд 61

Слайд 62

Тезис Чёрча — Тьюринга и алгоритмически неразрешимые проблемы Алан Тьюринг высказал

Тезис Чёрча — Тьюринга и алгоритмически неразрешимые проблемы

Алан Тьюринг высказал предположение (известное

как Тезис Чёрча — Тьюринга), что любой алгоритм в интуитивном смысле этого слова может быть представлен эквивалентной машиной Тьюринга. Уточнение представления о вычислимости на основе понятия машины Тьюринга (и других эквивалентных ей понятий) открыло возможности для строгого доказательства алгоритмической неразрешимости различных массовых проблем (то есть проблем о нахождении единого метода решения некоторого класса задач, условия которых могут варьироваться в известных пределах). Простейшим примером алгоритмически неразрешимой массовой проблемы является так называемая проблема применимости алгоритма (называемая также проблемой остановки). Она состоит в следующем: требуется найти общий метод, который позволял бы для произвольной машины Тьюринга (заданной посредством своей программы) и произвольного начального состояния ленты этой машины определить, завершится ли работа машины за конечное число шагов, или же будет продолжаться неограниченно долго.
Слайд 63

Исчисления. Исчисление функций, вычисляемых на множестве натуральных чисел предложено Эрбраном и

Исчисления.

Исчисление функций, вычисляемых на множестве натуральных чисел предложено Эрбраном и

Гёделем в 1938 г.
λ-исчисление А.Чёрча также может быть отнесено к этому типу алгоритмов, предложено в 1937 г.
Формальные грамматики, порождающие языки, предложены Хомским в 1953 – 1956 г.
Слайд 64

Лямбда-исчисление Ля́мбда-исчисле́ние (λ-исчисление) — формальная система, разработанная американским математиком Алонзо Чёрчем,

Лямбда-исчисление

Ля́мбда-исчисле́ние (λ-исчисление) — формальная система, разработанная американским математиком Алонзо Чёрчем, для

формализации и анализа понятия вычислимости.
λ-исчисление может рассматриваться как семейство прототипных языков программирования. Их основная особенность состоит в том, что они являются языками высших порядков. Тем самым обеспечивается систематический подход к исследованию операторов, аргументами которых могут быть другие операторы, а значением также может быть оператор. Языки в этом семействе являются функциональными, поскольку они основаны на представлении о функции или операторе, включая функциональную аппликацию и функциональную абстракцию.
λ-исчисление реализовано Джоном Маккарти (1960) в языке Лисп. Он ориентирован на разработку программ для решения задач в области искусственного интеллекта и счита-ется вторым после Fortran  старейшим высокоуровневым языком программирования. 
Слайд 65

Метапрограммирование Метапрограммирование предусматривает написание программ, которые работают с другими программами в

Метапрограммирование

Метапрограммирование предусматривает написание программ, которые работают с другими программами в качестве

данных. Язык обрабатывающей программы называется метаязыком, язык обрабатываемой — объектным языком. Простейшим примером метапрограмми-рования является любой компилятор, преобразующий код, написанный на языке высокого уровня, в низкоуровневый машинный язык или ассемблер.
Слайд 66

Ассоциативное исчисление

Ассоциативное исчисление

Слайд 67

Слайд 68

- Предыдущая
Материальная и духовная культура
Следующая -
Кадровый Советник - аутсорсинг

Похожие презентации

Определители и их применения
Текстовые задачи и пути их решения. Элективный курс. 9 класс
Математика в профессии сварщика
Комплексные числа
Построение треугольников по заданным элемента
Расчет площадей помещений. (Лекция 9.7)
Векторная алгебра
Презентация по математике "Урок математики. 2 класс." - скачать бесплатно
Устный счет
Тема: Порядок выполнения действий в выражениях без скобок. Цель: совершенствование знаний выполнения действий в выражениях без
Вычитание чисел 5,6,7,8,9. Уменьшаемое, вычитаемое, разность
Аппроксимация функций (тема 8)
Мода и медиана
Справочник по геометрии
Презентация по математике "Графическое решение квадратных уравнений" - скачать
Связь между координатами вектора и координатами его начала и конца
Примеры на действия с алгебраическими дробями
Целое уравнение и его корни. 9 класс
Это мы не проходили… интеллектуально-познавательная игра
Аттестационная работа. Рациональные способы устных вычислений
Простейшие вероятностные задачи. Элементарные и сложные события. Вероятность противоположного события. (11 класс)
Презентация по математике "тренажер" - скачать бесплатно
Геометрия. Основные утверждения и теоремы
Математика. Закрепление
Организация познавательной деятельности учащихся в условиях интеграции математики с физикой
Презентация по математике "ЧИСЛО И ЦИФРА 5" - скачать бесплатно
Прибавление и вычитание числа 2 (Анимированная сорбонка)
Презентация по математике "Окружность и круг" - скачать бесплатно
Вы можете прислать нам Вашу презентацию и мы опубликуем ее на сайте.
Обратная связь
Для правообладателей
Email: Нажмите что бы посмотреть