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.

×

Problem Loading...

Note Loading...

Set Loading...