New answers tagged

0 votes

Is $\{\langle \langle M\rangle, q\rangle\mid M(\varepsilon)$ enters state $q$ infinite times$\}$ not in RE?

I got it. Using reduction $\overline{HP} \leq L$ with $f\left ( \left ( \left \langle M \right \rangle ,x \right ) \right ) = \left ( \left \langle M_x \right \rangle ,q\right )$ where $M_x$ is a TM ...
mikealexx's user avatar
0 votes

Is $\{\langle \langle M\rangle, q\rangle\mid M(\varepsilon)$ enters state $q$ infinite times$\}$ not in RE?

Hint: given a Turing machine $M$ and a word $w$ over $M$'s alphabet, consider a machine $T$, that on the empty word simulates the run of $M$ on $w$. Can you force $T$ to visit a state infinitly often ...
Bader Abu Radi's user avatar
1 vote

Is $\{\langle \langle M\rangle, q\rangle\mid M(\varepsilon)$ enters state $q$ infinite times$\}$ not in RE?

The machine would go in an infinite loop if there is at least one state that it visits an infinite number of times (By pigeon-hole principle). Hint: Dovetailing
Zee's user avatar
  • 89
3 votes
Accepted

Time complexity of specific variant of Turing Machine

If the machine is a decider, meaning halts on its input $w$, then it does not repeat a configuration in its run on $w$. Hence, the number of configurations that the machine can be in bounds its ...
Bader Abu Radi's user avatar
2 votes
Accepted

Undecidability of the exactly-1-in-k halting problem

Consider a Turing Machine $M_1$. Create $k - 1$ looping machines $M_2, …, M_k$ that never halts. Then $M_1$ halts on all inputs if and only if for any input, exactly one among $M_1, …, M_k$ halts. ...
Nathaniel's user avatar
  • 13.8k
3 votes

Are there some additions that a Turing machine cannot perform

The cardinality of even natural numbers is the same as the cardinality of natural numbers. That does not mean that odd natural numbers do not exist.
Nathaniel's user avatar
  • 13.8k
5 votes
Accepted

Is the language L = {<M> | There exists an M' that stops on the same input words, but L(M) ≠ L(M')} in RE or R?

Notice, that all machines $M$ that don't halt on any input accept the same language, $\emptyset$. Thus if $M$ doesn't halt on any input then also $\langle M \rangle \notin L$. Now define the TM $M'$ ...
Knogger's user avatar
  • 595
2 votes

Turing Machine language, Undecidable, reductions

Before doing reductions, it is good to have some intuitions about decidability: that helps to find which reduction can succeed. First, none of those two languages is recursive, because Rice's theorem ...
Nathaniel's user avatar
  • 13.8k
0 votes
Accepted

Do there exist infinitely many languages that are RE-complete?

Yes, you are correct. By altering the value of k in the padding argument, we generate a distinct language for each different k.
munich markish's user avatar
2 votes
Accepted

Proof or disproof Fin = Fin-Complete $ Fin = \{ L \in \Sigma^* : |L| $ is finite and greater than 0 $ \} $

The claim is correct. To see why, note that every language in $L\in Fin$ is non-trivial and regular. Indeed, $L$ is not empty, by the definition of $Fin$, and does not equal $\Sigma^*$ as then it ...
Bader Abu Radi's user avatar
1 vote

Prove that there aren't any complete languages

I don't think your attempt works. $A \leq_T B$ doesn't imply $A \cap B \neq \emptyset$, take for example $$A = a^*, B = b^*.$$ We have $A \cap B = \emptyset$ as well as $A \leq_T B$. Also, it ...
Knogger's user avatar
  • 595
1 vote
Accepted

Prove that there aren't any complete languages

Doesn't this follow by a counting argument? Fix a language $C\subseteq \Sigma^*$. On the one had, the number of languages that are Turing-reducible to $C$ is at most $\aleph_0$. Indeed, there are only ...
Bader Abu Radi's user avatar
0 votes

Prove the existence of a language L over the alphabet Σ = {1} such that L ∌ RE and L ∌ CoRE

Your language is neither in RE nor in co-RE, and the reductions you have mentioned prove this. However, it is unclear to me whether your language is using only the alphabet $\{1\}$. This depends on ...
Arno's user avatar
  • 2,995
2 votes

Is there a language $L$ such that $L \in DSPACE(1) \setminus DTIME(1)$?

No. Consider the language $$L = \{x \in \{0,1\}^* \mid x \text{ has even parity}\},$$ i.e., $$L = \{x_1 \cdots x_n \mid x_1 + x_2 + \cdots + x_n \equiv 0 \pmod 2\}.$$ This language is in $\textsf{...
D.W.'s user avatar
  • 158k
0 votes
Accepted

Prove the existence of a language L over the alphabet Σ = {1} such that L ∌ RE and L ∌ CoRE

Both reductions look fine and are easy to come up with. You need to ask your instructor what is wrong with your suggested reductions. A reduction from $HP$ to $L_1$ operates as follows. Given input $\...
Bader Abu Radi's user avatar
2 votes
Accepted

Proof or Disproof if $ L $ is a Regular language then it has to be that $ L\leq HP $

From your attempt, I see that you got the intuition, but you need to define the reduction formally, and then prove that it works. In your solution, it is not clear how $M'$ is defined, and what is $M_{...
Bader Abu Radi's user avatar
0 votes

$L =$ { $\langle M \rangle$ | $M$ moves left on at least one input }

Concerning the general question Could two such “versions” of a language, where one version asks about any input and the other about a specific input, differ in decidability?: They sure can. E.g., ...
Emil Jeřábek's user avatar
0 votes
Accepted

$L =$ { $\langle M \rangle$ | $M$ moves left on at least one input }

The language $L'$ is decidable. Consider the operation of a TM $M$ on an input $w$. If $M$ does not move its head to the left when it runs on $w$, then after $|w|-1$ steps, $M$'s head reaches the ...
Bader Abu Radi's user avatar
2 votes
Accepted

proof or disproof if $ L_1 \subseteq L_2 $ then $ L_1 \leq L_2 $

The claim essentially says that if $L_1$ is included in $L_2$, then $L_2$ is harder than $L_1$, which clearly cannot be correct as the biggest language w.r.t containment is very simple. So you can ...
Bader Abu Radi's user avatar
0 votes

How complement of ETM is semidecidable

Consider an alphabet $\Sigma$, and let $w_1, w_2, w_3, \ldots$ denote all words in $\Sigma^*$ in minlex order, that is, for all $i < j$, one of the following holds: (1) either $|w_i| < |w_j|$, ...
Bader Abu Radi's user avatar
2 votes
Accepted

Proof or disproove $L_1 , L_2 \in RE \setminus R $ such that $ L_1 \cup L_2 \in R $ and $ L_1 \cap L_2 \in R $

Let us assume that $L_1$ and $L_2$ are both computably enumerable, and that $L_1 \cap L_2$ and $L_1 \cup L_2$ are decidable. I claim that $L_1$ is decidable, too. Given some $w \in \Sigma^*$, I want ...
Arno's user avatar
  • 2,995
1 vote

Language of Turing Machines that only accept their own encodings

You can reduce K to L: Let K = {e | e's Turing machine halts on e} Let f(x,y) be f(x,y) = Code of the following machine: For any input w: Run y's Turing machine on y. If w = x, accept. Otherwise ...
Ali Dastjerdi's user avatar
3 votes

A Turing machine for which it is impossible to predict whether it halts or not on a fixed input

For any specific machine $M_0$ and input $w_0$, there is a machine that decides whether $M_0$ halts on $w_0$. Indeed, one of the following machines works: The machine that outputs "Yes". ...
Yuval Filmus's user avatar

Top 50 recent answers are included