Математическая логика и теория алгоритмов

этой модели положено так называемое «ламбда-исчисление». Приме­ ром языка, основанного на ламбда-исчислении, является язык ЛИСП; объектно-ориентированные в числительные модели. В импера­ тивных (процедурных) и функциональных вычислительных моделях операция принимается за субъект, а вычисления представляются в ви­ де использования операций с некоторыми объектами. Однако если сделать наоборот, т.е. объект операции принять за субъект, а приме­ нение операций рассматривать как передачу запроса объекту, который и выполняет эту операцию, то такая модель является объектно- ориентированной, т.е. объекты рассматриваются как процессы. Реали­ зованы в языках PLASMA, MESA, LOOPS и др. Теперь перейдем к некоторым понятиям ламбда-исчисления. Ламбда-исчисление было введено Чёрчем как один из подходов для обоснования логики и математики. В дальнейшем часть этого ис­ числения явилась одной из теорий вычислений. Ламбда-исчисление - это теория, рассматривающая функции как п р а в и л а , а не как графики и фактически выделяющая вычисли­ тельный аспект при введении функций. Чёрч предложил использовать ламбда-исчисление для формали­ зации понятия эффективной вычислимости. Тьюринг показал, что вы­ числимость по Тьюрингу эквивалентна ламбда-вычислимости. Таким образом, несмотря на свой очень простой синтаксис, ламбда-исчи- сление способно реализовать все механически вычислимые функции. Выражение в ламбда-исчислении представлено в префиксной форме, т.е. вначале располагается оператор, например, вместо а+Ь пишется +а6, а вместо alb+bxc пишется (+(/а6)(х6с)). Все программы представляются в виде выражений, а процесс выполнения программы заключается в определении значения этого выражения и это называется оценкой выражения. Оценка выражения производится повторением операции выбора и упрощением тех частей этого выражения, которые можно 260