There is a definition of a 'monotone machine' in Li & Vitany's Book, and another one which is for example stated in this paper via c.e. (computably enumerable) sets. I can't see why these definitions should be equivalent.
Furthermore in Li & Vitany's book, there is a statement which says that monotone machines compute p.r. (primitive recursive) functions f with $f(x) \le f(y)$ when $x \le y$ (lexicographical ordering).
I don't see how such a function can be computed by a monotone machine.

Maybe someone can explain this to me or refer to a paper / book which descripes these connections.


The first definition: A monotone machine has a one-way read-only input tape, a one-way write-only output tape and work tapes. The input is read one bit at a time, and the output written one bit at a time, with the one-way nature of the output tape allowing no revisions. For such a machine M, we have M(x) terminates with output y, where x is a finite string and y is a possibly infinite string, if either M halts after reading the bits of x from the input tape and y is what is on the output tape at that point, or M computes forever after reading exactly the bits of x, and y is on the output tape on the limit.

The second one: A monotone machine L is a c.e. (computably enumerable) set of pairs of finite strings such that if , is in L and $x \le x'$ then $y$ and $y'$ are comparable (i.e. $y \le y'$ or $y' \le y$).

  • 2
    $\begingroup$ I'm sure anyone responding to this question will recognize this, but to clarify things for the casual viewer, it is not the lexicographic ordering that is being referred to but rather a prefix ordering: $x \preceq y$ iff $x$ is an initial segment of $y$. EDIT: After rereading Li & Vitanyi's monotone machine definition (I'm looking at the 2nd edition), it seems like they misspoke and described a prefix machine instead of a monotone machine. I suspect they mean to say that M(x) = y if y is what has been output just before the next input tape symbol is read. $\endgroup$
    – Kurt
    Commented Oct 1, 2010 at 4:39

1 Answer 1


When we say that a monotone machine is a set $L$ of pairs of strings $(x,y)$, the first component $x$ is the part of the input tape being read in order to produce the output $y$.

This set is c.e. (computably enumerable) because we can run computations with all (finite parts of) oracles in parallel, and watch for pairs $(x,y)$ where this happens.

The condition that if $(x,y)\in L$, $(x',y')\in L$ and $x\preceq x'$ then $y\preceq y'$ or $y'\preceq y$ just says that we have consistency, i.e., if you see more of the input bits you can't go back and say that you now outputted something different on an earlier input after all.

Conversely, given such a c.e. set we can produce a machine that monitors the c.e. set $L$ and looks for pairs $(x,y)$ entering $L$, and checks whether $x$ is a prefix of what's on the input tape given to the machine. If so, it extends its output string to $y$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.