Reading Philosophy

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.

Further code? I'm not sure what you mean, could you clarify?

I see what you mean about recognizing the loop code.

It's true to an extent. We could create a parser which could recognize certain loops. Though you wouldn't be able to apply it to all programs. There are some programs which apply fundamental mathematic principles that, although the theory states otherwise, we have been unable to prove (at least until recently), such as Fermat's Theory.

A program with such an algorithm wouldn't be over 1,000,000 lines of code. It's enough to create a program 10 lines long to be able to stump a halting algorithm. For that matter, the same example would stump a human being. Not that a human being would take an infinite amount of time to answer whether or not it would halt, just that it would be potentially wrong. Though, it should be said that the incredible complexity by which humans judge whether or not an algorithm stops is considerable and very accurate. Asking whether an algorithm which searches for large prime numbers greater than n where n is the largest prime number we've found so far is something a human being would repond within several seconds and be correct (though technically unproven). Though to be able to say that there is a prime number greater than the largest we've ever found and to prove it are radically different.

There's more in http://en.wikipedia.org/wiki/Halting_problem under "Can humans solve the halting problem?" section.

That should go to show that perhaps we approach the problem from the wrong point of view. If we could have a computer 'guess' accurately for 100% of programs, it'd be infinitely more useful than a computer which cannot *prove* anything about any program. Computers were designed to solve straight mathematics fast and easily, and they're very efficient at it. It was likely assumed at the time that higher functionality to that of a human being would evolve naturally from that, though we've since come to realize that our 'higher' intelligence derives from a sort of fuzzy logic in which we make very very very intelligent guesses, not correct answers.

The true direction we should be taking computers should be this fuzzy logic, in my opinion. We've mastered fast calculation, and now we need to master what would be equivalent to the right half of our brains (which I should add is the part least understood, but may indeed be the more brilliant of the two halves).

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 Jun 12, 2008.