Home About us Products Services Contact us Bookmark
:: wikimiki.org ::
计算机科学

计算机科学

计算机科学是一门包含各种各样与计算和信息处理相关主题的系统学科，从抽象的算法分析、形式化语法等等，到更具体的主题如编程语言、程序设计、软件和硬件等。作为一门学科，它与数学、计算机程序设计、软件工程和计算机工程有显著的不同，却通常被混淆，尽管这些学科之间存在不同程度的交叉和覆盖。 计算机科学研究的课题是：
- 计算机程序能做什么和不能做什么（可计算性）；
- 如何使程序更高效的執行特定任務（算法和复杂性理论）；
- 程序如何存取不同类型的数据（数据结构和数据库）；
- 程序如何显得更具有智能（人工智能）；
- 人类如何与程序沟通（人机互动和人机界面）。 计算机科学的大部分研究是基于“冯·诺依曼计算机”和“图灵机”的，它们是絕大多數实际机器的计算模型。作为此模型的开山鼻祖，邱奇-图灵论题（Church-Turing Thesis）表明，尽管在计算的时间，空间效率上可能有所差异，现有的各种计算设备在计算的能力上是等同的。尽管这个理论通常被认为是计算机科学的基础，可是科学家也研究其它种类的机器，如在实际层面上的并行计算机和在理论层面上概率计算机、oracle 计算机和量子计算机。在这个意义上来讲，计算机只是一种计算的工具：著名的计算机科学家 Dijkstra 有一句名言“计算机科学并不只是关于计算机的，正如天文学并不只是关于望远镜一样”。 计算机科学根植于电子工程、数学和语言学，是科学、工程和艺术的结晶。它在20世纪最后的三十年间兴起成为一门独立的学科，并发展出自己的方法与术语。 早期，虽然英国的剑桥大学和其他大学已经开始教授计算机科学课程，但它只被视为数学或工程学的一个分支，并非独立的学科。剑桥大学声称有世界上第一个传授计算的资格。世界上第一个计算机科学系是由美国的普渡大学在1962年设立，第一个计算机学院於1980年由美国的东北大学设立。现在，多数大学都把计算机科学系列为独立的部门，一部分将它与工程系、应用数学系或其他学科联合。 计算机科学领域的最高荣誉是ACM设立的图灵奖，被誉为是计算机科学的诺贝尔奖。它的获得者都是本领域最为出色的科学家和先驱。华人中首获图灵奖的是姚期智先生.他于2000年以其对计算理论做出的诸多“根本性的、意义重大的”贡献而获得这一崇高荣誉。

计算机系统

计算机系统可划分为软件系统与硬件系统两大类。

硬件


- 结构控制和指令系统
- 算法和逻辑结构
- 存储器结构
  - 冯·诺伊曼结构
  - 哈佛结构
- 输入/输出和数据通信
- 数字逻辑
- 逻辑设计
- 集成电路

计算机系统组织


- 计算机系统结构
- 计算机网络
  - 分布式计算
  - 网络安全
- 计算机系统实现

软件


- 系统软件
  - 操作系统
  - 编译器
- 应用软件
  - 计算机游戏
  - 办公自动化
  - 网络软件
  - CAD软件
- 计算机程序
  - 程序设计和程序设计实践
  - 面向对象技术
  - 程序设计语言
- 软件工程
  - 软件复用
  - 驱动程序
  - 计算机模拟
  - 程序设计方法学

数据和信息系统


- 数据结构
- 数据存储表示
- 数据加密
- 数据压缩
- 编码与信息论
- 文件
- 信息系统
  - 管理信息系统
  - 决策支持系统 - 专家系统
  - 数据库
  - 信息存储和数据存取
  - 信息交互与表达

主要的研究领域

形式化基础


- 逻辑学
  - 谓词逻辑
  - 模态逻辑
  - 时序逻辑
  - 描述逻辑
- 数学
  - 泛代数
  - 递归论
  - 模型论
  - 概率论和数理统计
  - 逻辑代数
    - 布尔代数
  - 离散数学
    - 组合数学
    - 图论
      - 网论
  - 信息论

理论计算机科学


- 形式语言
- 自动机
- 可计算性
- 算法
- 计算复杂性
- 描述复杂性
- 编译器
- 程序设计理论
- 信息论
- 类型理论
- 指称语义
- 微程序
- 遗传算法
- 并行计算

计算方法学


- 人工智能
- 计算机图形学
- 图像处理与计算机视觉
- 模式识别
  - 语音识别
  - 文字识别
  - 签名识别
  - 人脸识别
  - 指纹识别
- 仿真与建模
- 数字信号处理
- 文档与文本处理

计算机应用


- 数值计算
  - 数值分析
  - 定理机器证明
  - 计算机代数
  - 工程计算
    - 计算机化学
    - 计算机物理
    - 生物信息论
    - 计算生物学
- 非数值计算
  - 工厂自动化
  - 办公室自动化
  - 人工智能
  - 信息存储与检索
  - 符号语言处理
  - 计算机辅助科学
    - 计算机辅助设计
    - 计算机辅助教学
    - 计算机辅助管理
    - 计算机辅助软件工程
    - 机器人学
    - 多媒体技术
    - 人机交互
    - 电子商务

特定技术


- 测试基准
- 机器视觉
- 数据压缩
- 设计模式
- 数字信号处理
- 文件格式
- 信息安全
- 国际互联网络
- 超大规模集成电路设计
- 网络传输协议
- 网络处理器技术
- 整数运算器
- 浮点运算器
- 矩阵运算处理器
- 网格

计算科学史


- 计算机历史
- 软件业历史
- 编程思想

相关学科

计算机科学与另外的一些学科紧密相关。这些学科之间有明显的交叉领域，但也有明显的差异。
- 信息科学 - 软件工程 - 信息系统 - 计算机工程 - 信息安全 - 密码学 - 数学 - 工程学 - 语言学 - 逻辑学

卓越的先驱者


- 艾伦·图灵

参见


- 计算机科学课程列表
- 计算机科学家
- 图灵奖
- 冯·诺依曼奖
- 中国计算机产业
- 中国计算机科学大事年表
- 程序设计语言列表
- 操作系统列表
- ASCII艺术

外部链接

ko:컴퓨터 과학 ja:情報工学 simple:Computer Science th:วิทยาการคอมพิวเตอร์ Category:自然科学 Category:技术科学

计算

Originally, the word computing was synonymous with counting and calculating, and a science that deals with the original sense of computing mathematical calculations. The following definition of computing is given in the ACM report [http://portal.acm.org/citation.cfm?id=63238.63239 Computing As a Discipline]:
The discipline of computing is the systematic study of algorithmic processes that describe and transform information: their theory, analysis, design, efficiency, implementation, and application. The fundamental question underlying all the computing is 'What can be (efficiently) automated?'

科学与理论


- 计算机科学
- 计算理论
- Computational models
- DBLP, as of October 2005, now lists over 675 000 bibliographic entries on computer science and several thousand links to the home pages of computer scientists
- 科学计算

硬件

See information processor for a high-level block diagram.
- 计算机硬件
- 计算机硬件设计
- 计算机网络
- 计算机系统
- 计算机硬件历史

Instruction-level taxonomies

After the commoditization of memory, attention turned to optimizing CPU performance at the instruction level. Various methods of speeding up the fetch-execute cycle include:
- designing instruction set architectures with simpler, faster instructions: RISC as opposed to CISC
- Superscalar instruction execution
- VLIW architectures, which make parallelism explicit

软件


- 软件工程
- 计算机编程
- 软件专利

计算机历史


- History of computing hardware from the tally stick to the quantum computer
- Punch Card
- Unit record equipment
- IBM 700/7000 series
- IBM 1400 series
- System/360
- Early IBM disk storage

商用计算机


- Accounting software
- Computer-aided design
- Computer-aided manufacturing
- Computer-assisted dispatch
- Customer relationship management
- Data warehouse
- Decision support system
- Electronic data processing
- Enterprise resource planning
- Geographic information system
- Management information system
- Material requirements planning
- Strategic enterprise management
- Supply chain management
- Product Lifecycle Management
- Utility Computing

人的因素


- Accessible computing
- Human-computer interaction

计算机安全


- Cryptology - cryptography - information theory
- Cracking - demon dialing - Hacking - war dialing - war driving
- Social engineering - Dumpster diving
- Physical security - Black bag job
- Computer insecurity
- Computer surveillance
- defensive programming
- malware
- security engineering

数据

数字数据


- integral data types - bit, byte, etc.
- real data types:
  - Floating point (Single precision, Double precision, etc.)
  - Fixed point
  - Rational number
- Decimal
  - Binary-coded decimal (BCD)
  - Excess-3 BCD (XS-3)
  - Biquinary-coded decimal
- representation: Binary - Octal - Decimal - Hexadecimal (hex)
- Computer mathematics - Computer numbering formats -

字符数据


- storage: Character - String - Text - Plain text
  - representation: ASCII - Unicode - Multibyte - EBCDIC (Widecharacter, Multicharacter) - Fieldata - Baudot

其他专题


- 数据压缩
- 数字信号处理
- 图像处理
- 索引
- 数据管理

Mechatronics


- Punch card
- Key punch
- Unit record equipment

计算机分类


- Analog computer
- Calculator
- Desktop computer
- Desknote
- Digital computer
- Embedded computer
- Home computer
- Laptop
- Mainframe
- Minicomputer
- Microcomputer
- Personal computer
- Personal digital assistant (aka PDA, or Handheld computer)
- Server
- Supercomputer
- Tablet PC
- Video game console
- Workstation

当前的公司


- Apple Computer
- Avaya
- Dell
- Fujitsu
- Gateway Computers
- Groupe Bull
- Hewlett-Packard
- Hitachi, Ltd.
- IBM
- Microsoft
- NEC Corporation
- NetCB
- Novell
- Red Hat
- Silicon Graphics
- Sun Microsystems
- Unisys

历史上的公司


- Acorn, bought by Olivetti
- Bendix Corporation
- Burroughs, merged with UNIVAC to become Unisys
- Compaq, bought by Hewlett-Packard
- Control Data
- Cray
- Data General
- DEC, bought by Compaq, in turn bought by Hewlett-Packard
- Digital Research - a software company for the early microprocessor-based computers
- English Electric
- Ferranti
- General Electric, computer division bought by Honeywell, then Bull
- Honeywell, computer division bought by Bull and
- ICL
- Leo
- Lisp Machines, Inc.
- Marconi
- Nixdorf, bought by Siemens
- Olivetti
- Osborne
- Packard Bell
- Raytheon
- Royal McBee
- RCA
- Scientific Data Systems, sold to Xerox
- Siemens
- Sinclair Research, created the ZX Spectrum, ZX80 and ZX81
- Symbolics
- UNIVAC, merged with Burroughs to become Unisys
- Varian
- Wang

专业组织


- Association for Computing Machinery (ACM)
- British Computer Society (BCS)
- Association for Survey Computing (ASC)
- Institute of Electrical and Electronics Engineers (IEEE), in particular the IEEE Computer Society
- Institution of Electrical Engineers
- International Electrotechnical Commission (IEC)

Standards organizations and consortia

(see also standardization)
- International Electrotechnical Commission (IEC)
- International Organization for Standardization (ISO)
- Institute of Electrical and Electronics Engineers (IEEE)
- Internet Engineering Task Force (IETF)
- World Wide Web Consortium (W3C)

杂项


- List of computer term etymologies
- Load (computing)
- Indian Language Computing Category:计算 ja:コンピューティング

算法

Category:代数 Category:算法 算法是指完成一个任务所需要的具体步骤和方法。也就是说给定初始状态或输入数据，经过计算机程序的有限次运算，能够得出所要求或期望的终止状态或输出数据。 算法常常含有重复的步骤和一些比较或逻辑判断。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。

算法的历史

“算法”的中文名稱出自周髀算經；而英文名稱 Algorithm 来自于9世纪波斯数学家比阿勒·霍瓦里松的名字al-Khwarizmi，因為比阿勒·霍瓦里松在数学上提出了算法这个概念。“算法”原为"algorism"，意思是阿拉伯数字的运算法则，在18世纪演变为"algorithm"。 第一次编写算法是Ada Byron于1842年为巴贝奇分析机编写求解解伯努利方程的程序，因此Ada Byron被大多数人认为是世界上第一位程序员。因为巴贝奇(Charles Babbage)未能完成他的巴贝奇分析机，这个算法未能在巴贝奇分析机上执行。 因为"well-defined procedure"缺少数学上精确的定义，19世纪和20世纪早期的数学家、逻辑学家在定义算法上出现了困难。20世纪的英国数学家图灵提出了著名的图灵论题，并提出一种假想的计算机的抽象模型，这个模型被称为图灵机。图灵机的出现解决了算法定义的难题，图灵的思想对算法的发展起到了重要的作用。

算法的特征

#输入，一个算法必须有零个或多个输入量。 #输出，一个算法应有一个或多个输出量，输出量是算法计算的结果。 #确定性，算法的描述必须无歧义，以保证算法的执行结果是确定的。 #有穷性，算法必须在有限步骤内实现。注：此处“有限”不同于数学概念的“有限”，天文数字般的有限对于实际问题并无意义。 #有效性（亦称可行性），能够实现，算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现。

形式化算法

算法是计算机处理信息的本质，因为计算机程序本质上是一个算法来告诉计算机确切的步骤来执行一个指定的任务，如计算职工的薪水或打印学生的成绩单。 一般地，当算法在处理信息时，会从输入设备或数据的存储地址读取数据，把结果写入输出设备或某个存储地址供以后再调用。

算法的复杂度

算法的时间复杂度

算法的时间复杂度是指算法需要消耗的时间资源。一般来说，计算机算法是问题规模n的函数f（n），算法的时间复杂度也因此记做 T（n）=O（f（n）） 因此，问题的规模n越大，算法执行的时间的增长率与f（n）的增长率正相关，称作渐进时间复杂度（Asymptotic Time Complexity）。

算法的空间复杂度

算法的空间复杂度是指算法需要消耗的空间资源。其计算和表示方法与时间复杂度类似，一般都用复杂度的渐近性来表示。同时间复杂度相比，空间复杂度的分析要简单得多。

非確定性多項式時間(NP)

算法的实现

算法不单单可以用计算机程序来实现，也可以在神经网络、电路或者机械设备上实现。

例子一

这是算法的一个简单的例子。 我们有一串随机数列。我们的目的是找到这个数列中最大的数。如果将数列中的每一个数字看成是一颗豆子的大小,可以将下面的算法形象地称为“捡豆子”： # 首先将第一颗豆子放入口袋中。 # 从第二颗豆子开始检查，直到最后一颗豆子。如果正在检查的豆子比口袋中的还大，则将它捡起放入口袋中，同时丢掉原先口袋中的豆子。 # 最后口袋中的豆子就是所有的豆子中最大的一颗。 下面是一个形式算法，用近似于编程语言的伪代码表示 给定：一个数列“list"，以及数列的长度"length(list)" largest = list[1] for counter = 2 to length(list): if list[counter] > largest: largest = list[counter] print largest 符号说明:
- = 用于表示赋值。即：右边的值被赋予给左边的变量。
- List[counter]用于表示数列中的第counter项。例如：如果counter的值是5，那么List[counter]表示数列中的第5项。
- <= 用于表示“小于或等于”。

例子二

求两个自然数的最大公约数 设两个变量 M 和 N #如果 M < N，则交换 M 和 N #M 被 N 除，得到余数 R #判断 R＝0，正确则 N 即为“最大公约数”，否则下一步 #将 N 赋值给 M，将 R 赋值给 N，重做第一步。 用“BASIC 代码”表示－－ If M < N Then Swap M,N Do While R <> 0 R = M Mod N M = N N = R Loop Print N

算法设计和分析的基本方法


- 分治法
- 动态规划
- 贪心法（亦作饕餮法）

算法的分类


- 基本算法
  - 枚举
  - 搜索
    - 深度优先搜索
    - 广度优先搜索
    - 启发式搜索
    - 遗传算法
- 数据结构的算法
- 数论与代数算法
- 计算几何的算法
  - 凸包算法
- 图论的算法
  - 哈夫曼编码
  - 树的遍历
  - 最短路径算法
  - 最小生成树算法
  - 最小树形图
  - 网络流算法
  - 匹配算法
- 动态规划
- 其他
  - 数值分析
  - 加密算法
  - 排序算法
  - 检索算法
  - 随机化算法
  - 关于并行算法，请参阅并行计算一文。

参见


- 计算机科学课程列表 ja:アルゴリズム ko:알고리즘 th:อัลกอริทึม

编程语言

程序设计语言，是一组用来定义计算机程序的语法规则。它是一种被标准化的交流技巧，用来向计算机发出指令。一种计算机语言让程序员能够准确地定义计算机所需要使用的数据，并精确地定义在不同情况下所应当采取的行动。 程序设计语言原本是被设计成专门使用在计算机上的，但它们也可以用来定义算法或者数据结构。正是因为如此，程序员才会试图使程序代码更容易阅读。 设计语言往往使程序员能够比使用机器语言更准确地表达他们所想表达的目的。对那些从事计算机科学的人来说，懂得程序设计语言是十分重要的，因为在当今所有的计算都需要程序设计语言才能完成。 在过去的几十年间，大量的程序设计语言被发明、被取代、被修改或组合在一起。尽管人们多次试图创造一种通用的程序设计语言，却没有一次尝试是成功的。之所以有那么多种不同的编程语言存在的原因是，编写程序的初衷其实也各不相同；新手与老手之间技术的差距非常大，而有许多语言并对新手来说太难学；还有，不同程序之间的运行成本（）各不相同。 有许多用于特殊用途的语言，只在特殊情况下使用。例如，PHP专门用来显示网页；Perl更适合文本处理；C语言被广泛用于操作系统和编译器的开发（所谓的系统编程）。 高级程序设计语言（也称高级语言）的出现使得计算机程序设计语言不再过度地倚赖某种特定的机器或环境。这是因为高级语言在不同的平台上会被编译成不同的机器语言，而不是直接被机器执行。最早出现的编程语言之一FORTRAN的一个主要目标，就是实现平台独立。 虽然大多数的语言可以既被编译（）又被解译（），但大多数只在一种情况下能够良好运行。在一些编程系统中，程序要经过几个阶段的编译，一般而言，后阶段的编译往往更接近机器语言。这种常用的使用技巧最早在1960年代末用于BCPL，编译程序先编译一个叫做“0代码”的转换程序（），然后再使用虚拟器转换到可以运行于机器上的真实代码。这种成功的技巧之后又用于Pascal和P-code，以及Smalltalk和二进制码，虽然在很多时候，中间过渡的代码往往是解译，而不是编译的。 如果所使用的翻译的机制是将所要翻译的程序代码作为一个整体翻译，并之后运行内部格式，那么这个翻译过程就被成为编译。因此，一个编译器是一个将人可阅读的程序文本（叫做源代码）作为输入的数据，然后输出可执行文件（）。所输出的可执行文件可以是机器语言，由计算机的中央处理器直接运行，或者是某种模拟器的二进制代码。 如果程序代码是在运行时才即时翻译，那么这种翻译机制就被称作解译。经解译的程序运行速度往往比编译的程序慢，但往往更具灵活性，因为它们能够与执行环境互相作用。参见解译语言。

特点

每一种程序设计语言可以被看作是一套包含语法、词汇和含义的正式规范。 这些规范通常包括：
- 数据和数据结构
- 指令及流程控制
- 引用机制和重用
- 设计哲学 大多数被广泛使用或经久不衰的语言，拥有负责标准化的组织，经常会晤来创造及发布该语言的正式定义，并讨论扩展或贯彻现有的定义。

数据和数据结构

现代计算机内部的数据都只以二元方式储存，即开-关模式()。现实世界中代表信息的各种数据，例如名字、银行账号、度量以及同样低端的二元数据，都经由程序设计语言整理，成为高端的概念。 一个程序中专门处理数据的那个系统被称为程序语言的型态系统()；对型态系统的研究和设计被称为型态理论()。语言可以被分为静态型态系统()，例如C++和Java，和动态型态系统()，例如Lisp，JavaScript，Tcl和Prolog。前者可被进一步分为包含宣告型态()的语言，即每一个变量和函数的型态都清楚地宣告，或type-inferred语言（例如MUMPS，ML）。 大多数语言还能够在内置的型态基础上组合出复杂的数据结构型态（使用数组，列表，堆栈，文件等等）。面向对象语言（，又译作“物件导向语言”）允许程序员定义新的数据型态，即“对象”或“物件”（），以及运行于该对象的函数（）和方法（）。 除了何时以及如何确定表达式和型态的联系，另外一个重要的问题就是语言到底定义了哪些型态，以及允许哪些型态作为表达式的值。诸如C编程语言之类的低端语言允许程序命名内存位置、内存区域以及编译时的常量；ANSI C甚至允许表达式返回结构值（）。功能性的语言一般允许变量直接使用运行时计算出的值，而不是指出该值可能储存的内存地址。

指令及流程控制

一旦数据被确定，机器必须被告知如何对这些数据进行处理。较简单的指令可以使用关键字或定义好的语法结构来完成。不同的语言利用序列系统来取得或组合这些语句。除此之外，一个语言中的其他指令也可以用来控制处理的过程（例如分支、循环等）。

引用机制和重用

引用的中心思想是必须有一种间接设计储存空间的方法。最常见的方法是通过命名变量。根据不同的语言，进一步的引用可以包括指向其他储存空间的指针。还有一种类似的方法就是命名一组指令。大多数程序设计语言使用宏调用、过程调用或函数调用。使用这些代替的名字能让程序更灵活，并更具重用性。

程序设计语言的历史

二十世纪四十年代当计算机刚刚问世的时候，程序员必须手动控制计算机。当时的计算机十分昂贵，唯一想到利用程序设计语言来解决问题的人是德国工程师楚泽（）。 几十年后，计算机的价格大幅度下跌，而计算机程序也越来越复杂。也就是说，开发时间已经远比运行时间来得宝贵。 于是，新的集成、可视的开发环境越来越流行。它们减少了所付出的时间、金钱（以及脑细胞）。只要轻敲几个键，一整段代码就可以使用了。这也得益于可以重用的程序代码库。

常见的程序设计语言


- APL、A＋和J
- Ada
- 汇编语言
- AWK
- Basic、Fortran
- VBScript
- Brainfuck
- C、C＋＋
- C＃
- Clipper
- COBOL
- dBase
- PASCAL、Delphi
- Forth
- FoxPro
- F＃
- Fava
- IDL
- Java
- JavaScript
- J#
- LISP
- LOGO
- Modula
- Perl
- PHP
- PL/I
- Prolog
- Python
- Ruby
- Scheme
- Smalltalk
- SQL
- Tcl/Tk
- Visual Basic
- Visual FoxPro
- XML

参见


- 计算机科学课程列表
- 程序设计语言列表
- 编译器
- Hello World程序
- 脚本语言
- 維基程序員 category:人工語言 ja:プログラミング言語

计算机程序设计

程序设计是一门艺术。
— Edsger Dijkstra
程序设计是给出解决特定问题程序的过程，是软件构造活动中的重要组成部分。程序设计往往以某种程序设计语言为工具，给出这种语言下的程序。程序设计过程应当包括分析、设计、编码、测试、排错等不同阶段。专业的程序设计人员常被称为程序员。 某种意义上，程序设计的出现甚至早于电子计算机的出现。英国著名诗人拜伦的女儿Ada Lovelace曾设计了巴贝奇分析机上解伯努利方程的一个程序。她甚至还建立了循环和子程序的概念。由于她在程序设计上的开创性工作，Ada Lovelace被称为世界上第一位程序员。 任何设计活动都是在各种约束条件和相互矛盾的需求之间寻求一种平衡，程序设计也不例外。在计算机技术发展的早期，由于机器资源比较昂贵，程序的时间和空间代价往往是设计关心的主要因素；随着硬件技术的飞速发展和软件规模的日益庞大，程序的结构、可维护性、复用性、可扩展性等因素日益重要。 另一方面，在计算机技术发展的早期，软件构造活动主要就是程序设计活动。但随着软件技术的发展，软件系统越来越复杂，逐渐分化出许多专用的软件系统，如操作系统、数据库系统、应用服务器，而且这些专用的软件系统愈来愈成为普遍的计算环境的一部分。这种情况下软件构造活动的内容越来越丰富，不再只是程序设计活动了，还包括数据库设计、用户界面设计、接口设计、通信协议设计和复杂的系统配置过程。

设计工具


- 开发环境
  - 编辑器、编译器、解释器、调试工具
  - 集成开发环境
  - 可视化开发环境
  - 计算机辅助软件工程??

相关条目


- 程序
- 软件
- 程序设计语言
- 程序设计实践
- 程序设计方法学
- 软件开发
- 设计模式
- 计算机科学课程列表 Category:程序设计 ja:プログラミング ko:프로그래밍

计算机程序设计

程序设计是一门艺术。
— Edsger Dijkstra
程序设计是给出解决特定问题程序的过程，是软件构造活动中的重要组成部分。程序设计往往以某种程序设计语言为工具，给出这种语言下的程序。程序设计过程应当包括分析、设计、编码、测试、排错等不同阶段。专业的程序设计人员常被称为程序员。 某种意义上，程序设计的出现甚至早于电子计算机的出现。英国著名诗人拜伦的女儿Ada Lovelace曾设计了巴贝奇分析机上解伯努利方程的一个程序。她甚至还建立了循环和子程序的概念。由于她在程序设计上的开创性工作，Ada Lovelace被称为世界上第一位程序员。 任何设计活动都是在各种约束条件和相互矛盾的需求之间寻求一种平衡，程序设计也不例外。在计算机技术发展的早期，由于机器资源比较昂贵，程序的时间和空间代价往往是设计关心的主要因素；随着硬件技术的飞速发展和软件规模的日益庞大，程序的结构、可维护性、复用性、可扩展性等因素日益重要。 另一方面，在计算机技术发展的早期，软件构造活动主要就是程序设计活动。但随着软件技术的发展，软件系统越来越复杂，逐渐分化出许多专用的软件系统，如操作系统、数据库系统、应用服务器，而且这些专用的软件系统愈来愈成为普遍的计算环境的一部分。这种情况下软件构造活动的内容越来越丰富，不再只是程序设计活动了，还包括数据库设计、用户界面设计、接口设计、通信协议设计和复杂的系统配置过程。

设计工具


- 开发环境
  - 编辑器、编译器、解释器、调试工具
  - 集成开发环境
  - 可视化开发环境
  - 计算机辅助软件工程??

相关条目


- 程序
- 软件
- 程序设计语言
- 程序设计实践
- 程序设计方法学
- 软件开发
- 设计模式
- 计算机科学课程列表 Category:程序设计 ja:プログラミング ko:프로그래밍

可计算性

可计算性（calculability）是指一个实际问题是否可以使用计算机来解决．从广义上讲如“为我烹制一个汉堡”这样的问题是无法用计算机来解决的（至少在目前）．而计算机本身的优势在于数值计算，因此可计算性通常指这一类问题是否可以用计算机解决．事实上，很多非数值问题（比如文字识别，图象处理等）都可以通过转化成为数值问题来交给计算机处理，但是一个可以使用计算机解决的问题应该被定义为“可以在有限步骤内被解决的问题”，故哥德巴赫猜想这样的问题是不属于“可计算问题”之列的，因为计算机没有办法给出数学意义上的证明，因此也没有任何理由期待计算机能解决世界上所有的问题．分析某个问题的可计算性意义重大，它使得人们不必浪费时间在不可能解决的问题上（因而可以尽早转而使用除计算机以外更加有效的手段），集中资源在可以解决的问题集中． Category:计算机科学

数据库

数据库，--，可以被视为能够进行自动查询和修改的数据集。数据库有很多种类型，从最简单的存储有各种数据的表格到能够进行海量数据存储的大型数据库系统都在各个方面得到了广泛的应用。

数据库模型

数据库存在多种模型。最简单的有表格数据库，而应用于大型数据储存的数据库一般为网状数据库和关系数据库。此外也存在树状数据库,它的应用有LDAP（轻量级数据访问协议）数据库等。 表格数据库一般在形式上是一个二维数组。一般来讲，数组中每列表示一个数据类型。数据在其中以不同行的形式存储。表格数据库模型是电子表格（比如Excel）的基础。

数据库的索引

在数据库中存储对象

数据库程序

事务和并发性

事物

概念解释

数据表 ist eine Zusammenfassung einer Anzahl von Datensätzen mit gleicher Struktur, vergleichbar einem Karteikasten. 例如地址表:姓名,街道, 门牌号码, 城市, 电话号码 Alle 信息en, die zusammen einen 数据记录 (Entität, Record) ausmachen, sind als eine Zeile der Tabelle realisiert. Man kann den Datensatz als Zeile anschauen oder übersichtlicher als Formular auf einer Seite darstellen. Ein Datensatz ist vergleichbar mit einer Karte aus einem Karteikasten. Ein 数据域 ist ein Teil eines Datensatzes, z. B. in einer Adresstabelle das Feld mit dem Nachnamen. In Feldern können sich Daten unterschiedlichster Art befinden, z. B. Text, Zahlen, Daten, Bilder, etc. Ein Feld ist vergleichbar einer Zeile auf einer Karte eines Karteikastens. Hierbei werden Schlüsselattribute und sonstige 属性e unterschieden. Das Schlüsselattribut dient zum Identifizieren und Verknüpfen von Datensätzen, während die restlichen Attribute nur vom Schlüssel abhängige Daten enthalten. (Beispiel: Personalnummer ist Schlüssel; Eintrittsdatum und Geburtsdatum sind Attribute). Eine Abfrage dient der Ansicht einer oder mehrerer verknüpfter Tabellen bzw. Teilen davon. Das Ergebnis ist wiederum eine (temporäre) Tabelle, die nach bestimmten Kriterien gefiltert sein kann. Bei Karteikästen entspräche eine Abfrage der Auswahl einiger Karten nach bestimmten Kriterien, z. B. alle Kunden die mit A beginnen und daneben alle Karten der vom jeweiligen Kunden geliehenen Büchern. 简单的查询例如按照字母顺序排序或者根据特定条件过滤。 Üblicherweise werden Abfragen in der 查询语言 SQL erstellt. Abfragen können bei den meisten DBMS auch ohne Wissen über SQL mit den jeweiligen Hilfsprogrammen erstellt werden. Die aufbereitete Ansicht und/oder Zusammenfassung mehrerer Abfragen, dann letztendlich in Papierform, nennt man Report oder Bericht. Berichte oder Reports können mittels vom Hersteller mitgelieferter (bzw. in das DBMS integrierter) oder von Fremdherstellern gelieferter Software erzeugt werden. Diese Berichtsgeneratoren sind aber nicht Bestandteil des eigentlichen DBMS.

常见数据库管理系统


- 4th Dimension 或者叫4D，是一套從Mac OS發展出來的數據庫系統。現在亦有閞發視窗版。
- Microsoft Access 从微软公司兼并的一家公司的产品发展而来
- Adabas Software AG（德国）开发的的数据库参看http://www.softwareag.com/adabas/default.htm
- askSam, 结合了数据库和文本编辑mit vielen innovativen Eigenschaften
- Berkeley_DB 加州大学Berkeley分校研究成果
- Caché, postrelationale Datenbank der Firma intersystems
- Conzept16
- c-tree Plus FairCom公司的ISAM和关系数据库。参看 http://www.faircom.com. C语言编写。
- DB1 IBM产品
- DB2 IBM产品, 当前版本8.2
- dBase 在DOS时代十分重要的数据库，Windows版本是Visual dBase
- eXist native XML开放源代码数据库
- FileMaker ursprünglich von Claris, eine sehr benutzerfreundliche relationale Datenbank, funktioniert mit der gleichen Software sowohl unter Mac OS, wie auch unter Windows, die neueste Version ist 7.0
- 火鸟
- FoxBase 被微软收购，继续开发出微软FoxPro，2.6版之前有DOS和Windows版。
- Gupta SQLBase, 当前版本9.0
- IDMS
- IMS
- Ingres
- InterBase
- MaxDB 参看SAP DB
- 微软Access, 微软公司Office组件之一,当前版本2003 (另外还有XP)
- 微软Visual FoxPro, 当前版本8.0
- MS SQL-Server, 当前版本2005
- Sybase, 早期版本被微软购买开发出SQL-Server。
- mSQL
- MySQL 英特网上十分流行的数据库服务器，结合PHP脚本技术和ApacheWeb服务器使用。维基采用的就是MySQL数据库。
- Oracle, 当前版本10g
- Paradox Borland开发后转手Corel (WordPerfect Office)继续开发
- PostgreSQL, 当前版本8.0.4 (2005年2月)
- PrimeBase
- RRDtool, Round Robin Database
- SAP DB ursprünglich von SAP, wurde aber MySQL zur weiteren Entwicklung und Pflege übergeben und firmiert jetzt unter MaxDB.
- Tamino XML数据库k,基于Adabas的版本由Software AG开发，参看http://www.softwareag.com/tamino/
- Tdbengine
- Teradata, eine sehr leistungsfähige Datenbank der Firma NCR. Wird für große Datenmengen, sog. Data Warehouse verwendet.
- Visual dBase, die letzte Version war 5.0, dann verschwand dBase vom Markt
- Xindice native XML-Datenbank der Apache Software Foundation
- SQLite C Bibliothek für komplettes SQL basiertes Datenbanksystem im kommandozeilenorientierten Programm s. [http://www.sqlite.org/ SQLite下载]

相关内容


- 计算机科学课程列表
- 客户机-服务器模型
- 分布式的数据库
- LDAP（轻量级数据访问协议）
- 关系数据库
- SQL（结构化查询语言）
- PostgreSQL（ORDBMS） category:数据库 ja:データベース ko:데이터베이스 th:ฐานข้อมูล

人工智能

本条目是关于计算机科学中的人工智能，如果你想了解斯蒂芬·斯皮尔伯格导演的一部电影，请参见人工智能 (电影) 人工智能(Artificial Intelligence或简称AI)有时也称作机器智能，是指由人工制造出来的系统所表现出来的智能。这里，“人”也可以广义理解为任何生命体，比如说外星人，如果它们真的存在的话。通常人工智能是指通过普通计算机实现的智能。该词同时也指研究这样的智能系统是否能够实现，以及如何实现的科学领域。

概论

人工智能的定义可以分为两部分，即“人工”和“智能”。“人工”比较好理解，争议性也不大。有时我们会要考虑什么是人力所能及制造的，或着人自身的智能程度有没有高到可以创造人工智能的地步，等等。但总的来说，“人工系统”就是通常意义下的人工系统。 关于什么是“智能”，就问题多多了。这涉及到其它诸如意识（:en:consciousness）、自我（:en:self）、思维（:en:mind）（包括无意识的思维（:en:unconscious_mind）等等问题。人唯一了解的智能是人本身的智能，这是普遍认同的观点。但是我们对我们自身智能的理解都非常有限，对构成人的智能的必要元素也了解有限，所以就很难定义什么是“人工”制造的“智能”了。因此人工智能的研究往往涉及对人的智能本身的研究。其它关于动物或其它人造系统的智能也普遍被认为是人工智能相关的研究课题。 人工智能目前在计算机领域内，得到了愈加广泛的重视。并在机器人，经济政治决策，控制系统，仿真系统中得到应用。

强人工智能和弱人工智能

人工智能的一个比较流行的定义，也是该领域较早的定义，是由约翰·麦卡锡（John McCarthy）在1956年的达特矛斯会议（:en:Dartmouth Conference）上提出的：人工智能就是要让机器的行为看起来就象是人所表现出的智能行为一样。但是这个定义似乎忽略了强人工智能的可能性（见下）。另一个定义指人工智能是人造机器所表现出来的智能性。总体来讲，目前对人工智能的定义大多可划分为四类，即机器“象人一样思考”、“象人一样行动”、“理性地思考”和“理性地行动”。这里“行动”应广义地理解为采取行动，或制定行动的决策，而不是肢体动作。

强人工智能

强人工智能观点认为有可能制造出真正能推理（:en:Reasoning）和解决问题（:en:Problem_solving）的智能机器，并且，这样的机器能将被认为是有知觉的，有自我意识的。强人工智能可以有两类：
- 类人的人工智能，即机器的思考和推理就象人的思维一样。
- 非类人的人工智能，即机器产生了和人完全不一样的知觉和意识，使用和人完全不一样的推理方式。

弱人工智能

弱人工智能观点认为不可能制造出能真正地推理（:en:Reasoning）和解决问题（:en:Problem_solving）的智能机器，这些机器只不过看起来象是智能的，但是并不真正拥有智能，也不会有自主意识。 目前的主流科研集中在弱人工智能上，并且一般认为这一研究领域已经取得可观的成就。强人工智能的研究则出于停滞不前的状态下。

对强人工智能的哲学争论

“强人工智能”一词最初是约翰·罗杰斯·希尔勒针对计算机和其它信息处理机器创造的，其定义为： “强人工智能观点认为计算机不仅是用来研究人的思维的一种工具；相反，只要运行适当的程序，计算机本身就是有思维的。”（J Searle in Minds Brains and Programs. The Behavioral and Brain Sciences, vol. 3, 1980） 关于强人工智能的争论不同于更广义的一元论和二元论（:en:dualism）的争论。其争论要点是：如果一台机器的唯一工作原理就是对编码数据进行转换，那么这台机器是不是有思维的？希尔勒认为这是不可能的。他举了个中文房间的例子来说明，如果机器仅仅是对数据进行转换，而数据本身是对某些事情的一种编码表现，那么在不理解这一编码和这实际事情之间的对应关系的前提下，机器不可能对其处理的数据有任何理解。基于这一论点，希尔勒认为即使有机器通过了图灵测试，也不一定说明机器就真的象人一样有思维和意识。 也有哲学家持不同的观点。Daniel C. Dennett 在其著作 Consciousness Explained 里认为，人也不过是一台有灵魂的机器而已，为什么我们认为人可以有智能而普通机器就不能呢？他认为象上述的数据转换机器是有可能有思维和意识的。 有的哲学家认为如果弱人工智能是可实现的，那么强人工智能也是可实现的。比如:en:Simon Blackburn在其哲学入门教材 Think 里说道，一个人的看起来是“智能”的行动并不能真正说明这个人就真的是智能的。我永远不可能知道另一个人是否真的象我一样是智能的，还是说她／他仅仅是看起来是智能的。基于这个论点，既然弱人工智能认为可以令机器看起来象是智能的，那就不能完全否定这机器是真的有智能的。Blackburn 认为这是一个主观认定的问题。 需要要指出的是，弱人工智能并非和强人工智能完全对立，也就是说，即使强人工智能是可能的，弱人工智能仍然是有意义的。至少，今日的计算机能做的事，象算术运算等，在百多年前是被认为很需要智能的。

实际应用

机器视觉:指纹识别，人脸识别，视网膜识别，虹膜识别和掌纹识别等。 神经网络。 遗传算法。 专家系统。

可能后果

robot wordcup

学科范畴

人工智能是一门边沿学科，属于自然科学和社会科学的交叉。

涉及学科


- 哲学和认知科学
- 数学
- 心理学
- 计算机科学
- 控制论
- 不定性论

研究范畴


- 自然语言处理
- 知识表现
- 智能搜索
- 推理
- 规划
- 机器学习
- 知识获取
- 感知问题
- 模式识别
- 逻辑程序设计
- 软计算
- 不精确和不确定的管理

应用领域


- 智能控制
- 机器人学
- 语言和图像理解
- 遗传编程

参见


- 艾伦·图灵
- 恐怖谷理论
- Artificial intelligence projects
- 计算机科学
- 计算机科学课程列表
- cognitive science
- consciousness
- 约翰·希尔勒的中国房间
- semantics
- The Singularity
- collective intelligence
- 控制论
- 心理学

站外链接


- [http://bbs.matwav.com/ 研学论坛]关于人工智能，模式识别，科学交流的学术论坛
- [http://www.ChinaAI.org/ ChinaAI.org]-- 中国人工智能网－人工智能|模式识别|数字图像处理
- [http://ai-depot.com/ AI Depot] -- community discussion, news, and articles
- [http://www.loebner.net/Prizef/loebner-prize.html Loebner Prize website]
- [http://www.gameai.com GameAI] -- 关于计算机游戏方面的AI资源
- [http://www.kurzweilcyberart.com/ Kurzweil CyberArt Technologies]-- 关于人工智能艺术的网站，里面有著名的人工智能绘画程序AARON
- [http://cdtzx.swiki.net/ 关于人工智能，专家系统prolog语言全介绍的wiki网站] ja:人工知能 ko:인공 지능 th:ปัญญาประดิษฐ์

人机界面

人机界面（又稱用户界面或使用者界面）是系统和用户之间进行交互和信息交换的媒介，它实现信息的内部形式与人类可以接受形式之间的转换。凡参与人机信息交流的领域都存在着人机界面。 用户和系统之间一般用面向问题的受限自然语言进行交互。目前有有系统开始利用多媒体技术开发新一代的用户界面。
- 功能性界面
- 情感性界面
- 环境性界面

历史

参看


- 人机工程学
- 人机交互
- 工业工程 Category:人机工程学 ja:ユーザーインターフェイス

图灵机

即确定型图灵机 1936年，阿兰·图灵提出了一种抽象的计算模型 ── 图灵机 (Turing Machine)。图灵的基本思想是用机器来模拟人们用纸笔进行数学运算的过程，他把这样的过程看作下列两种简单的动作：
- 在纸上写上或擦除某个符号；
- 把注意力从纸的一个位置移动到另一个位置； 而在每个阶段，人要决定下一步的动作，依赖于 (a) 此人当前所关注的纸上某个位置的符号和(b) 此人当前思维的状态。为了模拟人的这种运算过程，图灵构造出一台假想的机器，该机器由以下几个部分组成： # 一条无限长的纸带。纸带被划分为一个接一个的小格子，每个格子上包含一个来自有限字母表的符号，字母表中有一个特殊的符号 \square 表示空白。纸带上的格子从左到右依此被编号为 0, 1, 2, ... ，纸带的右端可以无限伸展。 # 一个读写头。该读写头可以在纸带上左右移动，它能读出当前所指的格子上的符号，并能改变当前格子上的符号。 # 一个状态寄存器。它用来保存图灵机当前所处的状态。图灵机的所有可能状态的数目是有限的，并且有一个特殊的状态，称为停机状态。 # 一套控制规则。它根据当前机器所处的状态以及当前读写头所指的格子上的符号来确定读写头下一步的动作，并改变状态寄存器的值，令机器进入一个新的状态。 注意这个机器的每一部分都是有限的，但它有一个潜在的无限长的纸带，因此这种机器只是一个理想的设备。图灵认为这样的一台机器就能模拟人类所能进行的任何计算过程。

图灵机的形式化定义

一台图灵机 (Turing Machine)是一个七元组 (Q, \Sigma, \Gamma, \delta, q_0, q_, q_)，其中 Q, \Sigma, \Gamma 都是有穷集，且满足 # Q 是状态集合； # \Sigma 是输入字母表，其中不包含特殊的空白符 \square； # \Gamma 是带字母表，其中 \square \in \Gamma 且 \Sigma \subset \Gamma； # \delta : Q \times \Gamma \to Q \times \Gamma \times \ 是转移函数，其中L, R 表示读写头是向左移还是向右移； # q_0 \in Q 是起始状态； # q_ \in Q 是接受状态。 # q_\in Q 是拒绝状态，且 q_\neq q_。 图灵机 M=(Q, \Sigma, \Gamma, \delta, q_0, q_, q_) 将以如下方式运作： 开始的时候将输入符号串 \omega=\omega_0\omega_1\ldots\omega_ \in \Sigma^
- 从左到右依此填在纸带的第 0, 1, \ldots , n-1 号格子上， 其他格子保持空白(即填以空白符\square)。 M 的读写头指向第 0 号格子， M 处于状态 q_0。 机器开始运行后，按照转移函数 \delta 所描述的规则进行计算。 例如，若当前机器的状态为 q，读写头所指的格子中的符号为 x， 设 \delta(q,x) = (q', x', L)， 则机器进入新状态 q'， 将读写头所指的格子中的符号改为 x'， 然后将读写头向左移动一个格子。 若在某一时刻，读写头所指的是第 0 号格子， 但根据转移函数它下一步将继续向左移，这时它停在原地不动。 换句话说，读写头始终不移出纸带的左边界。 若在某个时刻 M 根据转移函数进入了状态 q_， 则它立刻停机并接受输入的字符串； 若在某个时刻 M 根据转移函数进入了状态 q_， 则它立刻停机并拒绝输入的字符串。 注意，转移函数 \delta 是一个部分函数， 换句话说对于某些 q,x， \delta(q,x) 可能没有定义， 如果在运行中遇到下一个操作没有定义的情况， 机器将立刻停机。

图灵机的基本术语

设 M=(Q, \Sigma, \Gamma, \delta, q_0, q_, q_) 是一台图灵机， # M 的带描述(tape description)是一个函数 F: \mathbb \to \Gamma，其中 F(i) 表示 M 的带上第 i 个格子中的符号； # M 的格局(configuration)是一个三元组 (F, q, e)，其中F: \mathbb \to \Gamma 是当前的带描述，q \in Q 是当前的状态，e \in \mathbb 是当前读写头所处的位置； # 设 C_1 = (F_1, q_1, e_1), C_2 = (F_2, q_2, e_2) 是 M 的格局，设\delta(q_1, F_1(e_1)) = (q, x, d)，若满足q_2=q，
e_2=\begin e_1 - 1 & d = L \\ e_1 + 1 & d = R \end
以及
F_2(i)=\begin F_1(i) & i \neq e_1 \\ x & i = e_1 \end
则称 M 从格局C_1 产生格局C_2，记作C_1 \to_M C_2。 # 设 C = (F, q, e)为 M 的格局，若 q = q_ 则称 C 为接受格局；若 q = q_ 则称 C 为拒绝格局；接受格局和拒绝格局统称为停机格局。 设 M 是一台图灵机，将字符串 \omega=\omega_0\omega_1\ldots\omega_ 作为其输入，若存在格局序列 C_1, C_2, \ldots, C_k，使得 # C_1 是 M 在输入 \omega 上的起始格局，即 C_1 = (F,q,e)，其中
F_1(i) = \begin \omega_i & 0 \leq i \leq n-1 \\ \square & \mbox \end
# C_i \to_M C_，其中 i = 1, 2, \ldots, k-1； # C_k 是接受格局。 则称 M 接受字符串 \omega，且 C_1, C_2, \ldots, C_k 称为图灵机 M 在输入 \omega 上的接受计算历史。同理，若 C_k 是拒绝格局，则称 M 拒绝 \omega，且C_1, C_2, \ldots, C_k 称为图灵机 M 在输入 \omega 上的拒绝计算历史。M 所接受的所有字符串的集合称为 M 的语言，记作 L(M)。

圖靈機的例子

[TODO: 這裡需要補充幾個例子] 設M=(\, \, \, \delta, 0, , )
和\delta:\\times\\to\\times\\times\. 比如做一個以 1 的個數表示數值的加法運算, 在磁带上的數據是 0000001110110000 , 就是3+2的意思. 程序\delta如下
0,0 -> 0,0R
0,1 -> 1,1R
1,0 -> 10,1R
1,1 -> 1,1R
10,0 -> 11,0L
10,1 -> 10,1R
11,0 -> E
11,1 -> 0,0S
第一行程序 0,0->0,0R 意思就是如果機器讀到0,就將其變成0,狀態變為0, 讀寫頭向右移動一格. R就是向右移動一格,L就是向左移一格,E是錯誤,S是停機. xx,y -> aa,bb 中 xx是當前狀態, y是當前格子的值, aa是程序下一步的狀態, b是當前格的修改值.
雖然這裡給出與上面不同形式的定義, 但兩者是等價的, 這裡的定義並不比上面的定義能完成更多的工作. 步數 狀態 磁帶 步數 狀態 磁帶 - - - - - - - - - - - - - - - - - 1 0 0000001110110000 9 1 0000001110110000 2 0 0000001110110000 10 1 0000001110110000 3 0 0000001110110000 11 10 0000001111110000 4 0 0000001110110000 12 10 0000001111110000 5 0 0000001110110000 13 10 0000001111110000 6 0 0000001110110000 14 11 0000001111110000 7 0 0000001110110000 15 0 0000001111100000 (停機) 8 1 0000001110110000 -- 停機 --

通用图灵机

对于任意一个图灵机，因为它的描述是有限的，因此我们总可以用某种方式将其编码为字符串。 我们用 \langle M \rangle 表示图灵机 M 的编码。 我们可以构造出一个特殊的图灵机，它接受任意一个图灵机 M 的编码 \langle M\rangle，然后模拟 M 的运作，这样的图灵机称为通用图灵机(Universal Turing Machine)。现代电子计算机其实就是这样一种通用图灵机，它能接受一段描述其他图灵机的程序，并运行程序实现该程序所描述的算法。

图灵机的变体

图灵机有很多变种，但可以证明这些变种的计算能力都是等价的，即它们识别同样的语言类。 证明两个计算模型 A 和 B 的计算能力等价的基本思想是： 用 A 和 B 相互模拟， 若 A 可模拟 B 且 B 可模拟 A， 显然他们的计算能力等价。注意这里我们暂时不考虑计算的效率，只考虑计算的理论上“可行性”。 首先我们可以发现，改变图灵机的带字母表并不会改变其计算能力。例如我们可以限制图灵机 的带字母表为 \，这并不会改变图灵机的计算能力，因为我们显然可以用带字母表为 \ 的图灵机模拟带字母表为任意有限集合 \Gamma 的图灵机。 另一个要注意的是，如果我们允许图灵机的纸带两端都可以无限伸展，这并不能增加图灵机的计 算能力，因为我们显然可以用只有纸带一端能无限伸展的图灵机来模拟这种纸带两端都可以无限 伸展的图灵机。 如果我们允许图灵机的读写头在某一步保持原地不动，那也不会增加其计算能力，因为我们可以用 向左移动一次再向右移动一次来代替在原地不动。 其它的常见图灵机变种包括：
- 多带图灵机
- 非确定型图灵机
- 枚举器

图灵可计算性


- 图灵可识别语言
- 图灵可枚举语言
- 图灵可判定语言
- 图灵可计算函数
- 递归可计算函数
- 停机问题
- 可判定性
- 不可判定性

其它等价的计算模型

除了图灵机以外，人们还发明了很多其它的计算模型。包括：
- 算盘机
- 递归函数
- λ演算
- 生命游戏
- 马尔可夫算法 然而这些模型无一例外地都和图灵机的计算能力等价，因此邱奇，图灵和歌德尔 提出了著名的邱奇-图灵论题：一切直觉上能行可计算的函数都可用图灵机计算，反之亦然。

参考文献


- Turing, A., [http://www.abelard.org/turpap2/tp2-ie.asp On Computable Numbers, With an Application to the Entscheidungsproblem], Proceedings of the London Mathematical Society, Series 2, Volume 42, 1936; reprinted in M. David (ed.), The Undecidable, Hewlett, NY: Raven Press, 1965;
- Michael Sipser, Introduction to the Theory of Computation, PWS Publishing, 1997. ISBN 053494728X

外部链结


- [http://www.cheransoft.com/vturing/ Visual Turing, a Turing machine interactive simulator/IDE] (free software for Windows).
- [http://www.igs.net/~tril/tm/ Suzanne Brittons Turing Machine Simulator] (java applet).
- [http://sourceforge.net/projects/turing-machine/ C++ Simulator of a Nondeterministic and Deterministic Turing Machine] (free software).
- [http://citeseer.org/cs?q=Turing+machine Citations from CiteSeer] category:可计算模型 category:图灵机 category:形式語言 ja:チューリングマシン ko:튜링 기계 th:เครื่องจักรทัวริง

邱奇-图灵论题

邱奇-图灵论题（The Church-Turing thesis）是计算机科学中以数学家阿隆佐·邱奇(Alonzo Church)和阿兰·图灵命名的论题。该论题最基本的观点表明，所有计算或算法都可以由一台图灵机来执行。以任何常规编程语言编写的计算机程序都可以翻译成一台图灵机，反之任何一台图灵机也都可以翻译成大部分编程语言程序，所以该论题和以下说法等价：常规的编程语言可以足够有效的来表达任何算法。该论题被普遍假定为真，也被称为邱奇论题或邱奇猜想 和图灵论题。

本论题之等价形式

本论题的另外一种说法就是逻辑和数学中的有效或机械方法可由图灵机来表示。通常我们假定这些方法必须满足以下的要求： #一个方法由有限多简单和精确的指令组成，这些指令可由有限多的符号来描述。 #该方法总会在有限的步骤内产生出一个结果。 #基本上人可以仅用纸张和铅笔来执行。 #该方法的执行不需人类的智慧来理解和执行这些指令。 此类方法的一个范例便是用于确定两个自然数的最大公约数的欧基里德算法。 “有效方法”这个想法在直觉上是清楚的，但却没有在形式上加以定义，因为什么是“一个简单而精确的指令”和什么是“执行这些指令所需的智力”这两个问题并没有明确的答案。 (如需欧几里得算法之外的范例，请参见数论中的有效结果。)

本论题之起源

在他1936年的论文“论可计算数字，及其在判定性问题(Entscheidungsproblem--德语，译者注)中的应用”中，阿兰·图灵试图通过引入图灵机来形式地展示这一想法。在此篇论文中，他证明了“判定性问题”是无法解决的。几个月之前，阿隆佐·邱奇在“关于判定性问题的解释”(A Note on the Entscheidungsproblem)一文中证明出了一个相似的论题，但他采用但是递归函数和Lambda可定义函数来形式地描述有效可计算性。Lambda可定义函数由阿隆佐·邱奇和史蒂芬·克林(Stephen Kleene) (Church 1932, 1936a, 1941, Kleene 1935)提出，而递归函数由库尔特·歌德尔(Kurt Gödel)和雅克斯·赫尔不兰特(Jacques Herbrand) (Gödel 1934, Herbrand 1932)提出。这两个机制描述的是同一集合的函数，正如邱奇和克林(Church 1936a, Kleene 1936)所展示的正整数函数那样。在听说了邱奇的建议后，图灵很快就证明了他的图灵机实际上描述的是同一集合的函数(Turing 1936, 263ff).y

本论题之成功

之后用于描述有效计算的许多其他机制也被提了出来，比如寄存器机器(register machine), 埃米尔·波斯特(Emill Post)的波斯特体系，组合可定义性(combinatory definability)以及马尔可夫算法(Markov 1960)等。所有这些体系都已被证明在计算上和图灵机拥有基本相同的能；类似的系统被称为图灵完全。因为所有这些不同的试图描述算法的努力都导致了等价的结果，所以现在普遍认为邱奇-图灵论题是正确的。但是，该论题不具有数学定理一般的地位，也无法被证明；如果能有一个方法能被普遍接受为一个有效的算法但却无法在图灵机上允许，则该论题也是可以被驳斥的。 在20世纪初期，数学家们经常使用一种非正式的说法即可有效计算，所以为这个概念寻找一个好的形式描述也是十分重要的。当代的数学家们则使用图灵可计算(或简写为可计算)这一定义良好的概念。由于这个没有定义的用语在使用中已经淡去，所以如何定义它的问题几经不是那么重要了。

哲学内涵

邱奇-图灵论题对于心智哲学(philosophy of mind)有很多寓意。有很多重要而悬而未决的问题也涵盖了邱奇-图灵论题和物理学之间的关系，还有超计算性(hypercomputation)的可能性。应用到物理学上，该论题有很多可能的意义： #宇宙是一台图灵机(由此，在物理上对非递归函数的计算是不可能的)。此被定义为大邱奇-图灵论题。 #宇宙不是一台图灵机(也就是说，物理的定律不是图灵可计算的)，但是不可计算的物理事件却不能阻碍我们来创建 超计算机(hypercomputer)。比如，一个物理上实数作为可计算实数的宇宙就可以被划为此类。 #宇宙是一台超计算机, 因为建造物理设备来控制这一特征并来计算非递归函数是可能的。比如，一个悬而未决的问题是量子力学的的事件是图灵可计算的，尽管我们已经证明了任何由qubit所构成的系统都是(最佳)图灵完全的。约翰·卢卡斯(和罗格·本罗泽(Roger Penrose)曾经建议说人的心灵可能是量子超计算的结果。 实际上在这三类之外或其中还有许多其他的技术上的可能性，但这三类只是为了阐述这一概念。

补充材料 <