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:コンピューティング

编程语言

程序设计语言，是一组用来定义计算机程序的语法规则。它是一种被标准化的交流技巧，用来向计算机发出指令。一种计算机语言让程序员能够准确地定义计算机所需要使用的数据，并精确地定义在不同情况下所应当采取的行动。 程序设计语言原本是被设计成专门使用在计算机上的，但它们也可以用来定义算法或者数据结构。正是因为如此，程序员才会试图使程序代码更容易阅读。 设计语言往往使程序员能够比使用机器语言更准确地表达他们所想表达的目的。对那些从事计算机科学的人来说，懂得程序设计语言是十分重要的，因为在当今所有的计算都需要程序设计语言才能完成。 在过去的几十年间，大量的程序设计语言被发明、被取代、被修改或组合在一起。尽管人们多次试图创造一种通用的程序设计语言，却没有一次尝试是成功的。之所以有那么多种不同的编程语言存在的原因是，编写程序的初衷其实也各不相同；新手与老手之间技术的差距非常大，而有许多语言并对新手来说太难学；还有，不同程序之间的运行成本（）各不相同。 有许多用于特殊用途的语言，只在特殊情况下使用。例如，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:プログラミング言語

计算机软件

軟--件（中国大陆及香港用语，台湾作软体）是一系列按照特定顺序组织的计算机数据和指令的集合。一般来讲软件被划分为系统软件、应用软件和介于这两者之间的中间件。其中系统软件为计算机使用提供最基本的功能，但是并不针对某一特定应用领域。而应用软件则恰好相反，不同的应用软件根据用户和所服务的领域提供不同的功能。 软件并不只是包括可以在计算机上运行的程序，与这些程序相关的文件一般也被认为是软件的一部分。简单的说软件就是程序加文档的集合体。 软件被应用于世界的各个领域，对人们的生活和工作都产生了深远的影响。

系统软件

系统软件是负责管理计算机系统中各种独立的硬件，使得它们可以协调工作。系统软件使得计算机使用者和其他软件将计算机当作一个整体而不需要顾及到底层每个硬件是如何工作的。 一般来讲，系统软件包括操作系统和一系列基本的工具（比如编译器，数据库管理，存储器格式化，文件系统管理，用户身份验证，驱动管理，网络连接等方面的工具）。

应用软件

应用软件是为了某种特定的用途而被开发的软件。它可以是一个特定的程序，比如一个图像浏览器。也可以是一组功能联系紧密，可以互相协作的程序的集合，比如微软的Office软件。也可以是一个由众多独立程序组成的庞大的软件系统，比如数据库管理系统。 较常见的有 #文字处理软件 如WPS、Word等 #信息管理软件 #辅助设计软件 如AutoCAD #实时控制软件 #教育与娱乐软件

按操作系统分类


- BeOS
- DOS
- Linux
- Mac OS
- Unix
- Windows

软件开发

软件开发是根据用户要求建造出软件系统或者系统中的软件部分的过程。软件开发是一项包括需求捕捉，需求分析，设计，实现和测试的系统工程。 软件一般是用某种程序设计语言来实现的。通常采用软件开发工具可以进行开发。

软件许可

不同的软件一般都有对应的软件许可，软件的使用者必须在同意所使用软件的许可证的情况下采能够合法的使用软件。从另一方面来讲，某种特定软件的许可条款也不能够与法律相抵触。 未经软件版权所有者许可的软件拷贝将会引发法律问题，一般来讲，购买和使用这些盗版软件也是违法的。

相关内容


- 计算
- 计算机
- 计算机科学
- 计算机程序设计
- 程序设计语言
- 软件工程
- 算法
- 数据结构
- 软件开发过程
- 软件开发工具
- 软件优化
- 数字图像处理
- 计算机图形学
- 办公自动化
- 计算机网络
- 数据库
- 电子表格
- 开放源代码
- 自由软件
- 密码学
- Wiki
- 網誌
- 操作系统
- 软件许可证
- 推荐软件

参见


- 计算机软件列表 ja:ソフトウェア ko:컴퓨터 소프트웨어 nb:Dataprogram simple:Software th:ซอฟต์แวร์

计算机程序设计

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

设计工具


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

相关条目


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

可计算性

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

数据结构

算法＋数据结构＝程序
— 尼古拉斯·沃斯
数据结构（Data Structure）是计算机存储、组织数据的方式。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率的算法。数据结构往往同高效的检索算法和索引技术有关。 在许多类型的程序的设计中，数据结构的选择是一个基本的设计考虑因素。许多大型系统的构造经验表明，系统实现的困难程度和系统构造的质量都严重的依赖于是否选择了最优的数据结构。许多时候，确定了数据结构后，算法就容易得到了。有些时候事情也会反过来，我们根据特定算法来选择数据结构与之适应。不论哪种情况，选择合适的数据结构都是非常重要的。 选择了数据结构，算法也随之确定，是数据而不是算法是系统构造的关键因素。这种洞见导致了许多种软件设计方法和程序设计语言的出现，面向对象的程序设计语言就是其中之一。 在计算机科学中，数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象（数据元素）以及它们之间的关系和运算等的学科，而且确保经过这些运算后所得到的新结构仍然是原来的结构类型。 “数据结构”作为一门独立的课程在国外是从1968年才开始设立的。 1968年美国唐·欧·克努特教授开创了数据结构的最初体系，他所著的《计算机程序设计技巧》第一卷《基本算法》是第一本较系统地阐述数据的逻辑结构和存储结构及其操作的著作。“数据结构”在计算机科学中是一门综合性的专业基础课。数据结构是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。数据结构这一门课的内容不仅是一般程序设计（特别是非数值性程序设计）的基础，而且是设计和实现编译程序、操作系统、数据库系统及其他系统程序的重要基础。 计算机是一门研究用计算机进行信息表示和处理的科学。这里面涉及到两个问题：
- 信息的表示
- 信息的处理 而信息的表示和组又直接关系到处理信息的程序的效率。随着计算机的普及，信息量的增加，信息范围的拓宽，使许多系统程序和应用程序的规模很大，结构又相当复杂。因此，为了编写出一个“好”的程序，必须分析待处理的对象的特征及各对象之间存在的关系，这就是数据结构这门课所要研究的问题。众所周知，计算机的程序是对信息进行加工处理。在大多数情况下，这些信息并不是没有组织，信息（数据）之间往往具有重要的结构关系，这就是数据结构的内容。数据的结构，直接影响算法的选择和效率。 计算机解决一个具体问题时，大致需要经过下列几个步骤：首先要从具体问题中抽象出一个适当的数学模型，然后设计一个解此数学模型的算法（Algorithm），最后编出程序、进行测试、调整直至得到最终解答。寻求数学模型的实质是分析问题，从中提取操作的对象，并找出这些操作对象之间含有的关系，然后用数学的语言加以描述。计算机算法与数据的结构密切相关，算法无不依附于具体的数据结构，数据结构直接关系到算法的选择和效率。运算是由计算机来完成，这就要设计相应的插入、删除和修改的算法 。也就是说，数据结构还需要给出每种结构类型所定义的各种运算的算法。 数据是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并由计算机程序处理的符号的总称。 数据元素是数据的基本单位，在计算机程序中通常作为一个整体考虑。一个数据元素由若干个数据项组成。数据项是数据的不可分割的最小单位。有两类数据元素：一类是不可分割的原子型数据元素，如：整数"5"，字符 "N" 等；另一类是由多个款项构成的数据元素，其中每个款项被称为一个数据项。例如描述一个学生的信息的数据元素可由下列6个数据项组成。其中的出身日期又可以由三个数据项："年"、"月"和"日"组成，则称"出身日期"为组合项，而其它不可分割的数据项为原子项。 关键字指的是能识别一个或多个数据元素的数据项。若能起唯一识别作用，则称之为 "主" 关键字，否则称之为 "次" 关键字。 数据对象是性质相同的数据元素的集合，是数据的一个子集。数据对象可以是有限的，也可以是无限的。 数据处理是指对数据进行查找、插入、删除、合并、排序、统计以及简单计算等的操作过程。在早期，计算机主要用于科学和工程计算，进入八十年代以后，计算机主要用于数据处理。据有关统计资料表明，现在计算机用于数据处理的时间比例达到80%以上，随着时间的推移和计算机应用的进一步普及，计算机用于数据处理的时间比例必将进一步增大。 数据结构是指同一数据元素类中各数据元素之间存在的关系。数据结构分别为逻辑结构、存储结构（物理结构）和数据的运算。数据的逻辑结构是对数据之间关系的描述，有时就把逻辑结构简称为数据结构。逻辑结构形式地定义为（K，R）（或（D，S）），其中，K是数据元素的有限集，R是K上的关系的有限集。 数据元素相互之间的关系称为结构。有四类基本结构：集合、线性结构、树形结构、图状结构（网状结构）。树形结构和图形结构全称为非线性结构。集合结构中的数据元素除了同属于一种类型外，别无其它关系。线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多关系，图形结构中元素之间存在多对多关系。在图形结构中每个结点的前驱结点数和后续结点数可以任意多个。 数据结构在计算机中的表示（映像）称为数据的物理（存储）结构。它包括数据元素的表示和关系的表示。数据元素之间的关系有两种不同的表示方法：顺序映象和非顺序映象，并由此得到两种不同的存储结构：顺序存储结构和链式存储结构。顺序存储方法：它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现，由此得到的存储表示称为顺序存储结构。顺序存储结构是一种最基本的存储表示方法，通常借助于程序设计语言中的数组来实现。链接存储方法：它不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系是由附加的指针字段表示的。由此得到的存储表示称为链式存储结构，链式存储结构通常借助于程序设计语言中的指针类型来实现。索引存储方法：除建立存储结点信息外，还建立附加的索引表来标识结点的地址。散列存储方法：就是根据结点的关键字直接计算出该结点的存储地址。 数据结构中，逻辑上（逻辑结构：数据元素之间的逻辑关系）可以把数据结构分成线性结构和非线性结构。线性结构的顺序存储结构是一种随机存取的存储结构，线性表的链式存储结构是一种顺序存取的存储结构。线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不连续。逻辑结构与数据元素本身的形式、内容、相对位置、所含结点个数都无关。 算法的设计取决于数据（逻辑）结构，而算法的实现依赖于采用的存储结构。数据的运算是在数据的逻辑结构上定义的操作算法，如检索、插入、删除、更新的排序等。 数据结构的形式定义为：数据结构是一个二元组： Data-Structure=(D，S) 其中：D是数据元素的有限集，S是D上关系的有限集。 数据结构不同于数据类型，也不同于数据对象，它不仅要描述数据类型的数据对象，而且要描述数据对象各元素之间的相互关系。 数据类型是一个值的集合和定义在这个值集上的一组操作的总称。数据类型可分为两类：原子类型、结构类型。一方面，在程序设计语言中，每一个数据都属于某种数据类型。类型明显或隐含地规定了数据的取值范围、存储方式以及允许进行的运算。可以认为，数据类型是在程序设计中已经实现了的数据结构。另一方面，在程序设计过程中，当需要引入某种新的数据结构时，总是借助编程语言所提供的数据类型来描述数据的存储结构。 计算机中表示数据的最小单位是二进制数的一位，叫做位。我们用一个由若干位组合起来形成的一个位串表示一个数据元素，通常称这个位串为元素或结点。当数据元素由若干数据项组成时，位串中对应于各个数据项的子位串称为数据域。元素或结点可看成是数据元素在计算机中的映象。 一个软件系统框架应建立在数据之上，而不是建立在操作之上。一个含抽象数据类型的软件模块应包含定义、表示、实现三个部分。 对每一个数据结构而言，必定存在与它密切相关的一组操作。若操作的种类和数目不同，即使逻辑结构相同，数据结构能起的作用也不同。 不同的数据结构其操作集不同，但下列操作必不可缺： #结构的生成； #结构的销毁； #在结构中查找满足规定条件的数据元素； #在结构中插入新的数据元素； #删除结构中已经存在的数据元素； #遍历。 抽象数据类型：一个数学模型以及定义在该模型上的一组操作。抽象数据类型实际上就是对该数据结构的定义。因为它定义了一个数据的逻辑结构以及在此结构上的一组算法。抽象数据类型可用以下三元组表示：（D，S，P）。D是数据对象，S是D上的关系集，P是对D的基本操作集。ADT的定义为： ADT 抽象数据类型名 ADT 抽象数据类型名; 抽象数据类型有两个重要特性：
- 数据抽象
  - 用ADT描述程序处理的实体时，强调的是其本质的特征、其所能完成的功能以及它和外部用户的接口（即外界使用它的方法）。
- 数据封装
  - 将实体的外部特性和其内部实现细节分离，并且对外部用户隐藏其内部实现细节。

常用的数据结构


- 离散结构
  - 集合
    - 并查集
    - 字典
      - 有序字典
- 线性结构
  - 线性表
    - 顺序表
    - 链表(鍵結串列）
      - 单链表
      -
- 静态单链表
      -
- 跳表 (Skip list)
      - 双链表
      - 循环链表
      -
- 单循环链表
      -
- 双循环链表
  - 散列表(哈希表或雜湊表)
  - 栈(堆疊)
  - 队列（佇列）
    - 链队列
    - 循环队列
    - 优先队列 (有时使用堆来实现)
  - 双端队列
  - 串
  - 跳跃表
- 非线性结构
  - 数组
    - 二维数组（矩阵）
      - 稀疏矩阵
  - 广义表
  - 树形结构
    - 二叉树（二元樹）
      - 哈夫曼树（最优二叉树）
      - 线索二叉树
      - 二叉排序树
      -
- 平衡二叉树
      -
  - AVL树
      -
  - 红黑树
      -
    - AA树
      -
  - 伸展树
      -
- 线段树
      - 堆
      -
- 二叉堆
      -
- 二项堆
      -
- 斐波纳契堆
      -
- 配对堆
    - 森林
    - B树
      - 2-3-4树
    - 剖析树
    - 后缀树
    - Trie
    - 四叉树 (Quadtree)
    - 八叉树 (Octree)
    - kd树
    - 生成树
      - 最小生成树
  - 图状结构（网状结构）
    - 有向图
      - 有向网 (带权有向图)
      - 有向无环图 (DAG)
      -
- AOE网 (带权有向无环图)
      -
- AOV网
    - 无向图
      - 无向网 (带权无向图)
    - 连通图
      - 强连通图
    - 完全图
    - 稀疏图
    - 稠密图
    - 表示方法
      - 邻接矩阵
      - 邻接表
      - 十字链表
      - 邻接多重表
- 其他数据结构
  - 标签联合
  - 联合
  - 框架
  - 数据库和“表”

相关条目


- 算法
- 计算机科学
- 计算机科学课程列表

参考文献


- Cliford A. Shaffer／张铭等译：数据结构与算法分析（C++版，第二版），电子工业出版社 ISBN 7-5053-7646-2/TP.4425 [http://www.china-pub.com/computers/common/info.asp?id=6469]
- 严蔚敏 吴伟民著：数据结构（C语言版），清华大学出版社 ISBN 7-302-02368-9/TP.1185 [http://www.welan.com/html/00/32100.Html] 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:ปัญญาประดิษฐ์

冯·诺依曼计算机

存储程序计算机最早是由著名数学家冯·诺依曼等人在1946年总结并明确提出来的，因此又被称为冯·诺依曼计算机。 存储程序计算机在体系结构上主要特点有： #以运算单元为中心 #采用存储程序原理 #存储器是按地址访问、线性编址的空间 #控制流由指令流产生 #指令由操作码和地址码组成 #数据以二进制编码

图灵机

即确定型图灵机 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)以及马尔可夫算法(Mar