Get the latest tech news
Right to Left Computability (2020)
Written 2020-11-21 Tags:Computability A TheoremIn the book Hacker's Delight, Henry S. Warren, Jr states A function mapping words to words can be implemented with word-parallel add, subtract, and, or, and not instructions if and only if each bit of the result depends only on bits at and to the right of each input operand.
Now that we have the full set of binary operations, and a mechanism to shift inputs to the left by a constant number of bits, we can build any right-to-left computable function. IO As a convenience to get data in and out of the machine, we add INPUT and OUTPUT instructions, which are likely connected to some human-facing console or UNIX pipe. Initially I considered some instructions like branch-if-greater-than, but this may require evaluating the entire infinite bit-string, and only works for a handful of cases.
Or read this on Hacker News