不过有个人提到的 Random-access stored-program machine 挺有趣

@没有人 楼主认为不能修改输入，那肯定是不能 O(1) 实现的
下面回复的人认为可以先修改输入，之后再修改回来，所以认为楼主是错的
所以他们的讨论就是在瞎扯 233

reference 1
reference 2

From this post

What is the connection of Turing-complete Language and Universal Turing Machine.
Anybody any idea?
Some discussion on stackexchange.

for example:
$\{a^ib^jc^k|i=j \text{ or } j=k \text{ where i,j,k}\ge0\}$
I'm the proof (in the last page)

（期末了，该预习编译原理了2333）

Colloquially, we say that "finite automata cannot count," meaning that
a finite automaton cannot accept a language like $\{a^nb^n|n\ge1\}$ that would
require it to keep count of the number of a ' s before it sees the b's.
Likewise, "a grammar can count two items but not three," as we shall see when we consider non-context-free language constructs in Section 4.3.5.

a grammar can not count three items:
a non-CFG: $\{a^nb^nc^n|n\ge1\}$

所以争议在于对“等价”的理解上？

然后这几个计算模型的区别，我觉得主要要侧重于
unlimited memory
unrestricted access
（ITOC 上的说法）
就是在他们的计算模式上
然后联系现实中的计算机，在计算模式上，现实计算机跟 TM 一样具有 unrestricted access ，所以一般认为这两者关系更强，
unlimited memory 只有在输入是无限长时才会有意义吧？然后现实中的输入肯定不会无限长啊，所以我们只需要足够长，所以才会有后面的计算复杂性，怎样子的“足够”？怎样才“足够”

我觉得在很多地方都没有严谨说清楚，讨论有很多误会，比如，在“状态”的语义上有歧义
一方认为是语文上的“状态”，即包含了一台机器所有描述，所以要包含栈（磁带）上的内容
另一方认为是课本严谨定义上的“状态”，所以是不包含栈（磁带）上的内容