Lambda the Ultimate

The 2,3 machine reminds me of other Turing tarpits like BrainFuck and Unlambda.

I'm not sure it is accurate to crown 2,3 as the "simplest universal Turing Machine" - unless one explains what they mean by simple. That is, 2,3 is the simplest UTM when the constraint is constucting a machine from the smallest number of bits possible.

[Note: content variously edited - stumbling for the right words].

... good to "see you" here, Frank!

And the same to you, Marc!

(Acronym Expansion Police): For the record, this usage of LBA appears to mean Linear Bounded Automaton.

As an LBA seems to be defined as a Turing machine that is restricted to use an amount of tape linear in the input, then what is an LBA without the size restriction but a general Turing machine?

A Turing machine is also only universal if you keep "feeding in" (letting it move to more) tape indefinitely.

Given a "classic LBA" L as you understand it, one can build (without general computation, in a finite number of steps) a second LBA, L-halting, that always either computes the same final result as L or halts with a state and tape condition that tells us that L would loop forever.

Suppose (for illustration -- there are other ways to construct this) that L and L-halting both use the colors Red, Blue, and Green on the tape.

L-halting-as-turing is a turing machine (infinite tape) that is just like L-halting, except there is an additional color -- Purple. When we program L-halting-as-turing we paint some continuous finite region of the tape with Red, Blue, and Green -- but the rest of the tape in both directions is purple. Because L-halting-as-turing is (at heart) just an LBA, if started off at the right place in the initialized region, it will never stray into a purple cell. It will always halt before doing so.

Now we can make one more machine: L-searching-using-L-halting-as-turing.

That last machine runs just like L-halting-as-turing but if it would ever halt because L would halt, it does something different -- it marches towards the right looking for purple. Finding purple, it continues until (if ever) it hits Red Blue or Green and, should it find such a cell, it does a second round of emulation of L-halting-as-turing. (Then repeats -- if that second emulation doesn't work it looks for a third chance, etc.)

So, it's pretty obvious that L-searching-using-L-halting-as-turing is not universal like a universal turing machine. If you give L-searching* a tape with only a finite non-purple region, it can't compute anything that couldn't be computed by giving an LBA (specifically L) a similar initialized region.

But, if the tape is not infinitely purple in at least one direction -- there's a chance that L-searching* can do computation.

Can L-searching* be universal if the rest of the tape isn't all purple -- but is some regular language pattern? Yes. As it passes over each purple cell, L-searching* can paint it some other color. When it next encounters a non-purple cell in its rightward-trek, it can enter a "retry" state that regards the painted over purple cells as extra memory in which to retry the same problem.

So here is an interesting question: do there exist LBA such that the corresponding L-searching* is *not* universal with any regular language input tape but *is* universal with some a-periodic tape that can be defined by induction over some non-universal computation?

Smith has shown that the 2-3 is equivalent to an L-searching* machine that is universal given a non-regular input tape. Is it universal given a regular tape?

Additional questions:

We can transpose the Chompsky hierarchy to input tapes. There are infinite tapes that can only be given by induction over a regular language, infinite tapes that can only be given by induction over a linearly bounded language, over a push-down automata language or over a turing machine.

Corresponding to each class of tapes is a class of machines that, given some tape of that sort, can complete a universal computation.

For example, regular machines, LBA, and PDA all (trivially) form a computationally complete system with a tape prepared by induction over a universal turing machine.

A regular machine does *not* form a complete system when combined with a tape prepared by another regular machine, or by an LBA or PDA.

And so on.

Smith has exhibited two machines: the 2-3 challenger and the induction step of his tape construction. Together they are universal. I'm not sure we know much more than that.

-t

This is not quite the same distinction as your GPCs here versus traditional TMs, but ...

Yuri Gurevich had a nice result back at the University of Michigan in the late 1980's or early 90s about TMs and their infinite tapes. Specifically, he showed that the computing power of a machine with finite tape size, as that finite size went to infinity, was in the limit not equal to the power of a traditional TM with an infinite tape.

This is a bit surprising, since "finite, tending toward infinity in the limit" sure sounds a lot like "infinite".

I could probably dig up a reference on this if someone wants it.

(Yuri is now at Microsoft Research, doing work on Abstract State Machines, some of this with Andreas Blass (still at Michigan, I think). ASMs were a kind of reaction to Denotational Semantics in their early years, at least as I understood it.)

Specifically, he showed that the computing power of a machine with finite tape size, as that finite size went to infinity, was in the limit not equal to the power of a traditional TM with an infinite tape.

Taking those words as ordinary english they sound trivially false and I don't see a paper on Yuri's http://research.microsoft.com/~gurevich/annotated.html">list of publications that is obviously what you are talking about. So, I'm sure I have no idea what you refer to.

Can you give some pointers and/or expand on what you mean by "limit", "infinite", and "equal in power"?

Thanks,
-t

[Sorry for the delay, Thomas: I couldn't find Yuri's tech. report in my files, but eventually got it (or what I suspect I was thinking of) from the web; "Google rocks", etc.).]

I think the tech. report in question was Reconsidering Turing's thesis: (toward more realistic semantics of programs), a 1984 technical report, #CRL-TR-36-84, with a PDF available at the link cited, via U. Mich. libraries "Deep Blue" project. (No chess connection, AFAIK: "blue" is just the color associated with Michigan's sports teams, as in "Go blue".)

I've just skimmed the report, but the basic idea is a critique of the notion in Turing's model of access to unbounded tape. Yuri defines a model based on families of resource-bounded machines instead. This particular tech. report does not formalize everything, but asks whether uniform families of bounded machines correspond to traditional TMs (with unbounded resources), including some discussion about algorithms which do or don't make use of explicit access to the bounds. While I don't think there is a firm technical result here regarding the difference between unbounded TMs and families of bounded machines in the limit, it is at least suggested by an informal construction. And I recall it being pitched that way at the time, although that may have been someone else's characterization (i.e., not Yuri's).

There may be more formal/technical results in Yuri's later work: you'll have to forgive some fuzziness and gaps in my memory, since this is all about 24 years ago. For that reason and others, you should look to Yuri's actual papers (rather than my interpretation) for an accurate sense of his results and position.

LTUers in general may be more interested in some remarks in the introduction to the tech. report about lambda calculus as the basis for formal semantics, e.g.:

It was surprising to find untyped lambda calculus as a basis for denotational semantics. This calculus was never too popular among logicians; the underlying intuition of the calculus is not clear. Note that untyped calculus is used in [St] mostly for foundational purposes; when it comes closer to applications, a much more intuitive typed calculus is used.

The paper represents the beginning of Yuri's (and others) Abstract State Machine project, which is now quite mature and well-documented in the papers listed at his (aforementioned by Thomas) Micrsoft website. In essence this is a critical response to denotational semantics in general.

At the time I think I had a basic stylistic clash with Yuri over these perspectives: I found lambda calculus quite intuitive and machine-based formalisms less so. Now I find his critique more interesting. Of course, I was just a beginning grad student in 1984: I have matured a lot since then (I hope ;) ), taught courses on automata and formal languages, etc.

(Ironically, I think that the combinator-graph based implementation of Miranda (tm), which I was using and studying at the time, would probably fit quite well into Yuri's scheme of things ... but I suspect his taste does not especially run toward functional languages. Miranda is of course a trademark of Research Software, Limited.)