THE BASIS DECISION PROBLEM IN LAMBDA-CALCULUS

被引：0
作者：
INTRIGILA, B [1 ]
机构：
[1] UNIV LAQUILA,DIPARTIMENTO MATEMAT PURA & APPLICATA,I-67100 LAQUILA,ITALY
来源：
MATHEMATICAL LOGIC QUARTERLY | 1993年 / 39卷 / 02期
关键词：
LAMBDA-CALCULUS; BASIS DECISION PROBLEM;
D O I：
10.1002/malq.19930390120
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
We show that the problem of deciding if a finite set of closed terms in normal form is a basis is recursively unsolvable. The restricted problem concerning one element sets is still recursively unsolvable.
引用
收藏
页码：178 / 180
页数：3
相关论文
共 50 条
  • [41] Objects and their lambda calculus
    Tzouvaras, A
    THEORETICAL COMPUTER SCIENCE, 2001, 258 (1-2) : 209 - 232
  • [42] THE SAFE LAMBDA CALCULUS
    Blum, William
    Ong, C. -H. Luke
    LOGICAL METHODS IN COMPUTER SCIENCE, 2009, 5 (01) : 1 - 38
  • [43] Lambda calculus with patterns
    Klop, Jan Willem
    van Oostrom, Vincent
    de Vrijer, Roel
    THEORETICAL COMPUTER SCIENCE, 2008, 398 (1-3) : 16 - 31
  • [44] A Simpler Lambda Calculus
    Jay, Barry
    PROCEEDINGS OF THE 2019 ACM SIGPLAN WORKSHOP ON PARTIAL EVALUATION AND PROGRAM MANIPULATION (PEPM '19), 2019, : 1 - 9
  • [45] EQUIVALENCE OF EVAL-READBACK AND EVAL-APPLY BIG-STEP EVALUATORS BY STRUCTURING THE LAMBDA-CALCULUS'S STRATEGY SPACE
    Nogueira, Pablo
    Garcia-perez, Alvaro
    LOGICAL METHODS IN COMPUTER SCIENCE, 2024, 20 (04) : 1 - 76
  • [46] The lambda-context Calculus
    Gabbay, Murdoch J.
    Lengrand, Stephane
    ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE, 2008, 196 (19-35) : 19 - 35
  • [47] A lambda calculus for quantum computation
    van Tonder, A
    SIAM JOURNAL ON COMPUTING, 2004, 33 (05) : 1109 - 1135
  • [48] Algorithms, The lambda Calculus and Programming
    Vichare, Abhijat
    RESONANCE-JOURNAL OF SCIENCE EDUCATION, 2013, 18 (04): : 345 - 367
  • [49] On the algebraic models of lambda calculus
    Salibra, A
    THEORETICAL COMPUTER SCIENCE, 2000, 249 (01) : 197 - 240
  • [50] A Nominal Axiomatization of the Lambda Calculus
    Gabbay, Murdoch J.
    Mathijssen, Aad
    JOURNAL OF LOGIC AND COMPUTATION, 2010, 20 (02) : 501 - 531
12345