Re^3: If I was forced to use only one kind of loop for the rest of my days it would be a

in reply to Re^2: If I was forced to use only one kind of loop for the rest of my days it would be a
in thread If I was forced to use only one kind of loop for the rest of my days it would be a

Who cares about Turing completeness? You're running on a machine with a finite number of states; so a DFA language is all you can really implement in real life. Turing complete languages can't be implemented; just approximated.

I could attack this statement from the theocretical side. Computer hardware is developping in a very fast pace. Let's imagine you have a system where the state of the program can be saved and reloaded on a machine with more memory, or one that runs on a transparent cluster of machines where new nodes can be added dynamically and old nodes discarded. Such a system could run forever, if you keep updating it with new hardware. While my lifetime or the lifetime of the computer I'm typing on right now is certainly finite, such an advanced system could live forever, if the civilisation doesn't end in some catastrophe. (In fact, Paul Davies argues in his book The Last Three Minutes that a super-entity could do an infinite number of calculations, and discusses this in the two cases of whether the Universe will expand forever and end in a Big Chill, or gravitation will win and the Universe will end in a Big Crunch.)

However, even if a DFA is all you can implement in the real-world (there are some steps between the DFA and a Turing machine in power of course), I am a mathematician, and I'd like to at least imagine that I have a Turing-complete machine. I use it even if it's only a theocretical construction. I am not an engineer, who uses a ruler to draw straight line, and uses large plastic templates to be able to draw any kind of ellipse. I just draw a bumpy line or a potato by hand, and say it's a straight line (moreover, an infinitely extending straight line that has no width or thickness) or an ellipse. This is a very pleasant, almost god-like state, because I can create objects engineers can't even dream of just by the power of my mind.

Naturally, this is not the real reason I wouldn't rely on foreach loops. The reason is simply that they're often difficult to use. It's not easy to convert while loops to foreach loops. It's even more difficult to do it if you care about efficency (because I don't just have any DFA, but a DFA with a limited number of states and limited speed of execution). Foreach loops require to use side-effects even if I don't want to, and you could easily avoid it with do loops. Foreach loops come in different versions in each programming language. But the deciding reason is that C doesn't have a foreach loops, so if I decided on foreach, I couldn't use C anymore.

Update: "it's silly to stop with a Turing-machine" -- you're right with this part. "Why not use a bigger field(?) than the integers" -- indeed, why not: Symbolic calculations with operator overload, Re^3: Illegal Modulus zero.

Comment on Re^3: If I was forced to use only one kind of loop for the rest of my days it would be a

Replies are listed 'Best First'.
Re^4: If I was forced to use only one kind of loop for the rest of my days it would be a by Anonymous Monk on Oct 05, 2005 at 17:40 UTC
I could attack this statement from the theocretical side. Computer hardware is developping in a very fast pace. Let's imagine you have a system where the state of the program can be saved and reloaded on a machine with more memory, or one that runs on a transparent cluster of machines where new nodes can be added dynamically and old nodes discarded. Such a system could run forever, if you keep updating it with new hardware. Nope, not even theoretically possible, unless you're much more theoretical than me. You need infinite memory as well as infinite time; where are you going to get infinite matter? It would take infinite energy to assemble it all. It would take infinite space to put it, and we're pretty sure the universe is finite, even if constantly expanding. Worse yet, any system we can concieve of has some critical component with non-zero probability of failure. Over infinite time, that non-zero failure probability becomes a certainty. To my mind, anything that requires perfect anything as a theoretical condition of it's existance is just a mathematical excercise, and there are more interesting ones out there. Update: "it's silly to stop with a Turing-machine" -- you're right with this part. "Why not use a bigger field(?) than the integers" -- indeed, why not: Symbolic calculations with operator overload, Re^3: Illegal Modulus zero. I wasn't trying to argue for computer implementation of various fields (the most basic being simple polynomials), nor was I looking for a first year primer on group theory. Thanks, but I've been to school once already. :-) My point was, if you're just in it for the complex mathematical abstraction, you can carry a Turing machine as far as you like. Cantor's theorems (together with some others) imply that you can make fields as arbitrarilly large as you like: for any field you care to name, there's a field extension that will make it infinitely bigger, even if the field already was infinite in size. Godel's theorem states that the field extension can never be large enough; for any field with basic, interesting properties, there is always a proposition which has a truth or falsehood which is expressable in a given field, but the truth or falsehood of that statement is not resolvable within that field, but only (possibly) in some field extension. You can build an infinite number of meta-Turing machine models in your head, and use them to do transfinite arithmetic if you so choose. None of it means anything, though; you're stuck with boring old DFAs when it comes down to what you can really ever build, so trotting out Intro To Theoretical Computing is nice and all, but in the real world, we can't even factor million digit numbers, let alone infinitely large ones. It would be nice to solve the optimal Travelling Salesman problem for all the cities on the planet, but we can't even do a single country. It's a long, long way to infinity! -- AC	[reply]

Replies are listed 'Best First'.

Re^4: If I was forced to use only one kind of loop for the rest of my days it would be a
by Anonymous Monk on Oct 05, 2005 at 17:40 UTC

Nope, not even theoretically possible, unless you're much more theoretical than me. You need infinite memory as well as infinite time; where are you going to get infinite matter? It would take infinite energy to assemble it all. It would take infinite space to put it, and we're pretty sure the universe is finite, even if constantly expanding.

Worse yet, any system we can concieve of has some critical component with non-zero probability of failure. Over infinite time, that non-zero failure probability becomes a certainty. To my mind, anything that requires perfect anything as a theoretical condition of it's existance is just a mathematical excercise, and there are more interesting ones out there.

I wasn't trying to argue for computer implementation of various fields (the most basic being simple polynomials), nor was I looking for a first year primer on group theory. Thanks, but I've been to school once already. :-)

My point was, if you're just in it for the complex mathematical abstraction, you can carry a Turing machine as far as you like. Cantor's theorems (together with some others) imply that you can make fields as arbitrarilly large as you like: for any field you care to name, there's a field extension that will make it infinitely bigger, even if the field already was infinite in size. Godel's theorem states that the field extension can never be large enough; for any field with basic, interesting properties, there is always a proposition which has a truth or falsehood which is expressable in a given field, but the truth or falsehood of that statement is not resolvable within that field, but only (possibly) in some field extension.

You can build an infinite number of meta-Turing machine models in your head, and use them to do transfinite arithmetic if you so choose. None of it means anything, though; you're stuck with boring old DFAs when it comes down to what you can really ever build, so trotting out Intro To Theoretical Computing is nice and all, but in the real world, we can't even factor million digit numbers, let alone infinitely large ones. It would be nice to solve the optimal Travelling Salesman problem for all the cities on the planet, but we can't even do a single country. It's a long, long way to infinity! -- AC

[reply]

In Section Past Polls