更改

跳到导航 跳到搜索
删除15字节 、 2021年7月28日 (三) 17:58
第673行: 第673行:     
# 凡是真正的计算机能计算的东西,图灵机也能计算。例如,"图灵机可以模拟编程语言中的任何类型的子程序,包括递归程序和任何已知的参数传递机制"(Hopcroft and Ullman 第157页)。一个足够大的FSA也可以模拟任何真正的计算机,而不用考虑IO。因此,关于图灵机的局限性的说法也将适用于实际计算机。
 
# 凡是真正的计算机能计算的东西,图灵机也能计算。例如,"图灵机可以模拟编程语言中的任何类型的子程序,包括递归程序和任何已知的参数传递机制"(Hopcroft and Ullman 第157页)。一个足够大的FSA也可以模拟任何真正的计算机,而不用考虑IO。因此,关于图灵机的局限性的说法也将适用于实际计算机。
  −
  −
  −
   
# 区别只在于图灵机有能力处理无限制的数据量。然而,在有限的时间内,图灵机(像实际的机器)只能操纵处理的数据量。
 
# 区别只在于图灵机有能力处理无限制的数据量。然而,在有限的时间内,图灵机(像实际的机器)只能操纵处理的数据量。
  −
   
# 像图灵机一样,实际的机器可以根据需要,通过获得更多的磁盘或其他存储介质,扩大其存储空间。
 
# 像图灵机一样,实际的机器可以根据需要,通过获得更多的磁盘或其他存储介质,扩大其存储空间。
  −
  −
   
# 使用较简单的抽象模型对真机程序的描述往往比使用图灵机的描述要复杂得多。例如,描述算法的图灵机可能有几百个状态,而给定实际机器上的等效确定性有限自动机(deterministic finite automaton,DFA)却有四千亿个状态。这使得DFA的表示方式无法分析。
 
# 使用较简单的抽象模型对真机程序的描述往往比使用图灵机的描述要复杂得多。例如,描述算法的图灵机可能有几百个状态,而给定实际机器上的等效确定性有限自动机(deterministic finite automaton,DFA)却有四千亿个状态。这使得DFA的表示方式无法分析。
  −
  −
   
# 图灵机描述的算法与它们使用的内存多少无关。目前任何机器所拥有的内存都有一个极限,但这个极限可以在时间上任意上升。图灵机允许我们对算法做出声明,这些声明(理论上)将永远成立,而不考虑传统计算机架构的进步。
 
# 图灵机描述的算法与它们使用的内存多少无关。目前任何机器所拥有的内存都有一个极限,但这个极限可以在时间上任意上升。图灵机允许我们对算法做出声明,这些声明(理论上)将永远成立,而不考虑传统计算机架构的进步。
  −
  −
   
# 图灵机简化了算法的表述。在图灵机上运行的算法通常比在实际机器上运行的算法更通用,因为它们有任意精度的数据类型可用,而且永远不必处理意外情况(包括但不限于内存耗尽)。
 
# 图灵机简化了算法的表述。在图灵机上运行的算法通常比在实际机器上运行的算法更通用,因为它们有任意精度的数据类型可用,而且永远不必处理意外情况(包括但不限于内存耗尽)。
  
150

个编辑

导航菜单