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.
×

Problem Loading...

Note Loading...

Set Loading...