turing machine in an LC (was: Xah Lee's stupid question #853,172)

[Jeremy Bowers]

On Tue, 08 Feb 2005 17:36:19 +0100, Bernhard Herzog wrote:

> Nick Vargish <nav+posts at bandersnatch.org> writes:
> 
>> "Xah Lee" <xah at xahlee.org> writes:
>>
>>> is it possible to write python code without any indentation?
>>
>> Not if Turing-completeness is something you desire.
> 
> It's possible to implement a turing machine with a single list
> comprehension.  No indentation needed.

I had to think about it, it's an interesting, and I'm going to tentatively
disagree, because of the statement/expression dichotomy. "Tentatively"
because if somebody can answer these objections than I will happily change
my mind :-)

I can't figure out how to write a TM in a Python List Comprehension
without one of either "variable binding" (so we can store the last symbol
list and manipulate it in the next iteration) or "recursive function" (to
express the whole tape as a recursive function), both of which require
statements. I can figure out how to write a single state transition, but
in a single LC I can't figure out how to feed the new state into the next
iteration; the previous values generated in the LC are, to my knowledge,
not accessible to the LC as it is running. (If they are, I *think* that
would indeed be enough.)

I'm sure Haskell could do both, being a functional language, and I am
satisfied that it is probably possible in that language, as long as you
are resigned to creating a wasted list (which may not even matter in
Haskell). But I think you're screwed in Python with an LC.

However, hack hack hack, I think you could do this in Python 2.4 with a
*generator* comprehension and a couple of supporting lines of non-indented
code:

Python 2.4 (#1, Jan  2 2005, 22:17:50) 
[GCC 3.4.3  (Gentoo Linux 3.4.3, ssp-3.4.3-0, pie-8.7.6.6)] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> import sys
>>> this = sys.modules[__name__]
>>> magicGenerator = (getattr(this, "results")[-1] + 1 for x in range(5))
>>> results = [0] # you have to prime the state here
>>> results.extend(magicGenerator)
>>> results
[0, 1, 2, 3, 4, 5]
>>> 

Now you *can* get at the previous state and write a state-transition
expression in perfectly legal Python.

What do you know, generator comprehensions are Turing Complete and list
comprehensions aren't. I wouldn't have expected that.

People caught using this technique in real code will be caught and forced
to code in Intercal for the rest of their lives.