In this blog post I'm going to put parts of my Turing machine which is supposed to simulate D function of loader.c, and, eventually, whole machine. For such large project I've decided that it deserves separate blog post. Click here to check out my post where I analyse the whole program.

I've decided to make this blog post before actually finishing analysis, because I'm able to already implement Subst and Apply functions.

Overall structure

The whole idea of my implementation is to quite directly follow Loader's program. The tape is going to be divided into finitely many blocks of varying length. Each of blocks will be either used to compute Subst, Apply or Derive. The rightmost one of these blocks will be active, which means that at the moment we are computing the corresponding function. If the active block computes, say, Subst, and it makes a call to Apply function, then we create new block which will actually resolve the instance of Apply (note that the active block will change). When we finally get the answer, we remove the Apply block and get back to Subst block, which becomes active again, with the result of Apply function. Note that all blocks other than the active ones are idle - waiting for the answer. When the answer is ready, the block becomes active and can continue working. The leftmost block will be (ultimately) the one awaiting for the result of Derive(x).

Ad blocker interference detected!

Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.