Menor combinador universal possível

17

Estou procurando o menor combinador universal possível , medido pelo número de abstrações e aplicativos necessários para especificar esse combinador no cálculo lambda . Exemplos de combinadores universais incluem:

  • tamanho 23: λf.f (fS (KKKI)) K
  • tamanho 18: λf.f (fS (KK)) K
  • tamanho 14: λf.fKSK
  • tamanho 12: λf.fS (λxyz.x)
  • tamanho 11: λf.fSK

onde S = λxyz.xz (yz) do tamanho 6 e K = λxy.x do tamanho 2 são os combinadores do cálculo do combinador SK . Os 4 primeiros exemplos são descritos neste documento .

Minhas perguntas são:

  • Existem combinadores universais menores em tamanho?
  • Qual é o menor combinador universal possível?

EDIT: Consulte também /math//a/180263/76284 , que possui λazbc.bc(a(λy.c))(que seria do tamanho 8 , correspondendo à soma dos tamanhos da base SK). Alguém sabe como expressar S e K deste combinador?

lo.logic computability lambda-calculus universal-computation combinatory-logic user76284
fonte
Talvez isso seja de interesse: wolframscience.com/nksonline/page-1123a-text?firstview=1
Andrej Bauer
Qual é a sua definição de tamanho? Você pode escrevê-lo como uma função?
Joshua Herman
Como 6 + 2 = 8 <11, isso me faz pensar se {S, K} é a menor base de combinadores medida pelo tamanho total?
Noam Zeilberger
Sua edição recente parece uma resposta (parcial).
Emil Jeřábek apoia Monica
Quão estritamente você está definindo " combinador "? Tem que ser da forma em λx*.Eque Eé livre de abstração?
Peter Taylor

Respostas:

9

Deve-se notar que encontrar combinadores com certas propriedades de redução é sempre difícil, e encontrar o menor desses combinadores pode ser facilmente indecidível (por razões triviais, pois pode ser indecidível provar que uma certa aplicação do combinador pára mesmo).

Existem várias perguntas abertas e simples de sabor semelhante, por exemplo, problemas 4, 6 e 10 da lista de problemas abertos da TLCA .

Uma coisa a ser observada é que seu combinador certamente precisa ter pelo menos 2 variáveis ​​vinculadas, uma das quais é duplicada (como qualquer conjunto completo de combinadores) e uma precisa ser apagada. Isso coloca um limite inferior de 4, eu acho (2 abstrações e 2 aparências de uma variável), que não está tão longe do limite superior de 11.

Edit: Os comentários e referências de Noam empurram o limite inferior para 5! Eu não ficaria surpreso se a prova também exigir que a variável extra apareça também, o que nos levaria a 6.

cody
fonte
3
Na verdade, duas variáveis ​​não são suficientes ( dl.acm.org/citation.cfm?id=2100917 , cstheory.stackexchange.com/a/36344/674 ), portanto, isso fornece um limite inferior ligeiramente mais alto (tamanho 5 = 3 abstrações e 2 aplicações).
Noam Zeilberger
@NoamZeilberger tudo bem, esse é um resultado fantástico que eu não sabia!
Cody
7

Para sua primeira pergunta, acredito que este artigo pode ajudar bastante. Possui um cálculo combinador de 6 bits que também é um UTM. Também possui um combinador universal que parece ter o tamanho 7 com um elemento, dado o que você deseja. Eles chamam isso de Zot. http://arxiv.org/pdf/cs/0508056v1.pdf

Não tenho certeza se você pode dizer ou provar que existe um combinador mínimo. O artigo sugere que ele deve ter pelo menos menos de 6 bits.

Joshua Herman
fonte
2
O combinador de Zot é, na verdade, o último listado no OP: λx.xSK (compartilhado com seus idiomas pai, Iota e Jot), que possui o comprimento 11. No "cálculo combinator de 6 bits" (Keraia), os "6 bits" são o tamanho do UTM; e parece que é apenas uma codificação do cálculo lambda, não um cálculo combinador (e, portanto, não possui um combinador universal interno).
2012rcampion