# There are problems a computer can't solve?

What is the decidability of the following problem?

Given input $$A$$, which is an algorithm, determine whether it is true that "$$A$$ does not halt for any input".

To be more formal, let $$\{a_n\}_{n=0}^\infty$$ be a (computable) enumeration of all algorithms. Which of the options best describes the set $$\{n : n \in \mathbb{N} \wedge \text{there doesn't exist x such that a_n halts on input x}\}$$?

Details

• The set of natural numbers is the set of non-negative integers, i.e. $$\{0,1,2,3,\ldots\}$$.
• A subset of natural numbers $$L$$ is decidable if there is an algorithm, such that, when it receives input $$n$$, it halts with output $$1$$ if $$n \in L$$ and halts with output $$0$$ otherwise.
• A subset of natural numbers $$L$$ is semi-decidable if there is an algorithm, such that, when it receives input $$n$$, it halts if $$n \in L$$ and doesn't halt otherwise.
×