h2g2 The Hitchhiker's Guide to the Galaxy: Earth Edition

There is one surefire way to distinguish between a computer and a human online. You simply give the "person" a computer program, and ask if it will ever finish, or if it will run forever.

Before I back up this claim, a little background:

Any computer can be simulated by a hypothetical machine called a UTM (Universal Turing Machine). This machine can be illustrated by another machine, Norma which can also simulate any computer.

It has been logically proved (apologies for the lack of proof here, my notes are at home) that Norma cannot solve the halting problem. As Norma can do anything that any other computer can do, it follows that no computer can solve the halting problem for all programs.

The reasoning is so certain that the lecturer that teaches the course has offered a sizable sum of money to any undergraduate who can write a program to solve the halting problem. If anyone out there happens to do it, send it to me and we'll split the cash.

CodFish II

Hello,

I don't like to disappoint you, but the halting problem
ist - in several respects - no way for distinguishing
between humans and computers.

1. if a computer cannot solve a certain problem, how
do you know that a human can? a human most
probably would give up after some time, but
a computer can be programmed to do that as well.
this argument is supported by the following:

2. it has *also* been shown that all halting problems
whose solution "only" needs finite resources
*can* in fact be decided. So machines only cannot
solve problems which humans cannot as well.

Stiller

Gee - if I could solve the halting problem, it'd be a heck of a lot easier to program....

As it is, I do what everyone else in this godforsaken industry does.... hack it.

There must be some questions that would even trip up the best programmed "bot".
For example:
"How old are you?"
This may bring two different responses:
1 (A bad program): I am 20 years old
2 (A bad program): 20.

But questions such as:
"I think Jello is a stupid way of spelling Jelly, Britain rules doesn't it?"
There are a few different questions in there and algorithms which check for words like "Doesn't" or "Think" or "Jello" would mess up the answer. There could be answers like:
1) Yes, I like Jello too
2) I don't think so either.
3) Don't call me stupid!

Until we achieve the sort of AI like that employed on Star Trek:Voyager's EMH, a human will be able to tell the difference and sooner or later, the program will trip up

I'm only 16 so my understanding of the subject is minimal, however, I hope I have raised some points that will make you think. Also, If you have QBAsic on your computer visit http://www.qbasic.com and download CHAT.BAS . It's a simple little program but if enough word were put in, it could really be quite a good thing to test.

Thank you for reading my insignificant work and I apologise for any spelling mistakes.

First question - the bot says 20, or whatever, despite the program itself only being a year old. So in some sense it lies... (actually, the bot would probably genuinely believe that it was a 20yr old male called Ed). What's the problem there?

The second question illustrates that simple algorithms are not sufficient to solve the Turing Test. In a sense that's reassuring - if it only took a two line program to solve, then I don't think many people would view it as a good test of intelligence. To solve the problem for real, you might have to...

a) parse the sentence, and build up a model of what has just been said.
b) relate that model to the model of the conversation so far, and recent sentences,
c) generate from that relation, and some creativity, a suitable reply
d) update the model of the conversation.

Even that level of complexity would probably fail - but it gives an idea...

(btw - not insignificant at all - don't put yourself down like that... )