Является ли исчисление SK2 полным базисом, где K2 - перевернутый K комбинатор?

10

В частности, если я определил новый K2 как

K2=λx.(λy.y)
вместо
K=λx.(λy.x)
будет ли {S,K2,I} -счет вычисляться на основе конкуренции?

Я предполагаю «нет» только потому, что я не могу построить обычный K-комбинатор из S , I и K2 комбинаторов, но у меня нет алгоритма для подражания и нет хорошего интуиция о создании вещей из этих комбинаторов.

Кажется, что вы можете определить

K2=KI
с помощью регулярного {S,K,(I)} -калькулята, но я не мог по-настоящему работать в обратном направлении, чтобы получить вывод K в терминах K2 и остальных ,

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

Я задал этот вопрос на StackOverflow, но мне было рекомендовано опубликовать его здесь. Я получил несколько комментариев на этот пост, но я не уверен, что понял их правильно.

Бонус: если это не полная основа, является ли итоговый язык, тем не менее, полным по Тьюрингу?

капуста
источник
это хорошая головоломка Кажется, что S и K 'позволяют вам только генерировать члены, чьи нормальные формы головы имеют до трех ведущих λs (т.е. термины, которые нормализуются к форме λx₁.λx₂.λx₃. Xᵢ t₁ ... tₙ), так что это может быть еще один путь к доказательству незавершенности, хотя оформить его немного сложно. Вы определенно никогда не достигаете «тупика», хотя: начните с определения I = λx.x = K2 K2, затем, повторяя преобразование t ↦ S t K2, вы можете выразить λx.x I ... I для любой строки из Is ,
Ноам
... И извините, под "неполнотой" я подразумеваю неполноту SK 'как комбинаторную основу для нетипизированного лямбда-исчисления. У меня также нет хорошей интуиции для того, является ли она тьюрингово-полной (что подразумевается комбинаторной полнотой, но не наоборот).
Ноам
Перекрестная публикация : stackoverflow.com/q/55148283/781723 , cs.stackexchange.com/q/108741/755 . Пожалуйста , не размещайте один и тот же вопрос на нескольких сайтах . Каждое сообщество должно иметь честный ответ, не теряя никого времени.
DW
Моя ошибка @DW, я могу что-нибудь сделать, чтобы исправить это?
Коул

Ответы:

14

S,K2,IS,K2

S(SS)K2

        @
       / \
      /   \
     @    K2
    / \
   /   \
  S     @
       / \
      /   \
     S     S

T@K2

S,K2,I

         @                           @
        / \                         / \
       /   \                       /   \
      @     g    [reduces to]     @     @
     / \                         / \   / \
    /   \                       e   g f   g
   @     f                 
  / \
 /   \
S     e
      @
     / \
    /   \
   @     f    [reduces to]   f
  / \
 /   \
K2    e

TTTTTS,K2,ITK2SK2KK2SK2KS,K2,I

ZAK
источник
Очень хороший аргумент!
Ноам
Очень приятный и понятный аргумент. Спасибо. Возможно, я открою отдельный вопрос, чтобы спросить о полноте Тьюринга.
Коул
5

S,K2,I


A,B,C

  • K:ABA
  • K2:ABB
  • S:(ABC)(AB)(AC)
  • I:AA

KI,S,K2ABB,(ABC)(AB)(AC),AAAABBABA

t,f,uABB(ABC)(AB)(AC)AAt

A B | A -> B
t t | t
t f | f
f t | t
f f | t
t u | f
f u | t
u t | t
u f | f
u u | t

K2,S,IttABAfuAtBS,K2,I

ZAK
источник
1
Мне нравится этот подход, но не могли бы вы уточнить, какие правила вы используете в качестве последовательного исчисления?
Ноам
Можете ли вы набросать, как доказать S в этом ограниченном исчислении секвенций? Кажется, это невозможно с правилами, которые, как я догадался, вы могли иметь в виду.
Робин Хьюстон
1
@ robin-houston: посмотрите мои изменения (я также добавил другой семантический аргумент с тем же выводом).
ЗАК
2
Я согласен с Чарльзом Стюартом (здесь: twitter.com/txtpf/status/1123962607306706944 ), что не ясно, как перейти от необитаемости в простом типе лямбда-исчисления к невыразимости с помощью комбинаторов. Может существовать аргумент, специфичный для K, но начальный шаг «... тогда можно было бы сделать то же самое в простом типе λ-исчисления» в целом не выполняется (Чарльз упомянул контрпример Y комбинатора) , Вы видите строгий аргумент?
Ноам
1
K