New answers tagged

1

You could start from the fact that the language $HP$ of the Halting problem is r.e. If its complement $\overline{HP}$ were r.e. too then that would mean that $HP$ is recursive (in $R$) which is impossible. Next, if there were at least one $k$ such that $L(M)^{\ge k} = \overline{HP}^{\ge k}$ then we could use this Turing machine $M$ to prove $\overline{HP}$ ...


1

The intuition is that finite languages are very simple in the sense that throwing a finite number of words from a language does not affect membership in $\text{R}$ or in $\overline{\text{RE}}$, etc. Therefore, since $L^{\geq k}$ is the result of throwing a finite number of words from $L$, we get that: $L(M)^{\geq k} \in \text{RE}$, and $\overline{HP}^{\geq ...


0

A simple solution for $L_1$: Check that for no input symbol there is a move to the left. As the machine will only ever encounter input symbols in it's long march to the right, this is enough.


1

For $L_1$, consider a computation $T(w)$ of a Turing machine $T$ that never moves its head to the left with input $w$. Let $\Gamma$ be the tape alphabet (including the blank symbol) and $Q$ be the set of states of $T$. Notice that, at any given step during the computation, the future behavior of $T(w)$ is completely determined by: The current state. The ...


1

It's basically correct, but it can be viewed as an oversimplification because that one sentence doesn't explain the details of how to feed it back into itself or why "feeding it back into itself" creates a paradox -- that requires additional explanation or justification.


2

The author is here referring to the Halting problem, and possibly also Rice's theorem (without putting words into their mouths). It says indeed that it's not possible to decide in advance whether a Turing machine will halt on any given input or not, thus it makes it impossible to decide in advance what the actual output of the machine will be. This is the ...


1

is EVEN undecidable? How can you prove its undecidability? It depends entirely on the enumeration that you use. E.g. one could make an enumeration that maps all Turing machines that halt with 1000 steps to an even index and all others to odd indices. Then EVEN is still an infinite set but decidable. However a simple way to prove EVEN undecidable (assuming ...


0

Unfortunately I cannot comment on Steven's answer, but I think the crux of the matter here is a confusion between the terms "problem", "class of problem" and "problem instance" (that is, when the machine and word are fixed, you have an instance of the halting problem, not a problem). As a side note, Turing did not prove in his ...


3

The problem of deciding whether, given a Turing machine $T$ and a word $w$, $T(w)$ halts is undecidable. If a Turing machine $T$ is fixed, the problem of deciding whether, given a word $w$, $T(w)$ halts might or might not be decidable (depending on the choice of $T$). As an example in which this problem is decidable consider the trivial Turing machine $T$ ...


-2

Predicting a random oracle is not solvable using, possibly, any kind of hypercomputation.


3

Let us say that $H$ is a partial Halting oracle if it takes as input a pair $(M,x)$ where $M$ is the description of a Turing machine and an input $x$, and: If $H$ terminates and outputs "yes" then $M(x)$ halts. If $H$ terminates and outputs "no" then $M(x)$ does not halt. In particular, $H$ is allowed to run forever and not give an ...


Top 50 recent answers are included