Reading Philosophy

This is a topic near to my heart. Through my studies of computer science, I particularly enjoy the theory behind it. How deep can you walk into a forest? Half-way, because the rest of the way is spent walking out of the forest. Pushing towards theory enough, and you begin to leave computer science and hit the realm of philosophy. Yes, that's right. Many of the topics that I find myself most interested in involve AI, or Artificial Intelligence. I thought I'd begin with that background information on me.

In one of my classes, the theory talked about various machines. By machines, I mean strictly abstract. For example, being in state A receiving input 0 will take you to state B. Machines that can be simulated by a pencil and paper.

One of these machines is called a Turing Machine. Perhaps some of you have heard of it. It is one of the more famous machines. The way it works is irrelevant for the discussion. What it is capable of, however, is very relevant. Essentially, if you can imagine a computer with infinite memory, you'd have a Turing Machine.

The capabilities of a Turing Machine can be measured. We know exactly what a Turing Machine can do, and what a Turing Machine cannot do. Humans are capable of doing things that a machine cannot. I'll give you an example.

This segment of code:

while(true) {
   printf("Hello World. ");
}

...would print Hello World indefinitely. How do I know this? I didn't test it. I can look at it and know. However, you cannot build a program (or Turing Machine) that can figure this out, as incredible as that sounds. It can simulate the program, but it would never end (thus never producing an answer).

Which begs the question, what is the key difference that allows humans to detect something a machine cannot? Nobody knows. Evidence has come to show that the realm of things that cannot be accomplished by Turing Machines is far greater than the realm that can be.

Another theorem states that if you can create a list of accomplishable steps to a goal, you can write a Turing Machine that will do that goal. Finding out that that segment of code up there never ends for any code is something that cannot be done by a list of steps.

All this time and energy spent into theorems and machines, and all we have seemed to pin down is the fact that if we can't express it using mathematics or language, then we cannot create a program that will run it, which perhaps suggests that there is much that we cannot do simply because we haven't invented the language express how to do it.

Do forgive me if I am ranting. I don't know if this is interesting for any of you guys, but this is fascinating for me.

Basically, according to the theories, artificial intelligence cannot be a form of Turing Machine. AI must simulate human intelligence, and to do that, it must work at a level closer to ours. To do that, we must first understand how we ourselves think.

If you want a calculator, stick with a computer. If you want a human simulator, you need to build a computer that doesn't depend on definite answers. Humans are not calculators. They make mistakes. It seems that this is the way we are able to accomplish things that machines cannot, as strange as that sounds.

I believe AI gives us a lot of insight about who we are. There is a theory that states that it is not possible for a sentient being of a certain level of intelligence to create another sentient being at a higher level. While I agree with this, I do believe the capability of human understanding stretches much farther than we know. Like a ladder, humans are climbing, and I believe the moment we reach the rung when we can lift computers to be sentient, it will be done.

Yes, I believe in artificial intelligence. Sorry to ramble. How do you guys feel about this subject?

If the world should blow itself up,the last audible voice would be an expert saying it can't be done

Its difficult to describe a chaotic system. And if its not a chaotic system to begin with then we still need all its variables for a good description. With the current knowledge we have about ourselves its impossible to create a machine that accurately simulates human decision making and behavior. The problem about it is not so much the limited technical power anymore, but more the fact that we dont know ourselves good enough yet to describe and program - even see - all the details.

For instance there is no accurate knowledge about infinity, but all we can do with our limited minds is to give a definition of what we think it might be. Looking at that piece of code we THINK we know what it does, but that is just an incorrect statement. Since noone knows, what infinity means we ASSUME the result and thus think we know the answer, which is in the end just one POSSIBLE answer, but stays unproven. We DEFINE the result, we do not know it for sure. Therefore any machine trying to simulate human intelligence has to be trained the current limitations of the human mind first of all.

Take the vast field of experiences, emotions and feelings. Mankind still looks at it in a state of fascination and not-knowing, TRYING to make some sense of it by different approaches. A combination of electrical and chemical ingredients mixed with a spoon full of time suddenly makes a personality, a soul. How? What is a soul anyway? You can try and answer that with a psychological approach, or with a bio-chemical, philosophically or even religious. But as long as we dont KNOW anything about it, its the main task for AI to project and define those limitations in knowledge rather than to get a grasp on its complexity.

So the task that makes AI difficult to built is not only to simulate human intelligence, but rather human stupidity. May be its technically possible meanwhile to find answers to questions that we didn't even think of yet. What to do with answers that we dont know and understand the question to? Those machines have to be taught the human self-protecting functionality to replace knowledge with assumptions, experience and definitions once any limits are reached. But those limits have to defined accurately, which again means we have to be aware of it to begin with. Not everything thats technically possible automatically is of any use to simulate human thinking. Can we learn about ourselves from such a machine? Hmmm.. I dont know. But what we actually learn from, is the curiosity to try and find out! Its highly likely, no, its absolutely sure that people in 200 years from now will laugh about a discussion like this, just because of their broadened knowledge and experiences then, which they gained in the end by our curiosity.

After decades of construction my website is finally up an running: www.kkds.de

I am not sure I agree with any of the arguments you forward for a theoretical, fundamental difference between "machine intelligence" and human intelligence.

I don't know of anything Turing Machines cannot theoretically do and which humans can do. Your code example is not quite right. The theorem is that one cannot build a Turing Machine that will be able to determine whether any program will stop. But it is easy to imagine Turing Machine that determines whether certain programs (such as the one you quote) would stop or not. By the same token, it would be easy to construct a program such that no human will ever be able to determine whether it stops or not.

Building programs that have human-like features (such as making mistakes) is actually not difficult, if you only allow a true randomizing element. Since all humans react to inputs, a human simulator could easily devise a randomizing element using some of its inputs (e.g. time between keystokes, least-significant digit in its clock, etc.)

There are several practical limitations for building a human simulator. I can think of three, but I'm sure there are many others:

1. Full complexity of a human mind far exceeds the hardware capabilities of today's computers

2. Humans require a very long training period

3. Human minds come with a lot of very sophisticated hard-wired input processing modules

All of those are practical, but not theoretical limitations.

Good posts, Martin and Eran.

It's good to discuss this with people that truly have a solid understanding of it.

However, Eran, I'd have to disagree with you regarding the program. You can make compilers, which will correct improper syntax and even semantical statements. However, if you ask it to check to evaluate if a program ever halts, it has to simulate it (even if it means ignoring most of the commands except the branches).

Sure, you could train a program to look for the exact code

while(true) {
    printf("Hello World. ");
}

...however, that is not the only way to create an infinite loop, not by a long shot in fact. Just like there are an infinite number of ways to write the expression 1=1 (2 - 1 = 1 etc.), there are infinite ways to create infinite loops.

So while you might make a program that will hunt down recognizable pieces of code, it will not manage to discover whether any program will halt or not. This is what the theorem states in fact. It has to work for any and all programs.

This of course implies you could not write out an algorithm which will accomplish this task. If you wish to prove me wrong, write a program or an algorithm that will detect whether this piece of code halts or not. :)

I had to try this myself in fact before I could believe it.

If the world should blow itself up,the last audible voice would be an expert saying it can't be done

Hawkeye,
I think where we differ is the distinction between the practical and the theoretical.

From a practical perspective I totally agree with you. It is very difficult and wholly impractical, with today's technology, to teach, for example, a compiler to detect infinite loops. God knows, on more than one occasion I would have been grateful for one :-)

In their ability to detect infinite loops, humans are much better than machines. But then, humans are much better than machines in many ways. Just think about hotmail's "demonstrate you are human" tests...

From a theoretical perspective, however, things are different. The theoretical proof that there cannot be a universal "stop-determining" Turing Machine relies on directing such a machine on itself (or a trivial variation of itself). The equivalent for humans might be to expect a human to look at a problem (say a difficult mathematical theorem such as Fermat's Last), and be able to tell whether a specific person could ever solve the problem. Hard, wouldn't you say?

I think you are both drawing the wrong conclusions. The point of the halting problem is not that programmed processes are inherently inferiour to human thinking, but that our way of programming machines is incomplete in expression.

'Yeah, That's what Jesus would do. Jesus would bomb Afghanistan. Yeah.' - snowlion

Could you be more specific Jaz?

At least, how I understood it, is if you had an entire warehouse full of sheets of 8.5 by 11 inch pieces of paper in gigantic crates the size of houses and another warehouse full of mechanical pencils full of lead, and you had to sit down to work a problem, and if you could accomplish that problem, so could a machine.

We're not talking about mental exhaustion. You have as much time in the world to do something. Some problems are tedious and long, but they can still be done with enough time. Likewise, if you limit the time or resources of a machine, you limit the type of things it can accomplish.

Unfortunately, you can't really look at someone and tell whether or not they can solve a problem. That isn't the point. The question is whether or not a machine can do it as well as a human. The only way a machine can do this is to simulate it.

There are two answers you can get as a result of running a halting problem on a program. One of which is of course, no, the program does not halt, or two, the more enigmatic answer, undetermined.

You can't do much with an undetermined. You could let it run for 10 minutes, but then say it doesn't halt if it keeps going past that mark, but this won't work for 100% of the programs. So what is the appropriate waiting time? 1 hour? 1 week? 1 year? 100 years?!

Well the answer is infinite time. How do humans do it then? We look at what it is accomplishing. If we see code repeat under the same conditions (or different conditions which makes no distinction on the course of actions to follow), then we realize it never halts. That's the difference. If we waited for a program to finish printing "Hello World", we'd be taking a machine's approach and never have a definite answer.

Are we in agreement Eran?

If the world should blow itself up,the last audible voice would be an expert saying it can't be done

I'll give you guys another example of something humans can figure out (barely) but machines cannot.

Supposing you have an x state machine, what are the maximum number of marks can be written on a tape that isn't infinite?

In other words, a state is something you are at currently.

So if you were in state Q0 for example, and you had a tape that started off looking like

.    |
     v
-----------------------------------
| | | | | | | | | | | | | | | | | |
-----------------------------------

And you see a blank, write an X instead, and move to the right and go to state Q1.

There would be no Q1, so your tape would look like

.      |
       v
-----------------------------------
| | |X| | | | | | | | | | | | | | |
-----------------------------------

...and your program would end. So F(1 state) = 1.
Now imagine if you had 2 states. The amount of x's you can write increases by a certain amount. The amount each time is faster than exponential, however (and here's the kicker) we have no formula to figure out what F(x) equals.

In other words, we have up to F(8) I think (it is something far greater than the number of atoms in the known universe), but we were not able to use a formula to figure it out.

This implies one of two things. 1) We have not figured out the formula yet or 2) No formula exists to describe such numbers.

If the world should blow itself up,the last audible voice would be an expert saying it can't be done

This post was edited by Hawkeye on Feb 01, 2005.

Could you be more specific Jaz?

When we're programming a machine we're still churning out Turing machine code. On a far higher level of abstraction of course, but the final output is still: read from tape, write to tape, move on. The halting problem proves that there are problems that cannot be solved by a Turing machine. What it doesn't prove is the impossibility of finding of other programming paradigms that might be more complete.

'Yeah, That's what Jesus would do. Jesus would bomb Afghanistan. Yeah.' - snowlion

That's certainly true, Jaz. Though, at least for me, it's hard to imagine a better programming language than the ones we already have. What can't you do with today's programming languages if you had enough time and resources?

Obviously not the halting problem. :P
Does this mean there is a programming language that can be used to solve the halting problem?

If you stumble over something like that, you'll be a multi-millionaire. There are businesses putting up million dollar rewards for people that can solve the halting problem and P=NP complete (proving halting implies P=NP complete).

If the world should blow itself up,the last audible voice would be an expert saying it can't be done

at least for me, it's hard to imagine a better programming language than the ones we already have.

Personally I am dissatisfied with the current state of language design. I don't have the overwhelming feeling that we're closing in on the best way. The state of art merely seems to be the result of many next logical steps stacked on top of each other. There is little overall concept to what we do. We’re nailing planks together and seeing what happens.

Of course it is hard to imagine something better, because we immediately associate "better" with "improvement to what we have" and the obvious improvements have already been implemented. No one can come up with something radically different on the spot.

What can't you do with today's programming languages if you had enough time and resources?

Even if I could do everything with the languages we have, it doesn't mean there isn't something vastly better. The biggest problem in software design is currently the fight against complexity. Even when implementing mildly extensive requirements complexity grows over our heads much faster than one would intuitively think it would. Object oriented design and, more recently, aspects, have taken away some of the pain, but what remains is a strong suspicion that there has to be a better way.

Also you can only throw so many people and resources against a problem until time required for coordination reaches some sort of equilibrium against productivity. And even unlimited resources do little to banish the scourges of complexity, increase of coupling and loss of cohesion.

'Yeah, That's what Jesus would do. Jesus would bomb Afghanistan. Yeah.' - snowlion

This post was edited by Jaz on Feb 01, 2005.

Hawkeye,
I'm afraid we are not in agreement.

You suggest one (failed) algorithm to determine whether a given program (="machine") will stop - i.e. simulate it.

But who said machines are theoretically limited to that algorithm? My point is that in theory we can program a machine to identify more and more complex patterns, and potentially even to come up with mathematically-robust proofs that certain machines (not all - only certain machines) will stop or will go on forever. There have been proofs-of-concept successes in teaching computers to come up with geometry proofs, for example.

I totally agree that's not an easy thing to do. But then we have already managed to teach computers to do "difficult" things like recognize speech and handwriting and play world-class Chess (but not Go :-)). Who are we to say that it is impossible to teach a machine to be able to make the stopping judgement on other machines, not perfectly - just as well as humans?

My point is that the usual theoretical proof is irrelevant. It states that it is impossible to device a machine that will be able to make the judgement correctly for arbitrary machines. But that's too high a bar, because people cannot do that either.

Eran, I don't doubt the capabilities of computers to do extraordinary things, but our limitations come from a proof. Unless that proof is made false, no amount of technological advances will enable us to detect any and all programs and whether or not they halt.

The proof: http://www.comp.nus.edu.sg/~cs5234/FAQ/halt.html

Now it's quite a different matter if we aren't talking about Turing machines. However, we are talking about computers, which are limited Turing Machines.

Though, I won't sit here saying that that proof is 100% correct. I have no idea. However, I am saying for Turing Machines to find out if another machine halts, the proof must inevitably be proven false.

And Jaz, I know perfectly what you mean. It seems that programming languages are doing more complicated things in the background just to display an easier system to the programmer. It's like putting on huge winter jackets to shield yourself from the cold outside, but not being able to move much afterwards. Makes me wonder what the best programming language is, and if it could actually be made readable to the average person.

If the world should blow itself up,the last audible voice would be an expert saying it can't be done

This post was edited by Hawkeye on Feb 02, 2005.

Hawkeye,
The theorem being proved by this proof is that one cannot construct a Turing Machine (or, equivalently, any computer program) which will be able to take a description of an arbitrary other Machine, and determine whether it halts or not.

The keyword here is arbitrary. The proof does not show, for example, that it is impossible to create a Turing Machine that will determine whether any C++ programs shorter than a 1,000,000 lines. In theory, that is still possible. The key to the proof is that if you could build a "Halt" program, you could then turn it "against itself".

What I argued before is that humans cannot determine whether an arbitrary Turing Machine will stop either. Before Fermat's Last Theorem was proved, for example, one could have used the following simple example: set up (a very simple) program that "tries out" successively large numbers to try to find a^n+b^n=c^n. If the machine finds such a combination, it halts. Otherwise, it continues to look for larger and larger numbers. Will it ever halt? Determining that is equivalent to proving Fermat's Last Theorem. Until a few years ago, no humans could have claimed to be able to do that. I am sure there are still many open problems in math that can similarly be "simulated" using a computer program that, consequently, no human could determine whether it (the computer program) will halt or not.

Humans are very good it determining whether relatively simple programs halt or not. But then, an incredibly complex program could potentially do that as well.

What if one simply constructed an alogorithm that recognizes the loop code and defaults to a rule that if there is no further code (of any kind) such loop must not halt?

This post was edited by curio100 on Jun 01, 2008.