New answers tagged

2

Suppose you had such a TM, namely a machine $M$ for which the problem was "Does $M$ halt on empty input?" Certainly that problem would be decidable: one of two algorithms must be correct, (1) Answer "yes" or (2) Answer "no". The fact that we might not know which one is the correct algorithm is immaterial here; the only thing that matters is that we're sure ...


0

Use the same proof as Radó did in his paper: Assume there is a program $\Sigma$ that computes the value asked for, combine with a program that given $n$ computes $2 n$, and add $1$ to the result. Call the number of lines of the result $N$. Writing a program that computes $N$ should take at most $N$ lines (add $1$ $N$ times). Combine the above, the result is ...


0

Whatever your "initial tape configuration" may be, you can translate it into a Turing machine starting with blank tape by prepending enough processing to write your starting tape contents before starting your machine proper.


0

A language (set of strings) can be computable or not (also called decidable), which means that given a string $\sigma$ there is a Turing machine (more generally speaking, a program) that is guaranteed to halt in a finite time, telling correctly whether $\sigma$ belongs to the language or not. You can consider e.g. the language of all valid C programs that ...


0

Let's write formally what $L$ and $\overline{L}$ are: $$L=\{\langle M,w,b \rangle| (b=0 \wedge M(w) \mbox{ halts}) \vee (b=1 \wedge M(w) \mbox{ does not halt}) \}$$ $$\overline{L}=\{\langle M,w,b \rangle| (b=1 \vee M(w) \mbox{ does not halt}) \wedge (b=0 \vee M(w) \mbox{ halts}) \}$$ The latter is confusing, so let's rearrange it: $$\overline{L}=\{\langle ...


2

The notion of an "undecidable program" doesn't make sense, for the same reasons I gave in response to your last question. It makes sense to talk about whether a language is decidable or undecidable. It doesn't make sense to talk about whether a program is decidable or undecidable. If you check the formal definition of decidable, you'll see that ...


1

You were very close to the answer. The special case you mentioned can be handled by hand. Modify the machines resulting from the reduction such that, for each transition, where the machine halts and rejects, let the resulting machine go into an endless loop instead. Now each machine either accepts or goes into an endless loop. That means, checking if both ...


1

Because the problem HALT defined in the online source is different from yours. Their HALT is defined as: \begin{align} \{ \langle M, w\rangle \mid{} &M\text{ is a Turing machine, $w$ is a string,}\\ &\text{and $M$ }accepts\text{ $w$ after a finite computation}\} \end{align}


Top 50 recent answers are included