New answers tagged

0

Couldn't we say "a tape of indeterminately many cells," or "an indeterminately long finite tape"? I know it's wordier, but it might be clearer?


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.


0

Not all computing machines use temporal pulsing. Turing machines don't. What is more, not all computing machines perform all steps in order: asynchronous circuits don't. Distributed systems don't. I believe the author is mixing up computing as a discrete (stepwise) process strictly sequential computing, in which no steps are executed concurrently clock-...


2

There are various models of analog computation, which embody computations which neither involve discrete states nor times. One of the more studied models is what might be called "Shannon machines" (after Claude Shannon): the General Purpose Analog Computer (GPAC). Shannon's original formulation of GPAC could not compute certain functions, including the ...


2

An algorithm may be infallible. Any physical computer can make an error e.g. if it is hit by a stray cosmic ray, a bolt of lightning or a large axe.


-1

The concept of sequentially performing one step after another seems to be inherent in our intuitive understanding of what constitutes an "algorithm", so it is present in one form or another in all useful models of digital computing. Even in a non-deterministic Turing machine, which can make multiple copies of itself at each step, each individual copy still ...


0

Putting similar arguments as above answers in a slightly different way : All context free languages can be decidable by a Halting Turing Machine. (Those would be a piece of cake for the Machine). Now even if we complement such a language, Halting TM can still decide whether it is accepted or not. The Complement of CFL still lies under the power of Halting ...


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

Your reduction actually shows that $L_m$ is not co-RE. Indeed, if $L_m$ were co-RE, then your reduction shows that $L_u$ is also co-RE. However, $L_u$ is known to be RE but not recursive, hence cannot be co-RE. Similarly, you can show that $L_m$ is not RE, by reduction from the complement of the halting problem: given an instance $(M,w)$ of $L_u$, create a ...


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


2

If a language is decided by some nondeterministic Turing machine, then it is decided by some deterministic Turing machine. However, not every behavior of a nondeterministic Turing machine can be replicated deterministically, as your example demonstrates.


1

If $L_1,L_2$ are two languages over a common alphabet, then their concatenation is given by $$ L_1 L_2 = \{ x_1 x_2 : x_1 \in L_1 \text{ and } x_2 \in L_2 \}. $$ If $L_1,L_2$ are r.e. then so is their concatenation. To see this, you can use the following algorithm. Given an input $x$, consider all possible partitions $x = x_1x_2$. For each partition, run a ...


2

If you have $g$ symbols (including a blank) and a tape of size $n$ then there are $g^n$ words of length $n$. This is really basic combinatorics: The reasoning is that you have $g$ options for the first symbol, $g$ options for the second symbol, i.e. $g^2$ options for the first two symbols. Then again $g$ options for the third symbol, giving you $g^3$ options ...


2

EDIT: I made a deeply silly mistake in my previous answer. Below what I've done is answered the question, then explained how two variations of the question - which I originally conflated with the actual question - yield a very different answer. An oracle of the type you describe computes the halting problem (and conversely every oracle computing the halting ...


Top 50 recent answers are included