Talk:XOṘ Mạchịne

From Esolang
Jump to navigation Jump to search

Proof of Incompleteness

XOṘ Mạchịne cannot produce the Or function.

There are six possible command pairs:

  • a1
  • b1
  • ab
  • ba
  • aa
  • bb

Consider the effects of these on the pair of values (a,b). The first four are reversible, and can make any two input reversible logic gate. The last two map two pairs of values to the same value, and the other pairs to another value.

The final step, outputting 1 iff a > b, maps one pair to 1, namely (1,0), and all other pairs to 0. This means that if only a1, b1, ab, ba, are used, we must produce a Boolean function with a single True output. If we add in aa, bb, we can construction Boolean functions with 0,2, or 4 True outputs, but 3 is impossible. This is since once we reach an aa, or bb, command pair, the possible (a,b) inputs get paired up and there is no way to seperate 3 values from the 4th one. --(this comment by Eric-D-Culver at 21:25, July 15, 2020‎ UTC; please sign your comments with ~~~~)

Retrieved from "https://esolangs.org/w/index.php?title=Talk:XOṘ_Mạchịne&oldid=79587"