标签: turing-machines

"图灵完成"的含义是什么意思？

你可以给出一个简单的解释,而不会涉及太多的理论细节吗？

When have you ever personally come upon the halting problem in the field? This can be when a co-worker/boss suggested a solution which would violate the fundamental limits of computation, or when you realized yourself that a problem you were trying to solve was, in fact, impossible to solve.

我最近想出来的时候是研究类型检查器.我们班级意识到编写一个完美的类型检查器是不可能的(一个可以接受所有运行没有类型错误的程序,并拒绝所有运行类型错误的程序),因为这实际上可以解决暂停问题.另一个是当我们在同一个类中意识到在类型检查阶段不可能确定除法是否会出现零,因为检查一个数字在运行时是否为零,也是暂停问题的一个版本.

背景

的冯·诺依曼体系结构描述了指令和数据被存储在存储器中所存储的程序的计算机和机的工作原理,通过改变其内部状态,即,一个指令在某些数据进行操作,并修改数据.因此,系统中存在状态.

的图灵机体系结构的工作原理是在磁带上操纵符号.即存在具有无限数量的槽的带,并且在任何一个时间点,图灵机都在特定的槽中.根据在该插槽读取的符号,机器可以更改符号并移动到不同的插槽.所有这些都是确定性的.

问题

1. 这两个模型之间有什么关系吗？冯·诺伊曼模型是基于图灵模型还是受其启发？

2. 我们可以说图灵模型是Von Newman模型的超集吗？

3. 功能编程是否适合图灵模型？如果是这样,怎么样？我认为功能编程并不适合Von Neuman模型.

什么是图灵机,人们为什么一直提到它？我的IBM PC就是我完成计算所需要的!为什么有人关心这些机器？

我不理解非确定性图灵机的概念.我想我理解术语非确定性算法 :(非确定性算法是一种算法,可以在不同的运行中表现出不同的行为,而不是确定性算法.)所以算法可能是这样的:

a = fromSomeAlgo();

if(a > foo)
   stateA();
else
   stateB();

但是对于我读过的非确定性图灵机,它可以在给定时间处于多个状态.另外一篇维基百科文章暗示"非确定性图灵机(NTM),可能有一套规则,规定了针对特定情况的多个动作".

那是什么意思 ？..对于给定的情况,不止一个行动......多个州......我根本就不明白这一点.

在课堂上,我们了解了暂停问题,图灵机器,减少等等.许多同学都说这些都是抽象和无用的概念,而且知道它们并没有真正的意义(即,一旦课程结束,你就会忘记它们结束而不是失去任何东西).

为什么理论有用？你有没有在日常编码中使用它？

我正在听edX课程,教授强调每台能够执行这六个基本原语的机器都可以称为图灵完成.但六个基本原语是什么？

在阅读亚马逊上Stephen Wolfram的"新种科学"评论时,我发现了以下声明:

每个计算机科学(CS)学生都知道dovetailer,这是一个非常简单的2行程序,它系统地列出并执行通用计算机的所有可能程序,例如图灵机(TM).

有人能给出"简单的2线程序",说明"dovetaling"吗？

我真的在努力理解这两者之间的区别.从我的教科书中,它实质上描述了差异

如果语言是图灵可识别语言的补充,那么这种语言就是可识别的.

我想这个定义我不理解的部分是:当它是图灵识别语言的补充时它意味着什么？

你究竟如何确定它是否是另一种语言的补充？

好的,今天的目标是建立一个图灵机模拟器.对于那些不知道它是什么的人,请参阅维基百科文章.我们今天使用的状态表位于该页面的正式定义的末尾.

代码将采用一系列"0"和"1"字符串字符,一个表示机器开始的字符的整数,以及一个表示程序状态的整数(无特定顺序),并输出最终结果字符串上的操作,以及最终位置.例子:

例1:

1010 state A(0)
   ^ (3)
1011 state B(1)
  ^ (2)
1011 state B(1)
 ^ (1)
1111 state A(0)
  ^ (2)
1111 state C(0)
   ^ (3)
1111 HALT
  ^ (2)

例2:

110100 state B(1)
   ^ (3)
110100 state B(1)
  ^ (2)
111100 state A(0)
   ^ (3)
111100 state C(2)
    ^ (4)
111110 state B(1)
     ^ (5)
1111110 state A(0)
      ^ (6, tape has been extended to right)
1111111 state B(1)
     ^ (5)
1111111 state …