Logic/Computability

Subject Classification

ACM: Theory of computation~Computability

AMS: Mathematical logic and foundations / Computability and recursion theory

2026

The Busy Beaver Function

by Arthur Freitas Ramos, David Barros Hulak and Ruy Jose Guerra Barretto de Queiroz

Jun 01

SAT is Not Solvable in Constant Time

by Daniel Shea

Mar 26

2023

The Halting Problem is Soluble in Malament-Hogarth Spacetimes

by Mike Stannett

Apr 29

The Cook-Levin theorem

by Frank J. Balbach

Jan 08

2022

Automation of Boolos' Curious Inference in Isabelle/HOL

by Christoph Benzmüller, David Fuenmayor, Alexander Steen and Geoff Sutcliffe

Dec 05

A Verified Translation of Multitape Turing Machines into Singletape Turing Machines

by Christian Dalvit and René Thiemann

Nov 30

Diophantine Equations and the DPRM Theorem

by Jonas Bayer, Marco David, Benedikt Stock, Abhik Pal, Yuri Matiyasevich and Dierk Schleicher

Jun 06

Ackermann's Function Is Not Primitive Recursive

by Lawrence C. Paulson

Mar 23

2020

Some classical results in inductive inference of recursive functions

by Frank J. Balbach

Aug 31

2019

Universal Turing Machine

by Jian Xu, Xingyuan Zhang, Christian Urban, Sebastiaan J. C. Joosten and Franz Regensburger

Feb 08

2018

Minsky Machines

by Bertram Felgenhauer

Aug 14

2008

Recursion Theory I

by Michael Nedzelsky

Apr 05