38 votes
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.
D.W.'s user avatar
  • 159k
33 votes
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 ...
Jörg W Mittag's user avatar
21 votes

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.
Nathaniel's user avatar
  • 15.6k
20 votes

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 ...
DirkT's user avatar
  • 991
17 votes
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 ...
D.W.'s user avatar
  • 159k
13 votes

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, ...
Knogger's user avatar
  • 1,032
8 votes

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 ...
user160573's user avatar
8 votes
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, ...
Jean Abou Samra's user avatar
8 votes

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 ...
willeM_ Van Onsem's user avatar
8 votes
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 ...
chi's user avatar
  • 14.6k
7 votes

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.
gnasher729's user avatar
7 votes
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 ...
Kai's user avatar
  • 865
7 votes

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 ...
Josiah's user avatar
  • 199
6 votes

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 ...
bebidek's user avatar
  • 161
6 votes
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, ...
confusedcius's user avatar
5 votes
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 ...
Rémi's user avatar
  • 402
5 votes
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). ...
Gro-Tsen's user avatar
  • 393
5 votes
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'$ ...
Knogger's user avatar
  • 1,032
4 votes
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 ...
D.W.'s user avatar
  • 159k
4 votes

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 ...
Ciro Santilli OurBigBook.com's user avatar
4 votes
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 ...
Andrej Bauer's user avatar
  • 30.4k
4 votes
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$ ...
Steven's user avatar
  • 29.5k
4 votes

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 ...
DirkT's user avatar
  • 991
4 votes

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 ...
Austin Hemmelgarn's user avatar
4 votes
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 ...
DirkT's user avatar
  • 991
4 votes
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.
gnasher729's user avatar
4 votes

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.
mhum's user avatar
  • 2,092
3 votes

A Turing machine for which it is impossible to predict whether it halts or not on a fixed input

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". ...
Yuval Filmus's user avatar
3 votes

Understanding proof for Busy Beaver being uncomputable

The reference blog has changed and it seems to have been corrected which includes the OP's correction. Although the waybackmachine archived this blog old uncorrected version (2013 version) but it can'...
An5Drama's user avatar
  • 193

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