New answers tagged

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

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


0

An undecidable language is necessarily infinite. A finite subset of it is always trivially decidable.


2

Given an integer k, are there integers (positive or negative) x, y, z with an absolute value ≤ $10^{1000}$ such that $x^3 + y^3 + z^3 = k$? It is believed that without the limit on the absolute values the answer is "Yes" unless $k \equiv 4 \mod 9$ or $k \equiv 5 \mod 9$. On the other hand, solutions are so rare that most likely solutions for some values k ...


1

If you consider space and time limitation, it'll be safe to assume that almost every Decidable problem (as per the exact definition) can have version that can be computationally not solvable. That said, Turing machines are not a practical model for computing. Even in the theoretical computer science community, the more realistic RAM machines are used ...


2

The language $L$ clearly exists — you just defined it! It’s not hard to check that your language is co-r.e., that is, you can enumerate ambiguous grammars. Since it’s not recursive, it cannot be r.e.


0

A good rule of thumb is to use Church's thesis: can you personally solve the problem? While this is of course informal, in practice it works very well after you develop a bit of experience with Turing machines. (That said, ultimately the theorem you'll learn and use here is Rice's theorem.) By way of example, let's first consider the following two sets: ...


1

Definitely not. Just think about that the universal set of input is a decidable language, but there are infinite subsets of it are undecidable...


2

Suppose you've come up with a machine $P_0$ which you claim decides the halting problem. I create a $Q_0$ that makes it malfunction somehow (your $P_0$ either ends up diverging or gives the wrong answer). The proof of the Halting Problem shows that I can always create such a $Q_0$. "Aha!" you say. "But now I can create $P_1$, which is exactly like $P_0$—...


0

The answer to your question is yes. That is exactly the whole point of the Halting Problem: It is impossible to build a recognizer that correctly answers "Yes" or "No" in finite time to the question "Does P halt?" for all P. We don't need to exhibit a P for which all recognizers fail to be able to prove that it exists.


0

From Wikipedia: Let S be a set of languages that is nontrivial, meaning there exists a Turing machine that recognizes a language in S, there exists a Turing machine that recognizes a language not in S. Then it is undecidable to determine whether the language recognized by an arbitrary Turing machine lies in S. It's the language (...


Top 50 recent answers are included