|
Here's a bit of educated trivia:
One of the foundation theorems of computer science is Turing's
Universality Theorem. (It's due to the English mathematician Alan
Turing, who went a large way to inventing what is now called computer
science.)
Turing's Universality Theorem states that any computing system that
reaches a certain level, has in principle all the power of any digital
computing system. ("In principle" means, capable of carrying out any of
the computations IF you give it enough added memory, and are willing to
wait as long as necessary for the answer.) The level of complexity is
surprisingly low, and is reached by all programming languages as that's
generally understood. A system that reaches that level is called
"Turing complete."
Now, interestingly, the SPSS transformation language is not Turing
complete. It's about the only reasonably powerful language I can name,
that isn't.
OK, why isn't it? Well, we can get at that through the famous "Halting
problem." That's another theorem of Turing's: if you have a Turing
complete system, there is no computer program that can study its
programs and tell, in all cases, whether or not the program will ever
stop.
But you CAN tell whether transformation-language programs will stop:
they always will. That's because there are only two exceptions to
straight flow of control through the program: DO REPEAT, and LOOP. DO
REPEAT is really a macro-like facility that generates the code implied
by each iteration. And all LOOPs terminate, because either they have an
indexing clause, or they'll be terminated when they reach the MXLOOPS
limit. (Of course, IF clauses on LOOP or END LOOP statements, or BREAK
statements within, may end them sooner.)
I'd been thinking you could make a loop run infinitely by modifying the
loop counter so the upper limit was never reached. Now that we know
that the actual loop counters are inaccessible to the program, that
isn't possible. So, all LOOPs terminate; so, all transformation
programs terminate; so, the language isn't Turing complete.
Now, you all were just waiting to have this question resolved, weren't
you?
(I don't know. Maybe you can make an infinite loop by setting an upper
bound larger than 2**53, so the counter eventually gets so large that
adding 1 to it doesn't change the value.)
|