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
  • 710
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.9k
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.9k
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.9k
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

Is $L = \{ \langle G,k\rangle \mid G $ has a simple cycle at length $k \}$ in P or in NP

Your understanding of how to demonstrate that a language belongs to NP is correct. If a language L consists of instances where each instance is a graph G and an integer k, and L is defined as the set ...
Michael's user avatar
  • 11
1 vote

Is $L = \{ \langle G,k\rangle \mid G $ has a simple cycle at length $k \}$ in P or in NP

I think that your friend is wrong and you are correct but your friend has a valid point actually while the run time is still polynomial I am still not sure if this is correct
munich markish's user avatar
1 vote
Accepted

Proof that nondeterministic TM runs in exponential time

Assuming $k$ is represented in binary, it takes $\lg k$ bits to represent $k$. So an algorithm whose running time is $\Theta(k)$ runs in time that is exponential in the length of the input. "...
D.W.'s user avatar
  • 158k
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
  • 191

Only top scored, non community-wiki answers of a minimum length are eligible