Skip to Main Content
计算机科学导论:跨学科方法
book

计算机科学导论:跨学科方法

by 罗伯特 塞奇威克, 凯文 韦恩
August 2021
Beginner to intermediate content levelBeginner to intermediate
450 pages
19h
Chinese
Pearson
Content preview from 计算机科学导论:跨学科方法

5.3 普遍性

图灵机模型本质上是一个数学作品,它将有关计算的基本数学概念简化,以使我们可以得出精确结论。这项工作的基础是由图灵在他最初的论文里提出来的,但随后学者们不断地发展,直到今天我们被各种计算设施所包围,都有赖于图灵机模型得出的这些结论。图灵机有如此巨大的影响力,我们所有从事于计算的人(当然,也包括本书的读者)都有必要对其有个基本理解。在本节中,我们试图讲解图灵在那篇论文中提出的两个基本概念:一是一台通用目的的计算机可以进行任何计算;二是假设所有计算设备本质上是等价的。

算法 当我们写一个计算机程序时,我们通常是在设计一种可以解决某个问题的方法。这个方法必须依赖于程序环境,或者这个方法适用于很多环境。正是方法,而不是程序本身,带领我们一步步地解决问题。在计算机理论中,名词“算法”(algorithm)用来描述实现计算机程序中有限的、确定的、有效地解决问题的办法。算法是计算机科学理论中的核心领域。

在本书中,我们已经学习了很多算法,比如牛顿定理、欧几里得定理、归并排序、广度优先搜索等。这里给出的定义虽然不够严谨,但也足够说明这个概念。图灵机给数学家们带来了这个概念,并可用于数学证明。在这里,我们关注于这些重要的思路,而不再停留于定义及其完整版证明。

可判定性。假设我们在纸带上输入一个字符串并将一个图灵机处于启动状态,有四种可能的结果。该机器可能:

·停在标有“YES”的状态(接受输入字符串)。

·停在标记为“NO”的状态(拒绝输入字符串)。

·停在标有“H”的状态(停止,不再接受或拒绝)。

·以上都不是(进入无限循环)。

目前,当机器停机时(或处于无限循环中),我们会忽略纸带前后的内容。我们说一个图灵机识别某个语言,是指图灵机以这个语言的所有可能的字符串作为输入时,都会引导机器最终走到接受状态。同时,对于所有不在所识别的语言中的输入字符串,图灵机都会停止运行(终止于标记为“NO”或“H”的状态),那么我们就说这个图灵机可以判定(decide)该语言。对于每一个输入字符串,这个图灵机必须都能停机并且给出正确的答案。例如,我们在前一节末尾设计的二进制频率计数器图灵机能够判定(和识别)所有a和b数量相同的二进制字符串。注意:对于DFA,当DFA总是停止时,我们不需要区分判定和识别。 ...

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.
Start your free trial

You might also like

数据科学之编程技术:使用R进行数据清理、分析与可视化

数据科学之编程技术:使用R进行数据清理、分析与可视化

迈克尔 弗里曼, 乔尔 罗斯
C语言核心技术(原书第2版)

C语言核心技术(原书第2版)

Peter Prinz, Tony Crawford

Publisher Resources

ISBN: 9787111641414