Daniel Karl I. Weidele, Hendrik Strobelt, et al.
SysML 2019
By a simple direct construction it is shown that computations done by Turing machines can be duplicated by a very simple symbol manipulation process. The process is described by a simple form of Post canonical system with some very strong restrictions. This system is monogenic: each formula (string of symbols) of the system can be affected by one and only one production (rule of inference) to yield a unique result. Accordingly, if we begin with a single axiom (initial string) the system generates a simply ordered sequence of formulas, and this operation of a monogenic system brings to mind the idea of a machine. The Post canonical system is further restricted to the “Tag” variety, described briefly below. It was shown in [1] that Tag systems are equivalent to Turing machines. The proof in [1] is very complicated and uses lemmas concerned with a variety of two-tape nonwriting Turing machines. The proof here avoids these otherwise interesting machines and strengthens the main result; obtaining the theorem with a best possible deletion number P = 2. Also, the representation of the Turing machine in the present system has a lower degree of exponentiation, which may be of significance in applications. These systems seem to be of value in establishing unsolvability of combinatorial problems. © 1964, ACM. All rights reserved.
Daniel Karl I. Weidele, Hendrik Strobelt, et al.
SysML 2019
C.A. Micchelli, W.L. Miranker
Journal of the ACM
Wang Zhang, Subhro Das, et al.
ICASSP 2025
Arnon Amir, Michael Lindenbaum
IEEE Transactions on Pattern Analysis and Machine Intelligence