Pei Yan Ru, Traversa Fabio L, Di Ventra Massimiliano
IEEE Trans Neural Netw Learn Syst. 2019 Jun;30(6):1610-1620. doi: 10.1109/TNNLS.2018.2872676. Epub 2018 Oct 31.
Universal memcomputing machines (UMMs) represent a novel computational model in which memory (time nonlocality) accomplishes both tasks of storing and processing of information. UMMs have been shown to be Turing-complete, namely, they can simulate any Turing machine. In this paper, we first introduce a novel set theory approach to compare different computational models and use it to recover the previous results on Turing-completeness of UMMs. We then relate UMMs directly to liquid-state machines (or "reservoir-computing") and quantum machines ("quantum computing"). We show that UMMs can simulate both types of machines, hence they are both "liquid-" or "reservoir-complete" and "quantum-complete." Of course, these statements pertain only to the type of problems these machines can solve and not to the amount of resources required for such simulations. Nonetheless, the set-theoretic method presented here provides a general framework which describes the relationship between any computational models.
通用内存计算机器（UMMs）代表了一种新颖的计算模型，其中内存（时间非局部性）同时完成信息存储和处理两项任务。UMMs已被证明是图灵完备的，即它们可以模拟任何图灵机。在本文中，我们首先引入一种新颖的集合论方法来比较不同的计算模型，并使用它来恢复先前关于UMMs图灵完备性的结果。然后，我们将UMMs直接与液态机器（或“储层计算”）和量子机器（“量子计算”）联系起来。我们表明UMMs可以模拟这两种类型的机器，因此它们既是“液态完备”或“储层完备”的，也是“量子完备”的。当然，这些陈述仅适用于这些机器能够解决的问题类型，而不适用于此类模拟所需的资源量。尽管如此，这里提出的集合论方法提供了一个描述任何计算模型之间关系的通用框架。
