# Tag Info

## Hot answers tagged undecidability

8

A popular reference is the article Undecidable Problems for Context-free Grammars by Hendrik Jan Hoogeboom. The following is a proof taken from this note by Rob van Glabbeek. Theorem: It is undecidable whether or not the languages generated by two given context-free grammars have an empty intersection. Proof: By a reduction of post correspondence problem (...

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

5

Post correspondence problem can be solved using a brute force approach. No. Brute force can be applied only if the number of dominoes we are going to use, is finite. For example, if we restrict each domino to be used at most once, then the number of possibilities will be finite and we can use a brute force algorithm. But the PCP allows us to use each ...

5

Your exam question makes very little sense. The obvious reading would be this: Let $M$ and $N$ be two Turing machines. Why is it not possible to prove that $M$ and $N$ compute the same function? More precisely: It is not the case that for all Turing machines $M$ and $N$ it is provable that $M$ and $N$ compute the same function. Well, this is quite ...

4

You haven't defined HALT, so let me assume that it consists of all Turing machines that halt on the empty input. If $M$ halts in time $f(n)$, then in particular it halts on the empty input, and so if $M$ belongs to your language then it also belongs to halt. But the converse doesn't hold, and $L \subseteq HALT$ doesn't imply anything about $L$ (for example, $... 4 The inference "the universe would be completely computable, so no undecidable/uncomputable things could exist" is invalid. In the effective topos, where everything is computable, there are many undecidable phenomena. For example, all real numbers are computable, but equality of real numbers is undecidable (and computable). To give you an idea how this ... 4 If$A=\{0,1\}^*$then$A\cup B=\{0,1\}^*$, regardless of what$B$is.$\{0,1\}^*$is decidable, and choosing to express it as something involving undecidable things doesn't change that fact. The question "Is$w$in$A\cup B$?" is equivalent to "Is at least one of the following statements true?$w$is in$A$;$w$is in$B$;$w$is in both$A$and&... 4 There are several issues with your question but perhaps I can clarify some issues. First off you assume$f(1) = 1.999...$and also that no$x \in \mathbb{N}$exists such that$f(x) = 2$but that's a contradiction in terms because$1.999... = 2$and thus$f(1) = 2$. Why does$1.999... = 2$? Well there's an easy answer but not fulfilling answer and a more ... 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 ... 4 A run of a TM is a sequence of configurations, where each configuration states the contents of the tape (from the left marker, up until the point where it is blank all the way to the right), the location of the head, and the state. An important feature of (deterministic) TMs is that you can uniquely continue a run from a given configuration. That is, a ... 3 Yes, your thought is correct. The only missing part, as you pointed out, is whether or how we can create a CFL algorithmically for the intersection of a CFL with a RL. If you take a close look at any proof for the fact that the intersection of a CFL with a RL is a CFL, you will find that the proof is constructive or can be made to be constructive easily, ... 3 There are two important misunderstandings in your question. You talk about "the Turing machine" for a language but there isn't just one: in fact, if a language is recursive (or RE) then there are infinitely many Turing machines that decide (or accept) it. If a Turing machine decides a language$L$then, by definition, it accepts every input in$L... 3 Do we ever take into consideration a word with infinite length during such analysis? Never say never. However, it is a safe bet that in the course of your undergraduate or even graduate study you can assume that all inputs to Turing machines are finite. Here is a more formal restatement/understanding of the problem in the question. \begin{align}\text{... 3 This is a situation where coding is non-trivial. \mathcal{C}_T is a class of decidable languages. To make sense of \mathcal{C}_T having any effective properties, we need to choose a coding. Naturally, we would code some decidable language L by the index of some TM that decides it. So what does it mean for \mathcal{C}_T to be recursively enumerable? ... 3 If you are interested in the effect of being able to compute with continuous real numbers, you might enjoy learning about the Blum-Shub-Smale theory of computation with the reals. A good survey is Computing over the Reals: Where Turing Meets Newton by Lenore Blum. Wikipedia states that the set of functions that are computable in this model are incomparable ... 3 If you give a word w not in the language, then the TM is not guaranteed to halt as an NPDA isn't always guaranteed to terminate in finite steps for a finite word. So, you can produce a counter example in which your construction doesn't work. Take an NPDA which doesn't terminate for a given word (exists, of course) and run your algorithm on that word. ... 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 defineL_2 = \lbrace b w \mid w \in H\rbrace$$and$$L_1 = L_2 \cup \lbrace a \rbrace.$$Now it is obvious ... 2 Let us follow the hint given by Yuval. What is the halting problem? It is the problem of accepting the following language.$$\text{HALT}= \{⟨M, w⟩ : M \text{ is a TM and }M\text{ will halt on input } w\}$$What is the current problem? It is the problem of accepting the following language.$$\begin{align} \text{One}&\text{StateBeforeAnother} = \{⟨M,... 2 In short, A LBA has finite number of configurations, say D. Hence, we can run for D steps and conclude the result. If it runs for more that D steps, by pigeonhole principle, we can say that, it is stuck in an infinite loop. 2 Because we cannot find, given a NTMN$and an input$x$, whether$N$fulfills the condition$N(x)\not= x$in any given finite amount of time. More precisely, we cannot enumerate all pairs$(N,x)$such that$N(x)\not= x$, although we can enumerate all pairs$(N,x)$such that$N$halts on$x$and$N(x)\not= x$. Think for a moment. When can you consider$(N,x)...

2

It isn't recognizable because it is infinite, therefore it'll loop infinitely. Does this work? No, because that claim is false. And your writing isn't at all clear, here. Recognizability is a property of languages, so your first two "it"s must refer to languages; but "loops infinitely" is a property of Turing machines, so your third "it" must be one of ...

2

You can use the counter value as the result of the function. Furthermore, if I understood well your question, a simple way to map $(bool,nat)$ is the following: modify the state transitions of the original automata $A$ to make the counter value equal to $2x$ if the counter of the original A is $x$ and the state is rejecting, $2x+1$ if the counter of the ...

2

It's a bit vague to talk about "models of universe". Let's stick to models of mathematics, as these are actually well understood. For example, we can ask about a topos (a model of a certain kind of set theory and higher-order logic, sufficient to develop theoretical physics) in which every map is continuous. Does it follow that some of the maps must be non-...

2

A stronger result than Turing's halting problem is Rice's theorem: the determination of any nontrivial property of programs is undecidable. To be precise, that's a semantic property, i.e. any property of programs determined by their behavior and independent of exactly how the program is expressed: the property has to have the same value for any two programs ...

2

Is that proof correct? Let's assume f is computable. Then I can show a TM which solves halting problem, actually even more - a TM which prints all halting TMs of given size. This TM works as following: Using blackbox for f, calculate f(n) Iterate through ALL possible TMs of input alphabet {0, 1}, states {0, 1..., n}, work alphabet {_, 0, 1, .... n} ...

2

Consider the word $w_n$ that is the output of $M'$ given input $n$. Note that description of $w_n$ is the description of $M'$, whose length is some constant $c$, plus the description of $n$, whose length is $O(\log n)$ since we can express $n$ in the binary representation. So $K(w_n)\le c + O(\log n)$. If $n$ is large enough, we get $$K(w_n)\lt n = |w_n|.$$...

2

Your thought falls short of a rigorous proof. It can hardly be considered correct intuition since it does not use the condition that each Turing machine is labelled with some number, although it does use the condition that each $k$ corresponds to a Turing machine. Your "proof" would work equally well if the condition "$M_1,M_2$,... is an enumeration of all ...

2

Nice question. Notations and terms $M$ or $N$ means a Turing machine (TM), whose specification may or may not given. $\langle M\rangle$ is the description of $M$ according to a predefined effective encoding scheme for TMs. $L(M)$ is the language recognized by $M$, i.e., the set of words accepted by $M$. At least that is what I have seen everywhere. ...

2

Let $A$ be a randomized procedure which outputs $h_p$ with success probability larger than $1/2$. Consider the following code, with input $x$: Let $y$ be the machine corresponding to machine $x$ running on itself as input. If $A(y) = 1$, go into an infinite loop, otherwise halt. Denote this program by $B$. What happens if we run $B$ on itself? Let us ...

2

The machine $M$ is deterministic. This means that, if $M$ is in a certain configuration $c$, then there is a single fixed configuration $c'$ (determined by the rules of $M$) which the execution of one step will lead it to. If $M$ ever reaches the configuration $c$ again, then the configuration $c'$ will follow no matter what. Hence, if the computation of $M$ ...

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