On 07/10/2007, Richard Loosemore <[EMAIL PROTECTED]> wrote: > I have a question for you, Will. > > Without loss of generality, I can change my use of Game of Life to a new > system called GoL(-T) which is all of the possible GoL instantiations > EXCEPT the tiny subset that contain Turing Machine implementations.
As far as I am concerned it is not that simple. Turing completeness has nothing to do with any particular implementation of a TM in that system. It is a property of the system. That is the ability to be organised in such as way as to compute whatever a turing machine could. And there are many, many potential ways of organising a Turing complete system to compute what a TM could. To take an analogous example. Lets say you wanted to take C and make it no longer turing complete. Well the simple way, you would remove loops and recursion. Then to be on the safe side self-modifying code in case it wrote in a loop for itself. Why such drastic measures? Because otherwise you might be able to write a java/ruby/brainfuck interpreter and get back to Turing completeness. So maybe I am throwing the baby out with the bath water. But what is the alternate method of getting a non-Turing complete subset of C. Well, you would basically have to test each string to see whether it implemented a UTM of some variety or other. And discard those that did. It would have to be done empirically. Automatic ways of recognising strings that implement UTMs would probably fall foul of Rice's theorem. So in imagining GoL-T, you are asking me to do something I do not know how to find simply without radically changing the system, to prevent looping patterns. And if I do the complex way of getting rid of UTMs, I don't know what the states left over from the great UTM purge would look like. So I can't say whether it would still be Complex afterwards, to know whether the rest of your reasoning holds. Will Pearson ----- This list is sponsored by AGIRI: http://www.agiri.org/email To unsubscribe or change your options, please go to: http://v2.listbox.com/member/?member_id=8660244&id_secret=50866846-9589ac
