Такая функция E, что:

∀F (F E = F)

Очевидно, что левой единицей E' (E' F = F) будет функция (λx.x). Но существует ли правая единица?

Или существует ли доказательство, что такого элемента не существует?

Если не существует единого правого элемента, то может ли существовать для каждой правильной функции F свой особый элемент E с такими же свойствами? Существуют ли методы его построения?

В общем случае, существует ли для каждой правильной фукнции лямбда-исчисления такая цепочка элементов, что:

∀F (F E1 E2 … En = F) (при n >=1)

Единая цепочка E1 E2 … En для всех правильных функций или особая для каждой, существуют ли методы построения таких цепочек по заданной функции?

Для некоторых функции такую цепочку легко посторить.

Например, для функции (λx.x) это будет сама функция (λx.x), действительно:

(λx.x) (λx.x) α=> 
(λx.x) (λy.y) β=> 
λy.y α=> 
λx.x

Для фукнций вида (λa.λb.a b), (λa.λb.b a), (λa.λb.λc.b c a) т.д., в который связанные переменные попадаются по одному разу, легко подобрать цепочку из функций вида (λx.x) и самой первоначальной функции в качестве последнего операнда по схеме:

пусть F := (λa.λb.a b), тогда E1 := (λс.c) и E2 := F, выведем:
(λa.λb.a b) (λс.c) (λa.λb.a b) β=> 
(λb.(λс.c) b) (λa.λb.a b) β=> 
(λb.b) (λa.λb.a b) α=> 
(λb.b) (λa.λc.a c) β=> 
λa.λc.a c) α=> 
(λa.λb.a b)

Но что можно сказать о цепочке E1 E2 … En для, например (λa.λb.a b a a)? Существует ли общее решение для нахождения такой цепочки или для доказательтства, что такой цепочки для заданного элемента не существует?


PS Сейчас пришло в голову, что точно точно не для всех функций имеется правая единица. А именно для константной функции λx.p и цепочек E1 E2 … En

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

задан 16 Дек '18 15:35

изменен 18 Дек '18 0:18

10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

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

Присоединяйтесь!

отмечен:

×34
×26

задан
16 Дек '18 15:35

показан
70 раз

обновлен
18 Дек '18 0:18

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru