I had some time to think about this problem towards the end of last year. I don't think that the idea presented is novel by any means (either the problem or the points discussed here). I think the problem is called the turing test in a somewhat generic sense (but I am not aware whether assumption of infinite time available is made in that case or not -- which has been made here). At any rate, I will discuss, in some detail at least, the context of the specific problem and the various assumptions that have been made in problem statement. I have tried to describe most of them clearly. The basic idea (in idealised sense at least) is very simple. A simple communication (through a text terminal) between a person and potentially either a person or a computer program. One side of terminal (terminal A): person Other side of terminal (terminal B): either a person or a computer program Note that this is part of the assumption that on the other side either there is a person or a computer program (to keep things as simple as possible). Also to keep things as simple (and clear) as possible, it is also assumed that the person on terminal A knows exactly which input strings move to terminal B as input (in case there is a program on terminal B). Now consider the following statements: p: on the other side of the text terminal is a computer program ~p: on the other side of the text terminal is a person What we want is a simple "nearly" mechanisable test (reason for word nearly will be discussed) to verify the statement p (or alternatively falsify the statement ~p). Now a certain degree of mathematical idealisation is assumed. It is assumed that person writing on terminal A can, or is willing to, perform basic clerical tasks and similarly for person (if there is one) on terminal B. If these assumptions aren't true then the mathematical idealisation clearly doesn't hold (and one might look at other fields of science in that case). An infinite time is assumed to be available to person on the terminal A. He has to simply eventually give one answer or the other after taking as much time as he wishes to. It is also assumed that if on terminal B we have a person, he is not trying to act as a computer program (but trying to show the opposite). The first half of the post are few notes (which I am more or less copying exactly) I made regarding this issue (when I was thinking about this topic). The notes are somewhat brief and I didn't write down a lot of details: Communication: (1.1) ----- (person) (A1.1) ----- (computer program) (2.1) ----- (person) (A2.1) ----- (computer program) (3.1) ----- (A3.1) ----- (4.1) ----- (A4.1) ----- ....... Fixing the Context: The program takes an input string and gives an output string. In other words, the program simply calculates the function f:S-->S over some suitably chosen finite alphabet. But here we need to decide what exactly should be taken as input. Case-1 Whatever the person just wrote as the last response, take that as input. But this is clearly a very unsatisfactory idealisation. For example, here are many silly conversations as a result of that: (1.1) What is your name? (A1.1) A2B2 (2.1) What was the last question? (A2.1) I don't remember. (3.1) What was the last question? (A3.1) I don't remember. (4.1) What was the last question? (A4.1) I don't remember. (5.1) Just look it up from the text interface. (A5.1) huh? ...... (1.1) What is your name? (A1.1) A2B2 (2.1) What was the last question? (A2.1) What was the last question? (3.1) What was the last question? (A3.1) What was the last question? ...... (1.1) What was the last question? (A1.1) There was no last question. (2.1) What is your name? (A2.1) A2B2 (3.1) What was the last question? (A3.1) There was no last question. ...... Case-2 A much better and more reasonable idea when constructing a response is to take as input all the questions that have that have been asked by person A till now: (1.1) What is your name? (A1.1) A2B2 (2.1) What was the last question? (A2.1) What is your name? ...... After the first question has been asked the input to computer program on the terminal B is: "(1.1) What is your name?" After the second question has been asked the input to the computer program is: "(1.1) What is your name? (2.1) What was the last question?" The conversation can also go like: (1.1) What is your name? (A1.1) A2B2 (2.1) Do you go to school? (A2.1) Not really, because I am a robot, I can't learn anything new. (A2.2) I don't have a replacement chip either. (A2.3) A little disappointing, isn't it? (3.1) Yeah, maybe. (3.2) Hello are you there? (A3.1) Sorry, I was afk. (4.1) abcdabcdabcd (A4.1) I don't understand what you mean. (A4.2) Can you repeat? ...... The inputs after various questions will be: "(1.1) What is your name?" "(1.1) What is your name? (2.1) Do you go to school?" "(1.1) What is your name? (2.1) Do you go to school? (3.1) Yeah, maybe." "(1.1) What is your name? (2.1) Do you go to school? (3.1) Yeah, maybe. (3.2) Hello are you there?" "(1.1) What is your name? (2.1) Do you go to school? (3.1) Yeah, maybe. (3.2) Hello are you there? (4.1) abcdabcdabcd" One thing that's perhaps missing in Case-2 is if the user asks questions too fast. In this case, either the program overwrites the input and starts computation again or it doesn't overwrite the answer (and simply adds inputs in succession). For example (over-writing case): (1.1) What is your name? (1.2) Do you go to school? (1.3) abcdabcdabcd (A1.1) Sorry I didn't understand you at all. example (without any over-writing) (1.1) What is your name? (1.2) Do you go to school? (1.3) abcdabcdabcd (A1.1) A2B2 (A1.2) No. (A1.3) I didn't understand your question. Case-3 Take all the conversation (not just the questions) as sentences up till now as input. (1.1) What is your name? (1.2) Do you go to school? (1.3) abcdabcdabcd (A1.1) Sorry you are going too fast. (A1.2) Let me respond one by one more slowly. (A1.3) For 1.1: A2B2 (A1.4) For 1.2: No (A1.5) For 1.3: I don't understand what you mean. ...... Now we will carry on assuming Case-3 here. Consider the following problem now: terminal A -- Person terminal B -- Computer Program Well what can one do in that case? We do the following for each program P with specific property (known to halt on certain inputs). First you explain some specific computation model C (that calculates a function from strings to strings) to the program on terminal B. After you have done that, take some time and construct the "counter program" to the program P and call it CP. Whenever P's output answer gives a "Yes" (as a sentence) or any "other" string to any input, CP loops forever (in the most trivial manner), and whenever P answers "No" (as a sentence) to any input CP halts immediately. Now suppose you have explained all the specifics of computation model C to the program on terminal B. And the current string for conversation is s. On the other terminal B, we have a person we have already communicated with them that to all questions of the form described below they are told in advance that the program P will always halt for given input (and also how CP will generally be constructed in completely uniform and transparent manner from P in all such questions). They are also told that their very next answer must be of the form "Yes" or "No" sentence (which they only make after evaluating all the steps of program P by themselves and then making judgement about CP).If terminal B doesn't respond after several trillions of years for a very small program calculation (with say less than 100 steps and few variables) then we can see that on the terminal B we have a program. Furthermore because you know how big program P is and the input string corresponding to number x you give the program on terminal B the time to determine it that is safely much much larger (for example, a trillion years for each step for a program P with 500 length and 100 variables etc. -- also have to account for a few trillion years for conversions between encoded numbers and strings). Now you ask the following question: "Does the program CP halt on input encoded as number x?" Here x is a string representation of a number. The set of strings must be encoded (as a number) in such a way such that for any arbitrary strings s and S there must exist some number b such that the string: s+"Does the program S halt on input encoded as number b?" has the number equal to b assigned to it (note that in above question b is string representation of the actual number). Does there exist such an effective correspondence function between set of strings over some alphabet and numbers? It should exist because if we think of numbers such as 1, 2, 3, 10 etc. and their corresponding string representations "1", "2", "3", "10" there seems to be a lot of space to make such assignments (for example, for some string s s+"100" is assigned the number 100, for another string t t+"150" is assigned the number 150 etc.). This correspondence also needs to be communicated (for example, through a precise correspondence program from N to set of strings). What if the program on terminal B just doesn't stop writing by itself? Well maybe one can ask it to stop writing until prompted to talk. In each case when terminal B successfully answers a question within the time limit, you manually (or mechanise that part?) look for the next program P (from which CP will be constructed) about which you want to ask the question (and continue in this manner) -- and importantly also determine the right input. I think one could also communicate the number of halt steps (or perhaps even the time limit) in advance to terminal B but probably with more burden on encoding? There could also be fair amount of variations I suppose (varying with underlying assumptions)? I know the explanation is much more sketchy than I would have liked it to be (but much of the later half of the post I thought over yesterday). At any rate, this is probably more fun as a casual discussion topic. Can someone explain the flaw in this reasoning?