Programmed a bit further, factored out the bits conversion. Code looks clean again. Looked at the CAM machine.
There's, of course, an informal proof that termination of eager reduction is good enough to prove Turing completeness of Dot. Since the SKI is expressible for normalizing terms, and normalization equals a normalizing eager algorithm which just rewrites an encoded term lazily, it is Turing complete.
QED?
No comments:
Post a Comment