我读了很多关于图灵机的东西并了解它是如何工作的，但是我无法掌握（而且似乎没有一本书试图教的）是我应该如何解决我要解决的问题？我的意思是：例如，检查一个单词是否是回文，由我正在学习的书中的 11 个状态组成。就我目前的知识水平而言，至少可以说，仅仅坐在一张空纸上并想出所有这些状态似乎几乎是不可能的。当我尝试做这样的事情时，我立即卡住了，因为我不知道我应该怎么做才能让这些状态以某种方式“一起”工作。我在编程时没有这样的问题，但是在这里，我只是不知道应该如何处理由一些 n-teen 状态组成的东西。你能给我一些学习的方向吗？
问问题
120 次
1 回答
0
图灵机是一种架构模型，与冯诺依曼机器相距不远。因此，它是一个非常低级的计算模型，使用它们解决编程问题的最佳方法是使用与传统硬件相同的技术，即通过抽象。
人们认为图灵机不是组合式的，但事实并非如此。将图灵机实现顺序组合、条件和循环的转换功能结合起来并不难。然后，从一个执行字符比较、字符交换和类似操作的基本机器的小型库开始，您可以构建非常复杂的程序。
我们使用这种技术编写了通用图灵机，并在 Matita Proof Assistant（类似于 Coq 的系统）中证明了它的正确性。参考是：
Asperti, Ricciotti “多磁带图灵机的形式化”，TCS 603，2015。
于 2017-02-01T13:09:58.570 回答