Register Machine Model of Computation: Difference between revisions

The next significant model to arise was the ''[https://en.wikipedia.org/wiki/Lambda_calculus lambda calculus]'', created by Alonzo Church in 1935. This was a simpler model of functions than the existing type of recursive function theory, but was demonstrated to have the same computational power as RFT. Church postulated that this these two models were, in fact, as complete as any sequential model could ever be.

 

 

The Turing Machine, in its basic form as described in the paper "[https://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf On Computable Numbers, with an Application to the ''Entscheidungsproblem'']", is thought of as a machine consisting of a tape read/writer and an infinitely long paper tape divided into cells containing data - one can think of the cells as boxes drawn on the tape to mark where a particular datum was. For each operation, the Turing Machine would position itself over a cell, read the datum in the cell, and based on that datum, decide whether to write a datum in a cell (whether the same one or a different one), move to another cell, or stop running and eject the tape in its current state as its final output. In his paper, he initially described each machine having a fixed set of responses to the data, stored separately in an ''action table'', and a fixed set of states which the data could put it into. He then proceeded