Turing Impossibility Properties for Stack Machine Programming

2012/01/29 by J.A. Bergstra, Bergstra, J. A., C.A. Middelburg +1
Computer Science · #Computability, Logic, AI Algorithms #FOS: Computer and information sciences #Logic in Computer Science (cs.LO) #Machine Learning and Algorithms #Optimization and Search Problems

paper · pdf · doi:10.48550/arxiv.1201.6028

openalex publication_date 2012/01/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01

Abstract

The strong, intermediate, and weak Turing impossibility properties are introduced. Some facts concerning Turing impossibility for stack machine programming are trivially adapted from previous work. Several intriguing questions are raised about the Turing impossibility properties concerning different method interfaces for stack machine programming.

Citations

• Putting Instruction Sequences into Effect
• On Computable Numbers, with an Application to the Entscheidungsproblem

Related

• The "paradox" of computability and a recursive relative version of the Busy Beaver function
• Notes on Stack Machines and Quantum Stack Machines
• Thoughts on sub-Turing interactive computability
• Alternating Pushdown and Stack Automata
• Unconstrained Church-Turing thesis cannot possibly be true