17
$\begingroup$

I am studying Turing machines and Turing completeness and just remembered I saw something called the Turing test. It seems that the Turing test (from Wikipedia)

is a test of a machine's ability to exhibit intelligent behavior equivalent to, or indistinguishable from, that of a human.

while Turing completeness and Turing machine are discussed in the context of the theory of computation. Is there a relationship between Turing complete and the Turing test?

I think they are completely separate topics, but I just want to be sure.

$\endgroup$
2
  • 2
    $\begingroup$ Nice to see I wasn't the only with this confusion $\endgroup$ May 14, 2023 at 15:49
  • 5
    $\begingroup$ @HangChen nobody has ever asked it before because you can just google the three things and see what they are. it's also pretty obvious that they're named after the same guy. $\endgroup$
    – Jason C
    May 15, 2023 at 3:12

3 Answers 3

38
$\begingroup$

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.

$\endgroup$
8
  • 14
    $\begingroup$ That should read: "Yes, they were all invented by Alan Turing. But that's about it." ;-) $\endgroup$ May 14, 2023 at 21:49
  • 5
    $\begingroup$ It's kinda like how a lot is named after Euler in math. $\endgroup$
    – ikegami
    May 15, 2023 at 2:06
  • 1
    $\begingroup$ Not to stir up anything and this is just me imagining the possibility. But wouldn't it be interesting if somehow, we will learn from some previously unknown source, that Turing actually have an idea how to relate his machine and his test for machine intelligence. Say for example, could it be that he imagined his Universal Turing machine to have on its tape some machine $M$ that will be used to simulate the Turing test and each time $M$ fails, the universal machine alters $M$, until it eventually pass this test. $\endgroup$
    – Russel
    May 15, 2023 at 3:21
  • 1
    $\begingroup$ @Russel They're only related in the sense that the Turing test is formulated to convince humans that Turing Machines can "think" in the layman sense of the word instead of in the sense of being able to process algorithms or calculate arithmetic results $\endgroup$
    – slebetman
    May 15, 2023 at 6:39
  • 3
    $\begingroup$ @ikegami Inevitable xkcd reference: xkcd.com/2721 $\endgroup$
    – IMSoP
    May 15, 2023 at 10:22
8
$\begingroup$

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 been built. Naming these after him is giving the deserved respect for him, especially since all of these were actually invented by him. His name, again, was Alan Turing.

$\endgroup$
-3
$\begingroup$

Negative. They have nothing to do with each other. The Turing test is a tool to assess a machine's ability to display intelligent behavior indistinguishable from that of a human.

There is nothing in the definition saying that the mentioned machine has to be a Turing machine, or that it has to be Turing complete. Nothing, even though any machine implementing an AI algorithm advanced enough to be reasonably expected to pass the Turing test would certainly have to be Turing complete.

All Turing machines are, by definition, Turing complete. All Turing completeness means is the ability to simulate a Turing machine. So, as you see, there isn't any relationship between them at all. Absolutely none whatsoever.

$\endgroup$
9
  • $\begingroup$ For the record, this is sarcastic. The acceρted post is bogus and low-effort superficial remark that should have been, at most, a comment. $\endgroup$
    – user160618
    May 16, 2023 at 12:40
  • $\begingroup$ I guess being a moderator puts you above the rules and allows you to farm hundreds of points by posting drive-by throwaway stubs and have people vote them up based solely on face value of the moderator badge icon. Sad! $\endgroup$
    – user160618
    May 16, 2023 at 12:41
  • $\begingroup$ Imagine a vast lookup table with a response for every possible statement in every possible context. This could pass the Turing test without being Turing complete. Also, not all Turing machines are Turing complete. Turing completeness means being able to simulate every Turing machine. $\endgroup$
    – Draconis
    May 16, 2023 at 17:16
  • $\begingroup$ In other words, this answer is simply wrong. $\endgroup$
    – Draconis
    May 16, 2023 at 17:16
  • 2
    $\begingroup$ I did not downvote, but the claim that in order to pass the Turing test, the machine has to be at least Turing complete is not at all that trivial. In fact context-free or context-sensitive grammars are not Turing complete, but can go a long way. $\endgroup$ May 16, 2023 at 20:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.