Наименьший возможный универсальный комбинатор

17

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

  • размер 23: λf.f (fS (KKKI)) K
  • размер 18: λf.f (fS (KK)) K
  • размер 14: λf.fKSK
  • размер 12: λf.fS (λxyz.x)
  • размер 11: λf.fSK

где S = λxyz.xz (yz) размера 6 и K = λxy.x размера 2 - комбинаторы исчисления комбинаторов SK . Первые 4 примера описаны в этой статье .

Мои вопросы:

  • Существуют ли универсальные комбинаторы меньшего размера?
  • Какой минимально возможный универсальный комбинатор?

РЕДАКТИРОВАТЬ: См. Также /math//a/180263/76284 , который имеет λazbc.bc(a(λy.c))(который будет иметь размер 8 , соответствующий сумме размеров базы SK). Кто-нибудь знает, как выразить S и K из этого комбинатора?

lo.logic computability lambda-calculus universal-computation combinatory-logic user76284
источник
Может быть, это представляет интерес: wolframscience.com/nksonline/page-1123a-text?firstview=1
Андрей Бауэр
Какое у вас определение размера? Вы можете написать это как функцию?
Джошуа Герман
Поскольку 6 + 2 = 8 <11, это заставляет меня задаться вопросом, является ли {S, K} наименьшей базой комбинаторов, измеряемых по общему размеру?
Ноам
Ваше недавнее редактирование скорее звучит как (частичный) ответ.
Эмиль Йержабек поддерживает Монику
Насколько строго вы определяете « комбинатор »? Должен ли он иметь форму, в λx*.Eкоторой нет Eабстракций?
Питер Тейлор

Ответы:

9

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

Есть несколько простых открытых вопросов аналогичного характера, например, проблемы № 4, № 6 и № 10 из списка открытых проблем TLCA .

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

Изменить: комментарии и ссылки Ноама выдвинуть нижнюю границу 5! Я не удивлюсь, если доказательство также потребует появления дополнительной переменной, которая подтолкнет нас к 6.

Коди
источник
3
На самом деле двух переменных недостаточно ( dl.acm.org/citation.cfm?id=2100917 , cstheory.stackexchange.com/a/36344/674 ), поэтому это дает немного более высокую нижнюю границу (размер 5 = 3 абстракции и 2 приложения).
Ноам
@NoamZeilberger хорошо, это фантастический результат, о котором я не знал!
Коди
7

По вашему первому вопросу, я думаю, эта статья может помочь куче. У него есть 6-битное исчисление комбинатора, которое также является UTM. Кроме того, он имеет универсальный комбинатор, который, кажется, имеет размер 7 с одним элементом, учитывая, что вы хотите. Они называют это Zot. http://arxiv.org/pdf/cs/0508056v1.pdf

Я не уверен, что вы можете сказать или доказать, что существует минимальный комбинатор. В документе предполагается, что оно должно быть не менее 6 бит.

Джошуа Герман
источник
2
Комбинатор Zot на самом деле является последним из перечисленных в OP: λx.xSK (совместно с его родными языками, Iota и Jot), длина которого равна 11. В «6-битном исчислении комбинатора» (Keraia) «6 бит» размер UTM; и похоже, что это просто кодировка лямбда-исчисления, а не исчисление комбинатора (и, следовательно, не имеет встроенного универсального комбинатора).
2012rcampion