Pointer Machine - Kolmogorov-Uspenskii Machine (KU-machine) Model

Kolmogorov-Uspenskii Machine (KU-machine) Model

KUM differs from SMM in allowing only invertible pointers: for every pointer from a node x to a node y, an inverse pointer from y to x must be present. Since outgoing pointers must be labeled by distinct symbols of the alphabet, both KUM and SMM graphs have O(1) outdegree. However, KUM pointers' invertibility restricts the in-degree to O(1), as well. This addresses some concerns for physical (as opposite to purely informational) realism, like those in the above van Emde Boas quote.

An additional difference is that the KUM was intended as a generalization of the Turing machine, and so it allows the currently "active" node to be moved around the graph. Accordingly, nodes can be specified by individual characters instead of words, and the action to be taken can be determined by a state table instead of a fixed list of instructions.

Read more about this topic:  Pointer Machine

Famous quotes containing the words machine and/or model:

    A multitude of little superfluous precautions engender here a population of deputies and sub-officials, each of whom acquits himself with an air of importance and a rigorous precision, which seemed to say, though everything is done with much silence, “Make way, I am one of the members of the grand machine of state.”
    Marquis De Custine (1790–1857)

    Socrates, who was a perfect model in all great qualities, ... hit on a body and face so ugly and so incongruous with the beauty of his soul, he who was so madly in love with beauty.
    Michel de Montaigne (1533–1592)