A Machine-Independent, Log-Sensitive Space-Cost Measure for the Weak Lambda-Calculus

2017/11/28 by Ugo Dal Lago, Biernacka, Małgorzata, Beniamino Accattoli +4 · 2 citations
Computer Science · Mathematics · #Algorithm #Artificial intelligence #Calculus (dental) #Church encoding #Computability, Logic, AI Algorithms #Computer science #Discrete mathematics #Encoding (memory) #Lambda #Lambda calculus #Logic, programming, and type systems #Mathematics #Physics #Programming language #Simply typed lambda calculus #Turing #Turing machine #Typed lambda calculus #semigroups and automata theory

paper · pdf · doi:10.4230/lipics.itp.2022.7

openalex publication_date 2017/11/28 · openalex created_date 2017/12/04 · openalex updated_date 2026/07/28

Abstract

This note is about encoding Turing machines into the lambda-calculus.

Citations

• (In)Efficiency and Reasonable Cost Models

Cited by

• (In)Efficiency and Reasonable Cost Models
• Lambda calculus [wikipedia]

Related

• Reasonable Space for the λ-Calculus, Logarithmically
• A Log-Sensitive Encoding of Turing Machines in the λ-Calculus
• An Invariant Cost Model for the Lambda Calculus
• Two Decreasing Measures for Simply Typed Lambda-Terms (Extended Version)
• Multi Types and Reasonable Space (Long Version)