On the strongly generic undecidability of the halting problem

DOI10.1016/J.TCS.2007.02.010zbMATH Open1118.03033OpenAlexW1983360706MaRDI QIDQ884482FDOQ884482

Alexander Rybalov

Publication date: 6 June 2007

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2007.02.010

zbMATH Keywords

halting problemgeneric complexity

Mathematics Subject Classification ID

Turing machines and related notions (03D10) Undecidability and degrees of sets of sentences (03D35)

Cites Work

• Generic-case complexity, decision problems in group theory, and random walks.
• MULTIPLICATIVE MEASURES ON FREE GROUPS
• Average-case complexity and decision problems in group theory.
• The halting problem is decidable on a set of asymptotic probability one

Cited In (8)

• Generic amplification of recursively enumerable sets
• A Parameterized Halting Problem
• Asymptotic density, immunity and randomness
• The origins of the halting problem
• The generic complexity of the bounded problem of graphs clustering
• On the generic undecidability of the halting problem for normalized Turing machines
• Generic complexity of undecidable problems
• The generic complexity of the graph triangulation problem

Recommendations

• Title not available (Why is that?) 👍 👎
• Generic complexity of undecidable problems 👍 👎
• Undecidability and intuitionistic incompleteness 👍 👎
• Strong nondeterministic Turing reduction - a technique for proving intractability 👍 👎
• Formalization of the undecidability of the halting problem for a functional language 👍 👎
• On the generic undecidability of the halting problem for normalized Turing machines 👍 👎
• Generic Complexity of Undecidable Problems 👍 👎
• Undecidability in Some Structures Related to Computation Theory 👍 👎
• Some undecidability results in strong algebraic languages 👍 👎
• DECIDABILITY AND UNIVERSALITY IN THE AXIOMATIC THEORY OF COMPUTABILITY AND ALGORITHMS 👍 👎

This page was built for publication: On the strongly generic undecidability of the halting problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q884482)