原文
原始链接: https://news.ycombinator.com/item?id=41115941
在本文中,作者讨论了图灵机(阿兰·图灵提出的一种计算模型)的概念,以及它如何模拟各种动态系统。 他们首先解释说,图灵机由有限字母表、有限内部状态集和磁带组成,磁带可以是无限的,也可以是有限的。 磁带按照一定的规则运行,在机器头的控制下,允许符号沿着磁带进行读/写和移动,代表机器在与磁带交互时的内部状态。 接下来,作者定义了两个动态系统之间的模拟,指出如果动态系统“A”各自的空间之间存在保留两个系统行为的注入映射,则动态系统“A”将模拟另一个动态系统“B”。 然后,他们证明了有限动态系统可以通过磁带长度为 1 的特定图灵机来模拟。然而,他们声称通用图灵机的传统概念能够使用描述的模拟方法来模拟任何其他图灵机。 由于所述模拟方法的强大性质,较早的说法可能是不正确的。 为了解决这个问题,作者引入了修改后的模拟定义,仅考虑非空结果而不是精确匹配。 接下来,他们扩展了图灵机的原始定义,结合了基于定义的结果函数生成结果的能力,从而得出了图灵机通用性和有限弱通用性的新形式定义。 最后,他们提出有限的弱普遍性可能捕捉到计算概念的一个重要方面,但建议需要进一步的研究来探索这一假设。
First of all, recall that a dynamical system is a set X with a map f: X -> X. The evolution of the system is given by the iterated application of f. A dynamical system is finite if the set X is finite.
I think it is useful to broaden this concept and define an IO-system as three sets X and I and O with a map f: I × X -> O × X. This means at every evolution step an "input" value i ∈ I has to be provided and an "output" value o ∈ O is obtained.
A Turing machine m consists of a finite alphabet A of symbols and a finite IO-system h: A × S -> O × S, where O = {move left, move right, print symbol a ∈ A}. This represents how the "head" of the Turing machine updates its internal state s ∈ S when reading a symbol from the alphabet I. We call this IO-system h the head of the Turing machine. You could specify the Turing machine with the data T = (A, S, O, h).
You now couple this Turing machine with another IO-system, which we call the "tape". It is either an infinite (N = ∞) tape or a finite, circular tape of length N. It has states X = {1, ..., N} × I × ... × I where the product I × ... × I has length N. It's set of inputs is the set O and its set of outputs is A. It's operation is given by a function t: O × X -> A × X, which describes the intended reaction of the type to the instructions from the head, i.e. depending on the instruction in O it either moves the "position counter" of the tape to the left, to the right, or it prints a symbol onto the tape. After it has performed this it reads the symbol at the current position and gives this output back to the head.
We can now combine the head h and the tape t into a "machine" dynamical system m: X × S × O -> X × S × O where h(x, s, o) = (t(o, x)_X, h(t(o, x)_A, s)_S, h(t(o, x)_A, s)_O). This represents the evolution of the Turing machine together with the tape. We call this the [machine dynamicals system with memory N of the Turing machine T].
Definition 1. Let's say that [the dynamical system f: X -> X simulates another dynamical system g: Y -> Y] if there exists an injective map u: Y -> X such that g(y) = f(u(y)). In order to compute the evolution g(g(...(g(y))...)) we can instead compute f(u(f(u(...(f(u(y))...)) and use injectivity of u to get back a result in Y.
Lemma 2. Any finite dynamical system is simulated by the machine dynamical system of some Turing machine with tape length N = 1. proof: Just set the head of the Turing machine to be the desired dynamical system and trivialize all the other objects.
This is a triviality result and tells us that this is not a good attempt to investigate universality of Turing machines in a "finite memory" setting.
False Hypothesis 3. There exists a universal Turing machine U in the sense that this Turing machine has the property that its machine dynamical system with infinite memory simulates the machine dynamical system with infinite memory of any other Turing machine T.
As far as I know this hypothesis is false because the sense of simulation mentioned above is far too strong. At this point I think there are many definitions one can make so let's stick with the one of Alan Turing.
Definition 4. We say that [the dynamical system f: X -> X simulates another dynamical system g: Y -> Y with respect to the "result" functions R: X -> {null, 0, 1} and Q: Y -> {null, 0, 1}] if there exists an injective map u: Y -> X such that the sequences Q(g^n(y)) and R((f ∘ u)^n(y)) are "result equivalent", meaning they are equal if you delete all instances of "null".
We now extend the concept of a Turing machine T by adding to it a result function r: O -> {null, 0, 1}.
Definition 5 (A. Turing, 1936). We say that [the Turing machine T with result function r: O -> {null, 0, 1} (N,M)-simulates another Turing machine T' with result function r': O' -> {null, 0, 1}] if the machine dynamical system of T with memory N simulates the machine dynamical system of T' with memory M, with respect to the result functions R: X × S × O -> {null, 0, 1} given by R(x, s, o) = r(o) and R': X' × S' × O' -> {null, 0, 1} given by R'(x, s, o) = r'(o).
Definition 6. We say that [a Turing machine U with result function r is (N,M)-universal] if it (N,M)-simulates any other Turing machine with result function.
Theorem 7 (A. Turing, 1936). There exists a (∞,∞)-universal Turing machine.
Definition 8. We say that [a Turing machine U with result function r is finite-weakly universal] if for any finite M there exists some finite N such that it (N,M) simulates any other Turing machine with result function.
Now it gets difficult becasue I don't actually know the answers anymore. I am pretty sure that any (∞,∞)-universal Turing machine is also finite-weakly universal. Even more so, it might be the case that finite-weak universality is equivalent to (∞,∞)-universality. Most certainly finite-weak universality is not a trivial concept and captures an interesting aspect of the concept of computation. I want to make the point that in my opinion infinite memory should not be seen as requirement in order to talk about these concepts of computation like Turing machines and universality.
It is also unclear how exactly to define the "Turing completeness" of a system, as I don't think there exists a definition of Turing completeness for dynamical systems. You have to specify how you are allowed to put an input into the dynamical system at least. I think that in some sense one could use what OP found and prove a rigorous result that with `find` + `mkdir` one can somehow construct a finite-weakly universal Turing machine.