Is There a Flaw in this Turing Test Reasoning?

[SSequence]

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?

 

[mfb]

What?

A computer program that tries to look like a human will have to react like a human: Take into account the whole previous discussion. Take some time for answers - if new text appears during that time, take that into account as well. The computer program will have to halt for every possible input, otherwise it is broken. It is easy to make sure that the program halts: If it doesn't produce an output after time X, just write nothing, or write some generic reply, or whatever. You cannot use the halting problem to figure out if there is a computer at the terminal.

You can make a list of every possible program, and test those programs one by one. But there is no upper limit on the program size, and there is a program for every possible sequence of replies, so you can never be sure.

 

[SSequence]

Perhaps there is a mistake since I do make a lot of mistakes. But anyway, I will try to address the points you have raised.

What?
A computer program that tries to look like a human will have to react like a human: Take into account the whole previous discussion. Take some time for answers - if new text appears during that time, take that into account as well.

I understand that, generally speaking, the computer on terminal B can't do elementary stuff superhuman fast. But the idea I had in mind didn't use much of that point at all.

I tried to describe three different cases. First case only the last response is taken as input. Second case only the replies posed by the person/program on terminal A are taken as input (in order and appended). The third case the whole discussion is taken into account (in order and appended as a whole -- obviously keeping track which replies were from terminal A and which ones were from terminal B). I just took that model as a reasonably interesting one to think about.

You mean to say that if new text appears during a conversation, in the third case, the current computation stops and the input is updated? This is not something I mentioned or thought about explicitly while writing the first post. But looking at example I posted for Case 3:
"(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.
..."

If the current computation wasn't being stopped/reset each time the "conversation string" got updated then the response corresponding to the lines (A1.1) and (A1.2) wouldn't have come from the program on terminal B. Instead the first response would have been the line (A1.3)

The computer program will have to halt for every possible input, otherwise it is broken. It is easy to make sure that the program halts: If it doesn't produce an output after time X, just write nothing, or write some generic reply, or whatever.

Sorry I am not getting the first sentence at all. Perhaps it depends on specific model?***
More specifically, for the model I described for Case-3 above where the whole "conversation string" is the input (and is updated everytime user on terminal A writes something) I don't understand why this should hold true. Is there a glaring issue with that model then (like Case-1 for example) -- and what is it if there is one?

I think I get the second sentence though. You are saying that the person on terminal A obviously keeps talking/writing and the program on terminal B just doesn't respond at all then obviously something is wrong? For example, if person on terminal A wrote a billion replies (and also within span of very very large time spread) and didn't get a single answer at all then he should assume that on terminal B there is a program? That should be true I guess. One would probably reasonably set up a very very high point where no response means that there is a program on terminal B.

You cannot use the halting problem to figure out if there is a computer at the terminal.

I didn't use halting problem anywhere. Only a counter-program that has some similarity to one used in hp proof.

You can make a list of every possible program, and test those programs one by one. But there is no upper limit on the program size, and there is a program for every possible sequence of replies, so you can never be sure.

That means that each time if one was to list out the steps of all programs (obviously at a given time only a finite number of programs will be "open" so to speak) and those that were not compliant with current history, rule them out? That would always leave infinite number of possibly valid candidates at each finite time? That should be certainly true.

*** EDIT: OK I think I am getting the basic point. You are probably thinking about it in some sort of reasonable sequential sense whereas I was thinking of the program in a more classical/mathematical sense (the input is given and the program evaluates output).

 

[mfb]

Can you summarize what you want to show/discuss in a single paragraph? It is hard to see the bigger picture if you directly start with details everywhere.

 

[SSequence]

terminal A -- Person
terminal B -- Person/Computer Program

First I should summarise the computational model C that I was thinking about:
Returns a "function" from A* (kleene closure) to A* where the set A has all the usual alphabet 0-9, a-z, A-Z etc. The model of conversation used goes like this. The basic unit of conversation is a sentence (which can be sent as a unit from one terminal to other). Furthermore there is never any error in data being sent as sentences ("Hi" being changed "Ha" etc.).

The program (on terminal B) stores the "whole conversation string" and uses it as input. The program starts evaluating the output from the input. And it "moves on" under two conditions:
a) It successfully calculates the output before there is interruption from the user. In that case it "sends" the output string to the user (as a sentence), updates its "conversation string" and starts computing again with new input.
b) If there is interruption from user while calculation (the user "sends" a sentence), the program "updates" its "conversation string" and starts calculating again from scratch with new input.

I also assumed (to make things as clear and transparent as possible) that the user also knows what "conversation string" is being used by the program (if there is one on terminal B) as input -- and that the program is deterministic. Furthermore I haven't thought much about relation of this model with sequential model.
I haven't yet thought if there is or isn't a substantial impact of changing these assumptions (in some cases some modifications would definitely be needed).

Now coming to the argument:
You do the following things first (and take as much time as necessary):
(a) Explain the specific computation model C (that calculates a function from strings to strings) to the program on terminal B.
(b) You tell the program on terminal B that they will be asked a question about some program CP (and also how CP will generally be constructed in completely uniform and trivial manner from some program P).
(c) You also tell the person/program on terminal B that the program P (of computational model C) will definitely halt after a finite number of steps (on the input that will be specified). So no matter how long it takes terminal B you should just keep simulating the program you will be given -- eventually it will halt.
(d) When it is very clear that the person/program on terminal B has understood what you have told them you tell them to:
(i) Be quiet (and wait for the next question no matter how long it takes)
(ii) Tell terminal B that it must give an exact response to the next question in terms of either "Yes" or "No". There must not be any other answer. Also don't give the answer too late (re-check your values again and again but still don't waste too much time perhaps).

Note that if the program on terminal B violates d(i) or d(ii) astronomical number of times then you can only assume that terminal B has a program operating it (because the person on terminal B was supposed to be trying to show you that he isn't a program).

After that you ask the question: "Up till all the conversation that has gone until now (including this very question) must be included as part of "conversation string" (and taken as input). The question is that does the program CP (of computation model C) halt?"

Now when terminal B has gone quiet. You take all the conversation string (including the very last question you just posted as sentence). Note that "CP" in the last sentence is actually going to be a long string (which we actually need to decide yet). You start simulating all program (only limited number of programs included at a given finite time) of computational model C step by step on the given input (the input will vary with each program because presence of "CP" but it will be calculable for any given program P). Some program P will halt.
(even after this question perhaps continue this to see which programs halt and keep adding them to your "List").

Now since terminal A is the one who posed the question. Suppose program P that halted was of length 100 for an input of size 200 and stopped after 100 steps etc. Give the terminal B 200 trillion years to resolve the answer. If terminal B gives:
a) a wrong answer
b) no answer by the time of the limit

In that case you conclude the verification of the following statement:
p: on the other side of the text terminal B is a computer program

If the answer is correct and within the time limit then you move on repeat the process again (making sure you now exclude those programs from the "List" whose conversation history doesn't match with the current program -- keep adding more and more programs to the "List" and make sure that every program that enters the "List" and doesn't leave based on conflict in "conversation history" will eventually be included in the questioning).

 

[SSequence]

If the answer is correct and within the time limit then you move on repeat the process again (making sure you now exclude those programs from the "List" whose conversation history doesn't match with the current program -- keep adding more and more programs to the "List" and make sure that every program that enters the "List" and doesn't leave based on conflict in "conversation history" will eventually be included in the questioning).

It seems that I casually put aside some difficult issues here :P.

EDIT:
OK I should explain the basic sense of why it won't work I think. Basically with each new question you are removing a possibility that the program isn't some specific one (say when you pose the n-th question program Pn is removed from the set of possibilities). Essentially if you take the basic idea to the bare bones, it seems that this won't work for the same reason that simple diagonalisation patterns (with a number of variations) don't work on partial recursive functions. At each stage even though a program Pn is removed (from the set of possibilities) there is no guarantee that some given program (with some specific property such as totality) will be included in that removal list at any time.

The main problem for this specific method lies in the selection of program chosen for which the question is to be posed at each stage.

Of course if one already knows the index of program on the terminal B it is very easy to pose a question for which the program gives a wrong answer (assuming it gives some answer). But that's a trivial point really.

EDIT:
Removed the speed bounding part. Actually what I wrote might work or might not. I didn't think it through that thoroughly. I will think about it and if it makes a lot of sense I will post again regarding the method in previous posts, otherwise I won't.

What I had in mind was one further assumption to the method in previous posts --- if you could recursively bound (in a strict sense) the total number of instructions (say in computational model C) that program on terminal B could perform in a unit time (starting from time 0). It would be assumed that the particular recursive function is known to person on terminal A.

 

[PeterDonis]

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).

You're assuming that the categories "person" and "computer program" are mutually exclusive. What if they're not?

 

[SSequence]

Well first of all as you can see the basic thought that I had when I thought about conversation (through a text terminal) a month ago was that whether the failure of diagonalisation (in a number of variations) that occurs in partial recursive functions transfers to a text conversation (between two terminals). My vague sense was (without much thinking in detail) that "perhaps" this failure could be avoided in the text conversation (possibly due to some kind of arbitrariness).

But after thinking about it in the last few days (as you can see from the walls of text) in some detail, it seems that seemingly the same failure of diagonalisation does occur in a text conversation too.

In both cases the idea was to seek an algorithm like process to do the work.

You're assuming that the categories "person" and "computer program" are mutually exclusive. What if they're not?

I didn't actually make the thread to discuss this direction. But if you want to discuss this in detail sure go ahead (not sure what I would add except my own points though).

To be fair, I do feel a bit disappointed in making lengthy posts and seeing that I made a mistake in my reasoning (that kind of disappointment is natural for a short while though). I might as well talk about something else.

Now there are many reasons. First of all even if there was no functional reason (in a principle sense) at all to think they aren't entirely different categories, I would still consider them entirely different categories anyway. I believe that there is never any point to creating an unnecessary confusion (in a philosophical sense that is).

Secondly they are different categories (and there is no doubt about it). My reasons are entirely mathematical/philosophical. First of all a few principle points that form the necessary idealisation:
-- Time is not important.
-- Potentiality is important (not what someone has achieved but what they can achieve if they have (or are told/given a hint) the right idea how).
-- Somewhat related to above point, mental issues related to intelligence are also irrelevant because they are related to the physical universe and have no specific relation to sentience of mind.
-- Rigour is secondary, it is sense and patterns that are primary. Rigour generalises sense afterwards.
-- Think of a plane and drawing a circle of some radius (with centre at the origin). A more talented person draws a bigger circle (bigger leaps of reason). A less talented person will draw many smaller circles increasing gradually in size (smaller and more easily understandable leaps of reason) and eventually creating a bigger circle than the one drawn by more talented person. In this particular sense then, being more talented isn't necessarily that important because the gain is of time mainly (and from the first point, time is not important in a principle sense). Perseverance is very important though.
-- Learning is important. One could learn the most complex number theoretic proofs possible if someone taught all the details as patiently and with as much clarity as possible.

Now these points might look too abstract, but in my opinion, all these points are essential. Now coming to my main points:
a) I don't think that I could prove any arbitrarily difficult number theoretic statement at all, no matter how much time I had -- I simply wouldn't be able to do it at all. So, in that sense, I consider those kind of statements simply beyond my potentiality entirely, but within the range of learning.
b) Non-determinism is important (I am talking about mathematical sense here).
c) Human mind is recursive in a fundamental sense.

This is all I have to say on this topic. Sure some points might need further explanations but as far as all the basic points related to this topic, there isn't much else I can think of.

P.S.
If this sounds far too abstract, its understandable. I didn't create this thread for this topic but since you mentioned this point, I thought I would put all the points I have in mind in an abridged format.

 

[PeterDonis]

I didn't actually make the thread to discuss this direction.

If the categories "person" and "computer program" are not mutually exclusive, this whole thread is a waste of time because you started with a false premise. So whether you wanted to discuss it or not, it certainly seems like an important point.

The rest of your post, to the extent I can make sense of it at all, gives no argument that I can see for why "persons" cannot be computer programs (much more complicated ones than any humans can write today) running on the hardware of brains. You basically just believe that can't be the case, so you refuse to consider the possibility. IMO that is the flaw in your reasoning.

 

[PeterDonis]

This thread appears to be going nowhere and is therefore closed.