Talk:X-machine

From Wikipedia, the free encyclopedia

Many thanks to whoever created this page - it was a great idea. Since my last edits a few months ago, I've been planning pages for the SXM and the SXM testing methodology, but time has been limited. If anyone can contribute to those pages as well, please do!

  1. I've now added a lot more detail, and included loads more references, and several more variants.
  2. Confusingly, there are two similar sounding parallel models: the CXM and CSXM. I've been trying to work out which one came first, but am rapidly coming to the conclusion that they were simply developed independently at essentially the same time (1994/5)
  3. The current description in this article only considers XMs that compute relations from X to X. However, by adding encoders and decoders they can be used to compute relations of type Y -> Z, for any Y and Z. This is part of the standard description, so it ought to be added. Would adding it in the example be enough?
  4. The computational power of XMs is quite subtle. Given any relation R: Y -> Z at all, there's an XM (with encoder/decoder) that computes it. I'd like to add a para discussing the meaning of this result.

Mike.stannett (talk) 22:51, 21 March 2008 (UTC)

I had a think about some of the above issues and have now expanded the discussion of Eilenberg's original X-machine model to include the encoders and decoders, as requested. Unfortunately, the example is not obviously a case of the most general kind of X-machine, but rather appears to accept keyboard keystroke inputs (like a Stream X-Machine), so I'm going to have to think about another example.

AJHSimons (talk) 14:35, 28 March 2008 (UTC)

So, I have now done what I suggested above. I have included a different example, which more obviously has an encoding and decoding stage, with the general X-machine running to completion and applying relations to X. The example is a keyhole optimizer, which performs several transformations upon the memory datatype X (a parse tree). I hope everyone likes this! I think it more accurately exemplifies Eilenberg's original machine. Of course, the word processor example could be used later to illustrate a Stream X-Machine.

AJHSimons (talk) 15:24, 29 March 2008 (UTC)

Good call - the example I originally included was decidedly trivial, whereas yours shows much more clearly how the processing works, and how X-machines can be used to describe real (and relevant) behaviours. Great to see all your extra info as well!

Mike.stannett (talk) 02:12, 31 March 2008 (UTC)