Why we probably won’t have sentient computers

This is actually going to be a very Computer Sciency post. I will try to explain the basic Computer Science principles I learned in college as clearly as I can, but if you are reading this and did not understand something, please leave a comment and I will try and explain it better.

There has been a lot of debate about why Artificial Intelligence is bad because (insert any ‘Matrix’ type of apocalypse here). Do we have reasons to believe that sentience or consciousness is actually more than Turing Complete?

Let us take the Problem of  Undecidability of  Turing Machines ( I don’t remember exactly what it was called). This is a wonderful problem which was proved by Alan Turing that a solution does not exist. The Problem of  Undecidability of  Turing Machine states that it is impossible for a Turing Machine to state that whether or not another Turing Machine will produce a particular output or not. Please keep in mind that a Turing Machine is a computer (or more precisely a computer program). How is this? Modern day computers (i.e hardware) are usually general purpose. This means that modern computers are designed in a way to allow any Turing Machine to be built out of them using software. When the hardware and software combine together a Turing Machine is born. This is a machine that is actually capable of information processing (computing). Any machine capable of information processing is usually called a computer. The reason we use a general purpose hardware and special purpose software is basically cost and manageability. It would be theoretically possible to build a hardware that can let you play Need For Speed. But the complexity and cost of such a machine would be huge. The advantage of doing things this way is that the hardware only needs to be researched once and then sold in billions of units. Thus the research cost for general purpose computers are less per unit(which is why some scientists are making super computers using PlayStation 3 rather than building the entire thing from scratch. Companies like Google, Facebook etc also favors cheap commodity hardware for this reason [and many other]).

The proof for the Problem of Undecidability of  Turing Machines is a proof by contradiction. It goes like this :

(Please keep in mind that when I refer to Turing Machines, I essentially mean software programs)


Suppose there is a Turing Machine H1 which can take Turing Machine H2 and an input for H2 ( say ) as input and produce an output (by printing onto the screen) “Yes” or “No” depending on whether or not H2 gives a particular output (say it prints “Hello World”) when given the input I.

i.e

Program H1 :

Read inputs H2 and I

if( H2 with input I produces output ‘Hello World’)

print “Yes”

else

print “No”

Now, let us modify H1 to print ‘Yes’ if H2 prints “Hello World” and prints ‘Hello World’ if H2 does not print ‘Hello World’ on input I.

Hence final (hypothetical) code of H1 is :

Read inputs H2 and I

if( H2 with input I produces output ‘Hello World’)

print “Yes”

else

print “Hello world”

Now let us make a new machine H3 such that H3 only takes H2 as input and simulates H1 with both inputs as H2, i.e it makes a copy of H2 and gives it as the two inputs for H1.

Program H3 is :

Read input H2

Illustration of stated Turing Machines
Final states of the Turing Machines H1 and H3

Simulate H1 and pass as inputs H2 and H2[ i.e a function call : H1(H2,H2) ]

Now, comes the twist : let us feed H3 as input to H3. What output should come from H3 (simulated H1)?

If it prints “Yes” that means that H1 is saying that when H3 is given as input to itself it should print ‘Hello World’. but that is exactly what we did [give H3 as input to itself] and it printed “Yes”, not ‘Hello World’. If it prints ‘Hello World’ that means that we just gave H3 as input to H3 and it printed ‘Hello World’, which means that H1 should have given us the output “Yes”. Hence in both cases we see a fallacy. Hence we say that all these machines cannot exist.

Hence we see that it is impossible for a Turing Machine to say whether or not a particular program produces a particular output (which is why software testing can never be completely automated. Ever) . But it is my feeling that if given a long enough time span, human beings can do that (this is unsubstantiated, I know, but I feel that way). If the program length is like a billion lines, it might be impossible for a human being to decipher it all in a lifetime and hence my hypothesis might be too hard to prove. But I seriously think that given enough time our brain can make a statement on whether or not a program will produce a particular output. Thus we are somehow different from computers (Turing Machines) and we will always be.

Three things:

1. Please do not think that this somehow implies there is a God or something. This might just mean that we are Turing Machines + some more capabilities, just as Turing Machines are PushDown Automata with some more extra sugar. But this also leads to interesting conclusions like if we assume every physical or chemical reaction in the world can be simulated on a computer, consciousness is not a sum total of some physical, chemical or electromagnetic reactions in the brain.

2. This also means that I do not believe a human brain can be completely ever simulated in a computer because if it can be, the underlying machine will break free of the limitations of the Turing Machine (unless of course someone can prove that human brain cannot say whether a particular program will produce a particular output or not).

3. Thanks to John E. Hopcroft, Rajeev Motwani and Jeffrey D. Ullman for their book  ” Introduction to Automata Theory, Languages and Computation“.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s