# Tag Info

Accepted

### Does the Turing test have anything to do with Turing completeness or Turing machines?

No, there is no relationship. The connection is that they are both based on concepts/work by Alan Turing, who was an early pioneer who made many advances.
• 159k
Accepted

### Can we ever achieve Turing completeness?

As far as I know we say something is turing complete (eg: a programming language) when it can compute any function and can do any task. No. A model of computation is Turing-complete if it can compute ...
• 6,140

### If the set of Turing machines is countably infinite, how can a Turing machine always have a finite set of states?

If the set of integers is infinite, how can any integer be finite? If the set of words of $\{0,1\}^*$ is infinite, how can any word be finite? You get the idea.
• 15.6k

### David Deutsch says "number of atoms in universe is finite", but then says "number of programs of all finite lengths is infinite". Contradiction?

A good analogy would be the integers: There is an infinite amount of finite integers. We can prove that by contradiction: Let's say there was a largest finite integer $i$, then $(i+1)$ would be even ...
• 991
Accepted

### Is a machine Turing-complete when it can decide a context-sensitive language?

No. Context-sensitive languages can be recognized by linear-time nondeterministic Turing machines, which are not Turing complete. The ability to recognize a recursively enumerable set also does not ...
• 159k

### If the set of Turing machines is countably infinite, how can a Turing machine always have a finite set of states?

Maybe consider a simpler example. All Strings over the alphabet $\Sigma = \{0, 1\}$ have finite length, but there are an infinite number of strings over $\Sigma$. The reason for this is simple, ...
• 1,032

### Does the Turing test have anything to do with Turing completeness or Turing machines?

The relationship exists. All of these were invented by Alan Turing. Alan Turing is the godfather of computer science who laid the solid foundations long before the first electronic computer has even ...
Accepted

### Is the Turing machine the only framework to analyse limits of computation?

Turing machines are far from being the only model of computation considered by computer scientists. Among well-studied models of computation are: Turing machines, λ-calculus (and its many variants, ...

### If the set of Turing machines is countably infinite, how can a Turing machine always have a finite set of states?

Each individual Turing machine has a finite fixed number of states. But not every two Turing machines have the same number of states. There are Turing machines with one state, there are Turing ...
Accepted

### If the set of Turing machines is countably infinite, how can a Turing machine always have a finite set of states?

You are mentally reversing two logical quantifiers, that are implicit in the statement "Turing machines must always have a finite set of states". You read this sentence as "there exists ...
• 14.6k

### Is ChatGPT wrong about the definition of unrecognizable and undecidable languages?

ChatGPT is not capable of being “right” or “wrong” about anything. It is however capable of producing very plausible sounding nonsense about just any subject. Never trust anything it says.
• 30k
Accepted

### Are 2 independent PDAs equivalent to a turing machine?

No, such a construct can recognise at most the intersection of two context-free languages. To see where it's lacking, consider $L = \{\textsf{a}^n~|~n\in\mathbb{N}~\text{is composite}\}$. I conjecture ...
• 865

### David Deutsch says "number of atoms in universe is finite", but then says "number of programs of all finite lengths is infinite". Contradiction?

The key distinction here is that a program is a concept. A concept is distinct from the place that concept is represented or stored. You can have the same program represented by different physical ...
• 199

### Are 2 independent PDAs equivalent to a turing machine?

What you actually ask is: can language of every grammar be represented as an intersection of two context-free languages? The answer is no. To prove that, we can observe that, while the class of ...
• 161
Accepted

### Can the minimisation operation be seen from a programming language perspective?

Is there a similar way in which the minimisation operation can be understood? More specifically, does minimisation correspond to some kind of "loop" found in programming languages? Yes, ...
• 246
Accepted

### Deciding whether a Turing machine decides a language $L$ in at most $n^2$ steps

This problem is indeed undecidable, assuming that $n$ is not a constant but refers to the length of the machine's input. Consider the problem $P$ of, given a Turing machine $\mathcal{M}$, to decide if ...
• 402
Accepted

### Turing degree of some functions related to Rice's theorem

Just to clarify the question, you are demanding that $f$ be total, i.e. that $f(M)$ terminate in all cases, even if $M$ does not terminate (otherwise we can simply run $M$ and return its output). ...
• 393
Accepted

### Is the language L = {<M> | There exists an M' that stops on the same input words, but L(M) ≠ L(M')} in RE or R?

Notice, that all machines $M$ that don't halt on any input accept the same language, $\emptyset$. Thus if $M$ doesn't halt on any input then also $\langle M \rangle \notin L$. Now define the TM $M'$ ...
• 1,032
Accepted

### Constructing equivalent (to a polynomial-time degree) decision problems from function problems

Special case: computing a (single-valued) function In the special case where the relation $R$ corresponds to a (single-valued) function, call it $g$, then yes, there is an equivalence. Suppose the ...
• 159k

### Compiler that compiles to a Turing machine?

Laconic This is the highest profile attempt I've heard of so far. It was announced on this paper by Adam Yedidia and Scott Aaronson: https://www.scottaaronson.com/busybeaver.pdf and on this blog post ...
Accepted

### What is lambda caculus's "fix point combinators" corresponding to Turing Machine?

The lambda calculus is not "equal" to Turing machines. There is a correspondence, but it is not equality, it's one of simulation. You should not expect every aspect of one to have a ...
• 30.4k
Accepted

### How to prove that the subset of a language L that is in P is also in P?

You cannot show that, since the claim is false. Let $L = \Sigma^*$ and let $L_A \subset \Sigma^*$ be the language of the halting problem. Clearly $L \in \mathsf{P}$ (a Turing machine that decides $L$ ...
• 29.5k

### Can we ever achieve Turing completeness?

Disclaimer: Please double check everything in this answer, because I am no expert on the topic. The Halting problem is not a necessary condition for Turing completeness. On the contrary: the Turing ...
• 991

### David Deutsch says "number of atoms in universe is finite", but then says "number of programs of all finite lengths is infinite". Contradiction?

Because the number of possible lengths is infinite. Consider the set of all possible sequences of the 26 upper case letters of the English alphabet, for all possible lengths of such a sequence. The ...
Accepted

### How far out can one determine a program is halting?

What you are describing is indistinguishable from: making a (free) copy of the Turing machine (in its current state) running it for $n$ steps seeing if it halted. I fail to see how this gives you ...
• 991
Accepted

### Is the function $f: \mathbb{N} \rightarrow \mathbb{N}$ where $f(n) = 2^n$ computable in polynomial time using TM?

Look at the size of the required output. How much time would it take you just to write the result? And this has nothing to do whatsoever with P vs NP, or computable or decidable languages.
• 30k

### What is the name of the theory that says that Turing equivalence is universal, and Turing machines are maximally computationally powerful?

I believe that the questioner is inquiring about the Church-Turing thesis.
• 2,092
For any specific machine $M_0$ and input $w_0$, there is a machine that decides whether $M_0$ halts on $w_0$. Indeed, one of the following machines works: The machine that outputs "Yes". ...