We consider 2-state reversible gates that route tokens from input wires to output wires. This can be thought of as a model that reduces computation to just flow control, with wires representing execution paths, and the token representing the current execution point. Memory and computation are strictly co-localized, in the sense that the state of a gate is only changeable or observable by a token that passes through it. Also known as Reversible Logic Elements with Memory (RLEMs), such gates have been studied extensively by Kenichi Morita and his co-authors. Through a series of surprising results, they have shown that all non-degenerate 2-state RLEMs with 3 or more inputs are universal, meaning any of them can be used to build any other RLEM of any size and number of states. They also proved that all smaller (2 or fewer inputs) 2-state RLEMs are not universal, with the exception of one gate that defied analysis. This one remaining gate, known as 2-17, was conjectured to also be non-universal, but this has remained an open question since 2012. Here we resolve this open question by showing that this extremely simple gate is in fact universal. This makes it the smallest universal reversible gate, and we name it the Morita gate in honor of Morita’s extensive foundational work in this area.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

The Morita Gate is Universal

  • Matthew Cook,
  • Ethan Palmiere

摘要

We consider 2-state reversible gates that route tokens from input wires to output wires. This can be thought of as a model that reduces computation to just flow control, with wires representing execution paths, and the token representing the current execution point. Memory and computation are strictly co-localized, in the sense that the state of a gate is only changeable or observable by a token that passes through it. Also known as Reversible Logic Elements with Memory (RLEMs), such gates have been studied extensively by Kenichi Morita and his co-authors. Through a series of surprising results, they have shown that all non-degenerate 2-state RLEMs with 3 or more inputs are universal, meaning any of them can be used to build any other RLEM of any size and number of states. They also proved that all smaller (2 or fewer inputs) 2-state RLEMs are not universal, with the exception of one gate that defied analysis. This one remaining gate, known as 2-17, was conjectured to also be non-universal, but this has remained an open question since 2012. Here we resolve this open question by showing that this extremely simple gate is in fact universal. This makes it the smallest universal reversible gate, and we name it the Morita gate in honor of Morita’s extensive foundational work in this area.