New answers tagged

2

Whether $\mathsf{HALT}_{M_0}$ is decidable or not depends on $M_0$. For example, if $M_0$ always halts, the $\mathsf{HALT}_{M_0}$ is trivially decidable, whereas if $M_0$ interprets its input as a Turing machine $M$ which it runs on the empty input, then $\mathsf{HALT}_{M_0} = \mathsf{HALT}_\epsilon$ is undecidable (see below). The language $\mathsf{HALT}_{...


6

You are committing a logical error. This question has nothing whatsoever to do with computability and machines. It is entirely about how to prove that something does not exist. Namely, to show the statement $$\lnot \exists x . \phi(x)$$ we do as follows: Assume that there is $x$ such that $\phi(x)$. We assume this even though perhaps we have no idea how to ...


7

First, let us see what the halting proof attempts to prove: There is no program $H$ that, on input $(x,y)$, always halts, and returns whether the program encoded by $x$ halts when run on the input $y$. We call the function which $H$ is supposed to compute the halting predicate. The program you are suggesting, which consists of simulating a run of ...


Top 50 recent answers are included