New answers tagged

0

The length of the smallest C program that generates a given string is known as the Kolmogorov complexity of the string. One of the basic properties of Kolmogorov complexity is its undecidability.


2

Concretely, we are always dealing with syntactical transformations, regardless whether there is a semantic theory that renders these transformations intelligible to us, or not. In the end, our ability to automatically demonstrate that two different programs are equivalent is restricted to properties that can be defined syntactically. Even then, there are ...


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


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


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


2

The answer is $\bf 0''$ (and so in particular computation in the limit - which corresponds to $\le_T\bf 0'$ - is not enough). And this stronger result is also folklore (I was assigned it as an exercise way back when). As an upper bound we just check quantifier complexity: $\Phi_e$ runs in polynomial time iff there exists some polynomial $p$ such that for ...


0

The question shows several misconceptions. I'll try to clarify the key aspects. If $L$ is recognizable but not decidable, then $L$ has to be infinite (otherwise, it is decidable). If a TM recognizes such $L$, it has to accept all the words in $L$ (by definition of "recognizes"), hence it must halt in infinitely many cases. A TM halting on infinitely many ...


Top 50 recent answers are included