On effective undecidability and Post's problem

2014/09/03 by Bas Westerbaan, Westerbaan, Bas
Mathematics · #FOS: Mathematics #Logic (math.LO) #math.LO

paper · pdf · doi:10.48550/arxiv.1409.1030

arxiv created 2014/09/03 · arxiv updated 2014/09/04

Abstract

In this thesis, we will look at some known and some previously uninvestigated notions of effective undecidability. We try to discover how far we can stretch effective undecidability in the hope to get a more tractable solution to Post's problem, than that of Friedberg and Muchnik.

Related

• Another proof of undecidability for the correspondence decision problem - Had I been Emil Post
• Systemic Constraints of Undecidability
• (Generalized) Post Correspondence Problem and semi-Thue systems
• Undecidability everywhere?
• Did Turing prove the undecidability of the halting problem?