New answers tagged

-1

Your algorithm will work properly if step 3 is modified to make sure that an uncrossed $b$ is always the last symbol of the input string (which is true even if $n$ is 0), rejecting the input string otherwise. That'll make sure that the number of $b$'s has remained a power of 2 during the entire process, and should make the first instruction numbered "6" ...


1

In slightly more detail, what's happening is: Run the machine on input $s_1$ for one step. If it accepts, list the string. If the machine didn't halt on the previous step, run the machine on $s_1$ for one more step and then on $s_2$ for a step. As before, if the machine accepts either string, list them and remove them from consideration. Do the same thing ...


1

A language is Turing-recognizable (or Recursively enumerable) iff there exists a Turing Machine which will enumerate all valid strings of the language. What you probably miss in the above proof is the fact that $i$ can take any value ... when we say $i$ steps, we can mean $10$, $100$, $100000$, $\infty$ steps. Basically $i$ is an index that indicates the ...


3

You are technically correct. A modern practical computer has finitely many states, and so any program it runs will eventually repeat a state. However, I would like to warn against interpreting this observation in the wrong way. It is not a problem in practice. The number of possible states is huge (it's huuuuuuuuuuuuuuuuuuuuge). Algorithms that are designed ...


0

Consider the following algorithm: $n \gets 0$ repeat: $n \gets n+1$ The algorithm runs for infinitely many steps without repeating the same state.


1

Let HALT be the following version of the halting problem: Given a Turing machine $T$, determine whether it halts on the empty input. Here is a computable reduction from HALT to $L_{all}$: Given a Turing machine $T$, construct a Turing machine $T'$ which erases its input and then transfers control to $T$. You can check that $T \in \mathrm{HALT}$ iff $T' \in ...


0

https://www.longdom.org/articles/reverse-engineering-turing-machines-and-insights-into-the-collatz-conjecture.pdf is one initial effort to do this for some subclass of Turing machines. Actually there is fantastic culture about it http://bluesky-home.co.uk/. These works almost exclusively cite the author itself, that indicates how undeveloped this field is. ...


1

No pushdown automaton can recognize this language, because the language is not context-free. This can be shown using the pumping lemma for context-free languages or Parikh's theorem. The latter gives a particularly straightforward proof: the language is not context-free because $2^n$ cannot be written as a finite union of linear functions. The language is ...


1

Actually this language is not a CFL. And here is a proof: Let's take string $w: a^mb^{2^m}$ where $m$ is constant guaranteed by pumping lemma for CFLs. Then $a^{m+k_1}b^{2^m+k_2} \in L$ where $1\le k_1,k_2<m$ (cases invloving either $k_1 = 0$ or $k_2=0$ are easier.) Now, that suggests that, $2^{m+k_1} = 2^m + k_2$ (by defination of $L$) $\therefore ...


-3

If a programming language has "branch (e.g. if)" and "loop (e.g. for/while)", it is Turing-complete, and vice versa. Having "branch" and "loop" is necessary and sufficient conditions for Turing-completeness. Haskell's recursion is a kind of loop.


2

The answer is "we don't know without more information" for all 4. Suppose $f$ is the identity function $f(x) = x$. Then $f \circ g = g \circ f = g$, which is non-computable. On the other hand, suppose $g$ is a total non-computable function (which is a special case of $g$ being a partial non-computable function), and suppose $f$ is the constant zero ...


3

P is a subset of NP, so any P language is NP as well. Also note that any deterministic machine is a non-deterministic machine where the image of the transitions function has always a size exactly equal to one. This implies that from each configuration you get a unique following configuration.


2

Your problem is decidable. If $M$ always executes less than 5 steps, then it never sees more than the first 4 symbols of its input. Hence it suffices to run $M$ on all inputs of length at most 4.


2

$D$ verifies $\langle M \rangle$ is a (deterministic) TM and then builds the configurations graph and checks if the initial configuration of $\epsilon$ is connected to an accept state (there are only finitely many) and returns true if there is and false if there isn't. The problem here is that, even if you define the TM so that there are only finitely many ...


0

then builds the configurations graph and checks if the initial configuration of ϵ is connected to an accept state (there are only finitely many) and returns true if there is and false if there isn't. The above is just another way of saying: run $M$ on $\epsilon$ and wait to see if the machine halts or not. This, hovewer, is not deciding the language $L$.


0

Q1: A state can get repeated. The point is that if a state gets repeated and no non-empty symbol has even been written, then you known the that the Turing machine will never halt as it is necessarily stuck cycling through some of the states encountered so far. Since none of the states of the cycle caused the TM to write a non-blank symbol, the TM will never ...


0

So I feel the definitions of universal language differs in both sources. Q1. Right? You quoted Ullman's definition for Universal language but didn't quoted the other source definition of universal language. The other source defined universal Turing machine which is not language. So the answer to your first question is that no you aren't right since the ...


0

So first Q1: At first the definitions of universal language and the universal machine. The universal language is defined as you mentioned in the question: $$ U= \{(M,w)\:|\:\text( TM\:M\:accepts\:w)\} $$ The Universal Turing Machine on the other hand is defined as follows: A machine, which can simulate an arbitrary TM on arbitrary input. Or you can say: ...


5

There is no known natural example of such a pair, and indeed there are various results in computability theory suggesting that such a pair does not exist. So to whip up an example one has to do some work. The simplest approach (indeed, the easiest I know) is via mutual diagonalization: we build inductively a pair of increasing sequences of infinite binary ...


2

Just take for $L_2$ an undecidable language of $a^*$ and take $L_1 = L_2 \cup \{b\}$. Then $L_2$ is also undecidable and $L_2 - L_1 = \{b\}$ is regular.


2

As you suspected, it can happen that $L_1-L_2\not=a^*$. The assumption that $H$ does not contain $a^*$ does not imply that $\lnot H$ must contain $a^*$. For example, if $H\cap a^*= \{a^2\}$, then $\lnot H$ does not contain $a^2$, let alone $a^*$. The technique to arrive at a simple solution is to let the regular part be disjoint with $L_2$. Here is the ...


3

Your example almost works. You need to make sure that the regular part is disjoint from the non-decidable part. Suppose our alphabet has at least two symbols, say $a$ and $b$. Consider any undecidable langauge $H$, for example the halting set, and define $$L_2 = \lbrace b w \mid w \in H\rbrace$$ and $$L_1 = L_2 \cup \lbrace a \rbrace.$$ Now it is obvious ...


-1

If we are saying non deterministic Turing machine and LBA are same then its wrong. If we say non deterministic Turing machine with limited space then we can call it as LBA. LBA has space boundaries where as Turing machine don't have.


1

Maybe you can write sth like "Σ\2 → x, R" on the transition. But as Yuval Filmus mentioned, the notations always depend on the lecturer.


1

A Turing machine diagram is a form of communication. Its goal is to describe a Turing machine — usually defined as a tuple with a specific format — in a form which is easier to grasp. As such, you can use whatever shortcut you want, as long as everybody understands what you mean. This might entail your explaining some non-standard notation which ...


1

You could write $\neq 2 \to x,R$, but you might have to explain somewhere that by that you mean that the transition is taken as long as the symbol read is not $2$. More generally, you can use whatever notation you want as long as you explain it and it's unambiguous. This is the answer of a practical mathematician. Your professor could have different ideas.


0

Rice theorem can be applied when we are talking about languages of Turing machines, not about Turing machine behavior or characteristics themselves or anything else which is not related to "only" languages they accept. You are talking about a narrow Rice's theorem. In Wikipedia, it states that Rice's theorem can also be put in terms of functions: for ...


0

You're right that both of these are non-trivial properties. The key is, Rice's theorem applies only to non-trivial semantic properties. So what defines a semantic property? Intuitively, a "semantic" property is a property of what the machine does, rather than how the machine works. If you treat the machine as a black box that takes input and gives output, ...


4

You said in a comment: I am talking to process this encoding, not the tape content. But the tape content affects the behavior of the TM, including whether it would enter an accepting state. The exact same TM in the exact same state might later accept, or not accept, depending only on what is on the tape. You want to "go through all encoded transitions ...


2

Because this process doesn't necessarily end; you can end up discovering more and more possible configurations (state+tape) which would lead to accepting if they were ever reached, but never a legal initial configuration.


6

No. A state of $n$ qubits can be represented with a vector of size $2^n$, and quantum gates can be implemented as linear operations for those vectors. Therefore a quantum computer can be simulated with a Turing machine, although with an exponential overhead. It is also known that the class of problems solvable by a quantum computer in polynomial time, BQP, ...


Top 50 recent answers are included