LISTSERV at the University of Georgia
Menubar Imagemap
Home Browse Manage Request Manuals Register
Previous messageNext messagePrevious in topicNext in topicPrevious by same authorNext by same authorPrevious page (June 2006)Back to main SPSSX-L pageJoin or leave SPSSX-L (or change settings)ReplyPost a new messageSearchProportional fontNon-proportional font
Date:   Sat, 3 Jun 2006 00:21:05 -0400
Reply-To:   Richard Ristow <wrristow@mindspring.com>
Sender:   "SPSSX(r) Discussion" <SPSSX-L@LISTSERV.UGA.EDU>
From:   Richard Ristow <wrristow@mindspring.com>
Subject:   The transformation language is not Turing-complete
Content-Type:   text/plain; charset=us-ascii; format=flowed; x-avg-checked=avg-ok-8FC4C0D

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.)


Back to: Top of message | Previous page | Main SPSSX-L page