On the strongly generic undecidability of the halting problem
type: Item
instance of: scholarly article
title: On the strongly generic undecidability of the halting problem
zbMATH Open document ID: 1118.03033
author: Alexander Rybalov
published in: Theoretical Computer Science
publication date: 2007-06-06T00:00:00Z
Mathematics Subject Classification ID: 03D35
Mathematics Subject Classification ID: 03D10
Mathematics Subject Classification ID: 68Q05
zbMATH DE Number: 5161899
zbMATH Keywords: generic complexity
zbMATH Keywords: halting problem
MaRDI profile type: Publication
full work available at URL: j.tcs.2007.02.010
OpenAlex ID: W1983360706
cites work: MULTIPLICATIVE MEASURES ON FREE GROUPS
cites work: The halting problem is decidable on a set of asymptotic probability one
cites work: Generic-case complexity, decision problems in group theory, and random walks.
cites work: Average-case complexity and decision problems in group theory.
DOI: 10.1016/J.TCS.2007.02.010
Recommended article: On the generic undecidability of the halting problem for normalized Turing machines
Recommended article: Generic Complexity of Undecidable Problems
Recommended article: Generic complexity of undecidable problems
Recommended article: Q4376062
Recommended article: Undecidability in Some Structures Related to Computation Theory
Recommended article: Strong nondeterministic Turing reduction - a technique for proving intractability
Recommended article: Undecidability and intuitionistic incompleteness
Recommended article: Some undecidability results in strong algebraic languages
Recommended article: Formalization of the undecidability of the halting problem for a functional language
Recommended article: DECIDABILITY AND UNIVERSALITY IN THE AXIOMATIC THEORY OF COMPUTABILITY AND ALGORITHMS
description: scientific article; zbMATH DE number 5161899