New answers tagged

0

Intuitively, $L$ is not decidable as given $\langle M_1, M_2, w\rangle$ we need to decide whether $w\in L(M_1)$, and $w\in \overline{L(M_2)}$. The first condition smells like deciding the language $A_{TM} = \{ \langle M, w \rangle: \text{ $M$ accepts $w$}\}$, and the second condition smells like deciding $\overline{A_{TM}}$. To make sure that the intuition ...


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


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


2

As you suggested, think how to reduce from the halting problem $Halt_{TM} = \{ \langle M, w\rangle: \text{$M$ halts on $w$} \}$. On input $\langle M, w\rangle$, the reduction should output a pair of TMs $\langle K_1, K_2\rangle$; such that $M$ halts on $w$ iff $L(K_1) = L(K_2)$. This is somehow a basic reduction that can be done by standard tricks, so it ...


2

If $M$ does not have the option to not move its head at all, as stated in a comment to the question, then the problem is trivially decidable by the Turing machine that immediately halts and accepts. If $M$ might not move its head while computing $T(w)$ and the problem is to decide whether it actually does so, then the problem must be undecidable as otherwise ...


1

Edit: the answer assumes that the tape of a TM is left bounded, that is, the tape has a leftmost cell. Given $\langle M, w\rangle$, $M$ does not move its head while running on the input $w$ when its in never the case that the head of $M$ is at the leftmost and the next transition suggests that $M$ moves its head to the left. Now can we decide whether this ...


2

If $L$ is undedidable and $A$ is finite, then $L \cup A$ is undecidable. To see this notice that, given $w \in \Sigma^*$: $$w \in L \iff (w \in L \cap A) \; \vee \; (w \in L \cup A \;\wedge\; w\not\in A).$$ Since $A$ if finite both $A$ and $L \cap A$ (which is also finite) are decidable. That is, we can test whether $w \in L \cap A$ and whether $w \not\in A$....


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.


1

The language $L$ is not decidable, this is an immediate consequence of Rice's theorem (you can instead try and prove that $L$ is not decidable directly using reductions). To begin with, there are two machines $M_1$ and $M_2$ such that $L(M_1)\in coRE$ and $L(M_2)\notin coRE$. For example, $M_1$ can be a machine that accepts all inputs, and $M_2$ can be a ...


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


0

I wanted to simply comment this, but given my current reputation, I can't. I am not sure how broad your definition of properties. But certain properties of a TM may not be decidable. A simple one is to check if an accept state is useful. That is, if the accept state will ever be entered. To see, we can construct a TM M that when executed ignores its input ...


0

The language $L$ is not in $\text{RE}$. Consider the complement of the halting problem $\overline{Halt_{TM}} = \{ \langle M, w\rangle: \text{ $M$ does not halt on $w$}\}$ which is not in $\text{RE}$. We show that $\overline{Halt_{TM}}$ reduces to $L$ (and therefore, $L \notin \text{RE}$). From this point, I am assuming w.l.o.g that every machine has an input ...


0

Let us start by properly defining your language as say $$L = \{\langle M \rangle \mid M \text{ rejects some input } x \in \Sigma^\ast\}$$ where $\langle \cdot \rangle$ denotes some suitable encoding over our alphabet $\Sigma$. To reduce $L$ to the halting problem $\mathrm{Halt} = \{\langle M, w \rangle \mid M \text{ halts on } w\}$ we consider some $\mathrm{...


Top 50 recent answers are included