由于甲骨文公司的版权限制，Linux 发行版不能包含 Oracle Java，Ubuntu 也只提供了开源的 OpenJDK。OpenJDK 会带来各种各样的兼容性问题，不推荐部署 Java 开发。甲骨文 Oracle Java 本身既包含 JRE（Java Runtime Environment Java 运行环境）又包含 JDK（Java Development Kit Java 开发套件），我们只需要安装一份 Oracle Java 8，即可满足需要。

对于 Ubuntu 及其衍生版，使用 PPA 软件仓库安装 Oracle Java 8 是最快捷的，在终端中输入命令如下即可完成安装：

1
2
3

sudo apt-get repository ppa : webupd8team/java
sudo apt-get update
sudo apt-get install oracle-java8-installer

下面这条命令可以设置环境变量，将 Oracle Java 8 设置为系统的默认 Java 虚拟机：

1

sudo apt-get install oracle-java8-set-default

完成以上步骤之后你可以通过下面这行命令检验是否安装成功：

1

java –version

如果安装成功，终端会得到如下提示：

1
2
3

java version “1.8.0”
Java (TM) SE Runtime Environment (build 1.8.0–b132)
Java HotSpot (TM) 64-Bit Server VM (build 25.0–b70, mixed mode)

具体显示的版本号可能会略有不同，例如，32 位机器上会显示 32 位虚拟机的相关信息。

新媒体的语言

列夫·曼诺维奇著
OrangeCLK 译
orangeclk[at]orangeclk.com

引言

现状的理论

我奢望人们在 1895 年或者 1897 年，最晚 1903 年，就能够认识到电影出现的重要性，然后对这个新型媒体的产生过程做下完备的记录。记录包括观众访谈会；逐年发展的叙事手法、场景调度、机位设置；对于新生的电影语言和其他与之共生的娱乐活动之间联系的分析等。不幸的是，这些记录都不存在。相反，我们只有些纸媒报道、电影发明人的日记、影片播放流程，还有些其他散落各处的星星点点。

现在我们正在见证一种全新媒体的出现——数字计算机的元媒体。和100年前电影面世不同，我们现在完全能体会到新媒体革命的巨大影响。但我仍然担心，我们留给未来理论学者与历史学者的资料，就如同电影年代留给我们的纸媒报道和播放流程那样，信息量并没有多多少。未来的学者会发现我们这个年代的分析文章已经充分意识到了计算机对文化的重要影响，但是大部分内容都是对未来的预测而不是对现状理论的记录。未来的研究人员会疑惑，为什么我们这个时代的理论学者，已经拥有了大量分析历史文化形态的经验，却没有努力把计算机媒体的符号代码、寻址模式、用户接纳模式记录下来？电影艺术从全景摄影、光学玩具、西洋镜等上个时代的艺术形式中脱颖而出，我们煞费苦心才还原出这段历史。在计算机媒体语言刚刚诞生的此时此刻，已有文化形式的元素正在逐渐介入计算机媒体。这个过程在我们的时代如此清晰，这些元素还都一一可见，还没有融为新的一体，那么我们为什么不尝试去构建一个类似于电影发展史的计算机媒体发展谱系呢？在多媒体界面的图标和按钮还都像油漆未干的油画笔触时，在他们演变为普遍规范并迅速消失淘汰之前，我们的理论学者在哪里？当神秘岛[1]的设计者调试代码，把图片转化为字节，美化每一帧 QuickTime[2]剪辑画面的时候，我们的理论学者在哪里？有一天，网景公司一位二十来岁的程序员吐出口香糖，啜下一小口温暖的可乐。他已经在计算机前连续工作了16个小时，正努力赶上产品开发的截止日期。最终他以满意的文件大小，制作了一小段星星飞过夜空的动画。在这个历史性的时刻，我们的理论学者在哪里？这段动画就是网景网景导航者[3]右上角的标识，在下一版网景导航者发布之前，它就是世界上观众最多的动画短片。

[1]Myst Cyan公司于1993年推出的一款图形解谜游戏。——译者注
[2]苹果公司的一款媒体播放器。——译者注
[3]网景导航者（Netscape Navigator）又称领航员，是网景公司开发的网络浏览器。曾经是世界上最流行的网页浏览器。——译者注

下面我就要尝试着记录现状，描述现状的理论。就像电影史学者在电影诞生的头几十年跟踪电影语言的发展那样，我想描述并理解新媒体语言发展的动力源泉。（我并不是说新媒体只有一种语言，而是采用这个泛用术语来指代新媒体对象的设计者们采取的种种规范，这些规范用于组织数据和构建用户体验等方面。）进一步类比，电影语言在 1910 年代形成了自己的经典范式，那么现在新媒体语言是否正在接近自己最终稳定的形式呢？这项预测对我很有吸引力。因为未来计算机媒体的语言会和现在的样子完全不同，1990 年的状况可能更接近1890年而非将来的经典范式。

现状在飞速变化，我们针对现状构建理论有意义吗？我只能说这是场糟糕的赌博。如果将来的发展证明我的理论预计是正确的，我就赢了。但是如果计算机媒体语言的发展方向和我分析揭露的方向不同，我的分析就成为来未来人眼中历史发展一种可能性的记录，我们现在可以见到但是未来人难以相信。

我们现在认为电影不会走向单一语言形式，电影不会只走向虚拟现实。相反，我们已经看到电影发展出了多种多样有表达力的成功语言形式。每一种语言都有它自己的美学变量，每一种新语言都导致了一些旧语言的消亡。（这个文化逻辑和托马斯·库恩关于科学范式的分析不同）[4]相似的，计算机媒体历史的每一步都产生了新的美学机遇，包括他们自己对于未来的计划，即他们自己的“研究范式”。这本身也是一种新的语言。研究范式在发展中不断被修正和取代。本书中，我会趁着新媒体研究范式改变之前，在它发展的头几十年记录它们。

[4] Thomas S. Kuhn, The Structure of Scientific Revolutions. 2nd ed. (Chicago: University of Chicago Press, 1970)——作者注

草绘新媒体：方法

本书中，我会在现代视觉和媒体文化的历史背景下对新媒体语言展开分析。新媒体是怎样依赖传统文化形式的？新媒体又是怎样从传统文化形式中分离的？新媒体有什么独特的手法来构建现实、面向用户、表达时间和空间？诸如矩形画面、移动视角、蒙太奇这些传统媒体的惯例和技术在新媒体上是怎样实现的？如果我们想做一次考据，把新的计算机媒体技术和旧的表征仿真技术联系起来，我们应该怎样界定重大的历史突破？

为了回答这些问题，我观察了新媒体的若干领域：网站、虚拟世界[5]、虚拟现实、多媒体、电子游戏、交互设备、计算机动画、数字视频、电影、人机界面等。虽然本书的重点在于陈述理论观点和历史结论，我还是会分析很多领域内关键的历史性新媒体对象。从美国商业经典到国际新媒体艺术家和收藏者，我都会有所涉猎。前者包括神秘岛、毁灭战士[6]、侏罗纪公园、泰坦尼克号等。后者包括 ART+COM、Antirom、jodi.org、George Legrady、Olga Lialina、Jeffrey Shaw、Tamas Waliczky 等。

[5]这里“虚拟世界”指计算机生成的三维互动环境。这个定义适用于所有现在已经面世的三维计算机环境，包括：高档的虚拟现实环境，它们配有头戴式显示器和现实图像的照片；街机、CD光盘、在线多人电子游戏；QuickTime虚拟现实电影；VRML（虚拟现实建模语言）场景；诸如“皇宫”“积极世界”等图形化聊天环境。——作者注
[6]ID software 的游戏产品，一直都走在 3D 显示技术前端。——作者注

文化内容计算机化，导致了新文化形式的涌现，比如电子游戏和虚拟世界。不仅如此，它还重新定义了已经存在的一些文化形式，比如摄影和电影。所以我也散乱地调查了视觉文化中计算机革命的影响。存储和操作图片的媒介由胶卷转变为计算机，这个过程怎样重塑了静态图像与动态图像的内在规律？我们文化中视觉语言的计算机化带来了什么影响？我们由此得到了哪些新的审美可能？

在解答这些问题的过程中，我描绘了艺术、摄影、视频、通信、设计、电影的历史。其中电影是 20 世纪最关键的文化形式。电影的理论与历史是我观察新媒体的绝佳镜子。本书将会探索以下话题：

• 电影历史和新媒体历史的比较；
• 数字电影的特征；
• 多媒体语言和十九世纪电影诞生前文化语言的关系；
• 屏幕、手持摄像机、蒙太奇在新媒体和电影中运用的对比；
• 新媒体和先锋电影之间的历史联系。

对照电影历史，本书将会从人性和科学的角度描绘新媒体的理论框架，包括艺术史、文学理论、媒体研究、社会理论、计算机科学等。我研究新媒体的总体方法可以称作“数字唯物主义”。我会从头开始构建新媒体的理论，而不是引用先验的理论。为了发现新的文化逻辑，我仔细探究了计算机硬件和软件的本质，以及在计算机上创造新文化对象所需要的操作。

大部分关于新媒体的著作充满了对未来的预测，本书则专注分析新媒体已经发展的现实。事实上现在新媒体艺术家和设计者的发展方向尚未明确。我希望我关于新媒体的这些理论不仅能帮助人们了解现状，而且而且能够为应用实验确立坐标。例如，“文化界面理论”这一章分析了打印、电影、人机界面这三项文化传统是如何塑造新媒体对象界面的。通过描述这些已经在新媒体中得到运用的传统元素，我分析指出了其他有待运用的元素和元素组合。“组合”一章列举了一批新的蒙太奇手法，为新媒体实验展示了一些新的方向。“数据库”一章中，我指出计算机数据库可以为新媒体叙事提供新的内容组合与审美可能，这是另一个发展方向。

虽然这本书没有预测未来，但是它还是隐性包含了新媒体发展的理论。这是在更大历史视角下观察新媒体的好处。我们开始观察新媒体发展至今的历史轨迹，我们推断这条轨迹今后将怎样延伸。“新媒体原则”一章描述了我眼中新媒体发展历史上最重要的几个趋势：模块化、自动化、可变性、转码性。

当然我们并不是盲目承认这些趋势的。理解塑造新媒体革命的逻辑过程，可以让我们发展出新的新媒体特性。先锋电影制作者在电影已经存在的情况下开发了新的视听叙事手法，与此类似，如今先锋新媒体艺术家的任务就是开创新的计算机媒体语言。如果我们的理论可以揭示现在“主流”语言的构造方法，先锋艺术家就可以更容易地发明创造。

草绘新媒体：组织

本书描绘了新媒体研究领域的一种可能性，希望能够促进新媒体研究（数字化研究）这一新生领域的发展。就像文学理论教材可能以叙事和声音的章节为重点，电影研究教材可能重在讨论摄影和剪辑，本书提出了新媒体理论中新范畴[7]体系的定义和精化。

[7]在哲学中，范畴（希腊文为 κατηγορια）概念被用于对所有存在的最广义的分类。比如说时间，空间，数量，质量，关系等都是范畴。在分类学中，范畴是最高层次的类的统称。它既不同于学术界对于学问按照学科的分门别类，又有别于百科全书式的以自然和人类为中心的对知识的分类，范畴论是着眼于存在的本质区别的哲学分类系统。——译者注

我已经把书分成了若干章，每章介绍一个关键概念或者关键问题。前面章节介绍的概念是后面章节分析的基础构件。我参考了与新媒体相关的各已有领域的教材，例如电影研究、文学理论、艺术历史。

很多电影教材可能从电影技术讲起，以电影流派结尾。本书的套路几乎一样，从新媒体的物质基础讲到它的形式。

术语：语言、对象、表征

我在本书标题中加入了“语言”这个词，但是这并不意味着我们在理解新媒体时需要从语言符号的结构开始。相反，现在大部分关于新媒体和计算机文化的研究都把重点放在社会学、经济学、政治学领域。我用“语言”这个词揭示本书与众不同的重点，即：新媒体新兴的表征习惯、重复出现的设计模式、关键的实现形式等。我也考虑过“美学”“诗性”这两个词，但是最终还是决定采用“语言”。“美学”有很多我不喜欢的对立——例如艺术文化和大众文化、美和丑、有价值和不重要等。“诗性”也承担了一些我不希望有的内涵。基于俄罗斯形式主义者 1910 年代的工作，1960 年代的理论家将“诗学”定义为研究某种特殊艺术形式具体属性的学科，就像叙事文学那样。例如，文学家茨维坦·托多洛夫在他的著作《诗歌导论》中说：

“与对特定作品的解读不同，它（诗性）寻求给意义命名，旨在探寻作品诞生的普遍规律。与心理学、社会学等科学相反，它只在文学自身内部探索规律。所以诗性是一条既‘抽象’又‘内在’的通往文学之路。”[8]

[8] 茨维坦·托多洛夫，《诗歌导引》，译：理查德·霍华德（明尼阿波利斯：明尼苏达大学出版社，1981年）。——作者注

与这种“内在”方式不同，我不认为新媒体的习惯、元素、形式是史上独特的，也不认为孤立地研究它们会很有意义。相反，本书希望能够将新媒体与文化的其他领域建立联系，无论是过去的元素还是现在的元素，列举如下：

• 其他艺术和媒体的传统：他们的视觉语言和他们组织信息、营造受众体验的策略等；
• 计算机技术：计算机的物理性质、计算机在现代社会中的使用方式，计算机交互界面的结构、计算机的关键软件应用等；
• 当代视觉文化：内部组织、图像志、图像学，还有我们文化中多种多样视觉现场的受众体验，例如时尚和广告，超市和艺术品，电视节目和宣传横幅，办公室和电子音乐俱乐部等；
• 当代信息文化。

“信息文化”这个概念是我发明的，可以和我们已经熟悉的另一个概念相对照——视觉文化。信息文化包括了不同场景和物品中呈现信息的方式——路标，机场和火车站的显示屏，电视机菜单，电视新闻的平面布局，书籍、报纸、杂志的版面设计，银行、旅馆、其他商业场所和休闲场所的室内设计，飞机和汽车的操作界面，计算机操作系统（Windows、Mac OS、UNIX）和软件应用（Word，Excel，PowerPoint，Eudora，Navigator，RealPlayer，Filemaker，Photoshop等）的界面等。与视觉文化相应，信息文化也包括信息组织方式、信息获取方式（影像学的相似概念）和用户与信息对象、信息呈现的交互模式等。

另一个值得一谈的术语是“对象”。整本书中我都使用了“新媒体对象”这一术语，而非“产品”“艺术作品”“交互媒介”或者其他术语。一个新媒体对象可能是数字照片、数字电影、虚拟三维环境、电子游戏、超媒体DVD、超文本网站、万维网等。“对象”这个术语和我试图描述新媒体通用规则的目的相一致，这些规则同样也适用于所有的媒体类型，适用于不同的信息组织形式，适用于所有的信息规模。我用“对象”这个词也是为了强调我对于文化的广泛领域都很关心，而不仅仅是新媒体艺术。其次，“对象”是一个计算机科学和计算机工业中的标准术语。在计算机的面向对象编程语言中，“对象”强调语言的封装模块特性。这些语言包括C++、Java、面向对象数据库、微软Office产品中的对象链接和对象嵌入技术等。这就实现了我的目标：在计算机文化的理论中采用计算机科学的术语和范式。

此外，1920 年代俄罗斯先锋艺术家们也使用了“对象”一词，我希望它也能够包含这一层内涵。俄罗斯建构主义者和生产主义者都把他们的创造叫做“对象”（对象、结构、语言[9]等）而非艺术品。就像建筑领域的包豪斯，先锋艺术家更愿意成为工业设计师、图像设计室、建筑师、服装设计师，而不是成为传统艺术家，像传统艺术家那样为博物馆和私人收藏打造独一无二的艺术品。“对象”更多意味着工业化规模生产，而不是传统艺术家的手工作坊。它也意味着艺术家愿意将合理的劳动组织和工程效能代入他们的艺术创作之中。

[9] 原作中作者列夫·曼诺维奇在这里生造了三个英文单词，来模拟俄语术语的发音，分别是 vesh、construktsia、predmet——译者注

对于新媒体对象，以上所有的内涵都是很有价值的。在新媒体的世界，艺术和设计之间的界限很模糊。一方面，很多艺术家以商业设计为生；另一方面，职业设计师往往通过系统性实验和创立新标准新风格推进新媒体语言的发展。“对象”的第二点内涵，关于工业生产的内涵，也适用于新媒体。很多新媒体工程是大型团队共同推进的（与单人制片人、小团队、经典好莱坞时代的制片体系不同）。很多新媒体对象都销售了逾百万份，例如一些流行的电子游戏和软件应用。它们需要适应花样繁多的硬件软件标准，这样新媒体领域的特征使得它需要大规模的工业生产。[10]

[10]软件标准包括但不限于操作系统（UNIX、Windows、Mac OS等）、文件格式（JPEG、MPEG、DV、QuickTime、RTF、WAV等）、脚本语言（HTML、Javascript等）、编程语言（C++、Java等）、通信协议（TCP-IP等）、人机交互规范（对话框、剪贴板、提示帮助等）、一些不成文的惯例（例如，有十年多图像大小都是固定的640×480像素）。硬件标准包括存储介质格式（极碟、爵士可扩充硬盘、只读光盘、数字光盘）、接口类型（串行接口、通用串行总线、火线），总线架构（外部控制器接口）、随机存储器类型。——作者注
极碟是美国埃美加（Iomega）公司所发明的一种高容量软式磁盘机，使用具有较坚固外壳的特制高容量软碟片，并利用部分硬盘中使用的技术，制成的个人电脑储存装置。爵士可扩充硬盘是美国埃美加(Iomega)公司利用硬盘技术制成的可移除存储设备。通用串行总线即日常生活中俗称的 USB 接口。火线（FireWire）接口是IEEE 1394的别名，是由苹果公司领导的开发联盟开发的一种高速传送接口。外部控制器接口是是一种连接电子计算机主板和外部设备的总线标准。当代计算机主板上的大部分插槽都是外部控制器接口规范插槽。——译者注

最后，也是最重要的，我用“对象”这个词暗示1920年代先锋艺术家们的实验室实验概念。现在，越来越多的艺术家转向新媒体，却没有多少人愿意针对新媒体元素，针对最基本的信息组合、表征、生成策略，展开系统的、实验室级别的研究。而这正是1920年代俄罗斯福库特马斯设计学院和德国公立包豪斯学校的先锋艺术家们所做的研究。他们探索了他们时代的新媒体：摄影、电影、新式打印技术、电话通讯等。现在，发明“可读写光盘”“数字电影”这些新产品的直接诱惑实在太大了，几乎没有人能够抵挡住这样的诱惑，转而专注于寻找镜头、语句、词语、甚至字母在新媒体概念中的等价物，去寻求惊人的发现。

第三个贯穿本书且需要点评的术语是“表征”。近几十年人类文明发展出了不少新生的文化对象，我使用“表征”一词，就是希望能够引入对这些文化对象运作方式的理解，复杂而又细致的理解。新媒体对象是文化对象。所以，任何新媒体对象，无论是网站，电子游戏，还是数字图片，都是在表征或构建一些外物，例如：实实在在的物理对象、其他文档中的历史信息、文化整体或特定社群的范畴体系等。就和其他文化表征一样，新媒体表征也难免有倾向性。它们牺牲其他内容，只描述出物理现实的部分特征。它们在诸多世界观中选择一个，在大量范畴体系中表达其一。对于操作系统和软件应用，它们的软件界面也是表征形式。本书中我会通过陈述这一点进一步论述新媒体表征的倾向性。用特定方式组织数据，新媒体就可以突出某种描述人与世界的模型。例如，目前组织计算机数据的两大常用方案分别是树形目录文件系统（自1984年麦金塔[11]计算机的图形用户界面起）和扁平的超链接网络（1990年代诞生的万维网）。它们采用了根基不同、截然相反的方式表征这个世界。树形目录文件系统认为这个世界遵循逻辑分层的秩序，每个对象都有明确不同的位置。万维网模型认为每个对象都一样重要，每个对象都可以和其他对象相联系。[12]此外，界面也可以凸显某种数据访问方式，与特定艺术作品和媒体技术相联系。例如，1990年代的万维网将网页作为数据组织的基本单元，而Acrobat软件给文本文档提供了视频播放功能。界面起到了旧文化形式和媒体的“表征”作用，强调部分内容，轻视部分内容。

[11]麦金塔电脑（Macintosh），俗称 Mac 机，也称作苹果机或麦金托什机 ，是对苹果 PC 中一系列产品的称谓。首款 Mac 于 1984 年 1 月 24 日发布，是苹果公司继 Lisa 后第二款具备图形界面的 PC 产品。——译者注
[12]首先，目录文件结构并不诞生在 1984 年，在图形界面出现以前，树形文件结构早就广泛存在。在计算机领域中，文件目录结构与超链接网络也不是对立关系。每一个位于目录中的文件都有自己的链接地址，网络中超链接的相对关系也需要依靠目录结构来表征。在计算机工业世界，两者分工合作，各有所长。而且你中有我，我中有你，互相交融，远非对立。译者认为作者在这里对两种数据组织方式有片面的处理。——译者注

我发现，在描述新媒体语言时，“表征”一词的对立意义非常有用。给“表征”选择不同的对立意义，“表征”就能体现出不同的内涵。这些对立意义的介绍分散在本书的各个章节，我总结如下：

1. 表征——仿真（“屏幕”小节）。这里，“表征”意味着各种屏幕技术应用，例如后文艺复兴绘画、电影、雷达、电视等[13]。我将“屏幕”定义为一个矩形表面，它展现虚拟世界，但同时也是用户物理世界中的一个实际存在，不会完全遮蔽用户的视野。“仿真”则指让用户完全沉浸在虚拟世界中的技术，如巴洛克的耶稣教堂、十九世纪的全景图片、二十世纪的电影院等。
2. 表征——控制（“文化界面”小节）。这里，我把两种图像对立起来，一者是虚构世界的视觉表征，一者是控制面板（例如，图形界面及其图标、菜单）的细节模拟。控制面板使用户可以操作计算机，这种新型的图像可以称作“界面图像”。表征和控制这一组对立对应着深度和表面的对立。例如，计算机屏幕，在表征情境下是通往虚拟空间的窗口，在控制情境下则是一个扁平的控制面板。
3. 表征——操作（“遥控”小节）。创造幻觉（时尚、写实油画、西洋镜、军事诱饵、电影蒙太奇、数字合成等）的技术和执行操作的技术存在对立。执行操作的技术可以让用户通过表征（地图、建筑图纸、X射线图、远程监控等）操作真实对象。我把执行操作的图像成为“工具图像”。
4. 表征——通信（“遥控”小节）。表征技术（胶卷、音频、录像磁带、数字存储格式等）和实时通信技术（电报、电话、电传[14]、电视、远程监控等）构成对立。表征技术可以让人创造传统美学对象，这些对象存在于确定的时间或空间，并且涉及它们之外的事物。现在人与人之间的沟通交流越来越重要，“通信文化”形式一般不产生任何文化对象，新媒体迫使我们重新思考传统上文化和对象的等价关系。[15]
5. 视觉幻觉艺术——仿真（“幻想”一章的引语）。这里，幻觉艺术包含“屏幕”小节中表征和仿真的双重意义。幻觉艺术结合了传统技术和旨在创造虚拟真实视觉的技术，如视角化绘画、电影、西洋镜等。这里的“仿真”指除视觉表现外，计算机模拟现实其他内容的方法，如物理对象的移动、自然现象中的物体形变（水面、烟雾等），动机、行为、人类的言谈和语言表征等。
6. 表征——信息（“形式”一章的引语）。新媒体有两个对立的设计目标，一者像传统小说那样，希望用户沉浸在虚拟世界；一者希望给用户提供获取信息的高效渠道（搜索引擎、网站、在线百科等）。

[13]这些设备或艺术品都需要引入屏幕技术。——译者注
[14]电传是一个合成词，是远距离打印交换的缩写形式。电传既具有电话的快速，又具有打字机的准确，尤其是当电文中有数据时，这种优点表现得特别明显。——译者注
[15]古时人们沟通会产生书信等具体的文化对象，这些文化对象往往记载着时间、地点等重要的外部事物信息。但是现在，如果没有刻意地录音、存储，大量信息就耗散在电波和光纤里，不形成文化对象，也不指涉外部。——作者注

导语

本文力求在万字篇幅内尽可能清晰地介绍计算理论的基本概念和最新发展。

普通科学读物总是逻辑清晰环环相扣，但是这实在把读者累坏了。本文作为心疼读者的二逼科学读物，目标是希望读者在看不懂第一章的情况下仍有可能把第二章看下去。对于涉及到的新兴专业术语，作者将做出尝试性的汉语翻译，用汉语的语法、汉语的风格、汉语的词汇展现全文。

可计算性问题

现实生活中有很多计算类的问题，考试要计算成绩，购物要计算价格，与佳人约会要算好时间，出门旅行要算好乘车方案。计算的结果不局限于数字，也可以是方案，可以是图像，可以是子弹穿过木块的运动轨迹，也可以是组成新款计算机的电路设计。只要一份答案可以用语言描述，它就可能是某个计算过程的结果。

可是世界上并不是所有问题都能算出结果。姑娘的头发有多少根，这个问题很难，但是交给机器做，一根一根数，数一根拔一根，总是能数完的。这个问题就可计算。但是姑娘明天心情如何，这个问题就根本没办法计算了。事实上就连她们自己也弄不清楚。

那么，什么问题是可计算的？什么问题是不可计算的？我们能不能在数学上给“可计算”下一个精确定义，然后用数学手段研究万事万物的可计算性？

历史

这个问题的源头早在17世纪就被提出来了。欧洲大陆近现代数学的共同导师莱布尼茨，在发明了相当完善的微积分体系后，马不停蹄地试图再发明出一套数学机制来判断任何逻辑陈述的真假。但是这个问题的难度已经远远超出了莱布尼茨的时代，首先，莱布尼茨缺乏数学工具去描述逻辑陈述本身；其次，也没有成熟的逻辑知识去帮助他理解逻辑。但是他已经隐隐地感受到，有必要创造出一种“形式语言”来描述问题。

世界上最后一个通晓所有数学领域的数学家希尔伯特，用他的天才智慧和完美主义创造了完善的希尔伯特公理体系，构建了完整的逻辑规则，在一阶逻辑上找到了既可靠又完备的演绎系统。1928年，在逻辑学基础上，他正式提出了这个问题，数学史上大名鼎鼎的判定问题，德语Entscheidungsproblem，英语Decision Problem：我们能不能找到一种算法来判定一切一阶逻辑陈述的真假？

“算法”“一阶逻辑”这样的字眼实在晦涩费解，事实上算法我们就可以理解为一种可行的方法或机制，而一阶逻辑是数学中公理系统的标准形式逻辑，大部分判断句都可以用一阶逻辑的陈述来表达。而那种经常会产生悖论的“整数和偶数一样多”这类蕴含着“无穷大”概念的判断，则不在一阶逻辑范畴之内。这些给数学和逻辑添麻烦的魂淡问题，我们今天就先不理会了。

所以我们可以用更形象的语言来描述这个问题，这个问题是在问我们，我们能不能造出来一个黑箱子，做对这世上一切判断题？

咦？这个问题看起来强度有点弱啊，我们刚才是可以数女生头发数目的，我们是可以做解答题计算题的，可是这个判定问题只对判断题有要求。

没关系，很多计算题也可以转化成判断题。我们只要不断地向黑箱子问：“她有1根头发吗？”“她有2根头发吗？”……只要你寿命够长能把问题问完，总有一天，你会得到正确答案。一上来就直接考虑计算题，对我们而言太难了，所以我们先从判断题开始吧。

形式语言与图灵机

语言

莱布尼茨需要一种工具来描述问题。描述问题，当然需要语言。什么语言呢？中文？Engish？二进制数码1111111111？printf(“C++”)？吙煋呅？都不是。下面我要隆重推出高端大气上档次的形式语言，一大波定义即将袭来，大家耐耐性子，文科生也能看懂的~

直观上说，语言都是字符串组成的，这里的语言也不例外。我们假设字母表Σ为任意有限集合，表示空串，记为，。

定义：语言为的任意子集。

举个例子，假设字母表 = ，那么，把所有的并起来，就得到。这样所有有限长的SB串就都包括在\(\Sigma^\)里了。我们取\(\Sigma^\)的任何一个子集，就都构成一个语言。

全串，全串，只有一个的串，和一样多的串，……他们都是字母表上的语言。给定任何一个字母表上的字符串，给定一个上的语言，判断是否属于，也就等价于做一道判断题。

图灵机

阿兰·图灵，英国杰出的同性恋数学家，二战时德军密码的破译者，计算机科学的宗师，在1936年5月发表了一篇划时代的论文《论可计算数及其在判定问题中的应用》。判定问题就是我们上文提到的希尔伯特判定问题；可计算数，就是我们上文提到的可以计算出来的答案。图灵为了解决这个问题，发明出了一台惊世骇俗的机器模型，说只要是这台机器能计算的，就是可计算的；这台机器能判定的，就是可判定的。此机一出，判定问题彻底终结，江湖人称“图灵机”。

说到这图灵机啊，结构十分简单。一条长长的纸带，一个读写头，读写头指向纸带上的一个格子，可以在纸带上自由地左右移动，这就没了，和我们这一代人小时候常见的磁带机差不多。当然了，也有区别。纸带是无限长，划分成无限多个格子，每个格子里可以填一个字符。这里也可以填，也就是啥也不写，空在那。读写头有个状态，初始时，读写头的状态是，位于纸带上某个字符之上，读写头会根据和这两条信息，决定做出三件事：

1. 把x改写成字符y
2. 向左或者右移动一格
3. 把自己的状态切换为某个

这种决定不是读写头一拍脑袋想的，而是我们事先设计好的。我们事先就决定好了一台图灵机的字母表、状态集、 读写头在每个的情况下做出什么动作，机器在达到哪些状态的时候停下。

好了，一台图灵机的结构就这么简单。让我们来看几个例子吧。

识别与判定

我们假设图灵机有两个停止状态，当读写头切换到这些状态的时候，图灵机就停止了。如果图灵机停在，我们称它接受（accept）了输入串；如果停在，我们称它拒绝（reject）了输入串。

定义：如果存在一台图灵机可以接受语言中的所有串，我们称是可识别的。

定义：如果存在一台图灵机可以接受中的所有串并拒绝中的所有串，我们称是可判定的。

我们现在把都设置成，也就是二进制码。设为所有全0串的集合，那么我们很容易发现是可判定的。

证明：构造一个图灵机，它有3个状态, , 。再设置读写头的工作函数，使得。这个图灵机就可以判定。

这个例子太简单，大家可以试试看怎么构造图灵机判定所有回文串的集合。

此外，这个世界上还有很多奇葩问题——或者说语言——是只能识别不能判定的。比如说大名鼎鼎地停机问题：给定一台图灵机和一个输入串，让图灵机能在这个输入串上运行，请问这台图灵机能停下吗？

我们可以很容易地识别出能停下的情况，只要模拟这台图灵机的运行情况就可以了，一旦停下就对外声称这个图灵机可以在这个输入下停止；但是如果不停呢？对不起，数学家已经证明，没法识别。

理论、算法、应用

我们现在手头已经有了语言和图灵机这两大工具，已经可以开始建设计算机科学的理论大厦了。在这之前，我认为非常有必要提一提理论的意义。

昨天小师妹段萌软就问，理论是神马？理论可以吃吗？

很遗憾，大部分第一流的理论研究不仅不能吃，甚至都是没有“用”的。它离我们的现实生活实在太遥远，写不出百度也造不出 QQ，不能让我们的选课快上一秒，也不会让情侣间少丢几条短信情话。

理论研究的问题往往是，“如果明天的天气可以预测，那么女孩儿的心情也可以预测”这种命题？这个问题如果证明了，就是理论界的重大突破，我们只要能预测天气，就能猜对女孩儿心思了。多么美妙啊！可是，现实中大家既不能预测天气也不能预测女孩儿的心思，所以这个命题不管被证明还是被推翻，对于我们的现实生活一点帮助都没有。大家和妹子交往，还是要看天吃饭。

哎，我把理论说得也太不堪。事实上理论不仅对于现实有深远指导价值，其本身蕴含的智慧更是人类精神文明的伟大见证。

计算机科学的宏伟格局，理论、算法、应用，三位一体，缺一不可。

譬如我们想为广大懒助教提供一个自动批改试卷选择题的程序，这一程序就是应用。为了做出这个应用，我们需要设计一个识别正确答案的算法，而理论告诉我们这个问题是可判定的，我们一定能找出一个算法解决问题。

应用有时会驱动理论的发展，譬如，如果助教希望这个程序还能够批阅解答题，那么我们就需要为解答题设计新的算法，这可太难了，我们的程序得能理解语义才行。能否让程序去理解自然语言的语义，这就是一个理论问题了。只有理论解决，我们才能够提出切实可行的算法，来实现这一应用。

相反，理论的进步也可以指导应用的发展。比如，理论告诉我们，一个问题是不可解的，那我们设计算法时就可以避开这个地雷。又如，理论告诉我们，在二维平面上随机游走会无限次经过原点，那么我们在设计算法的时候，就可以设计回到原点后程序的种种行为，不用担心无法返回。

诚然，理论是一切方法和应用的基石，就像物理理论是电灯、电脑、汽车、楼房的基石一样。没有理论支持，我们也可能造出电灯泡。但有了理论支持，我们就能知道电灯的原理，就可以研发各种新款电灯。另一方面，理论还能证明使用电灯既不会导致核爆也不会导致怀孕，这样大家用起来才安心，才能确保在重要场合使用电灯不会带来一些难以预料的副作用。

然而，大部分理论就像我前文所说，是基本上没用的。理论就像法拉第口中的婴儿，只有长大了才能彰显出独特的价值。

计算的时间复杂度

P vs NP

任何计算过程都需要耗费时间与空间。对于图灵机而言，读写头移动的次数就是消耗的时间，读写头走过的纸带格子数就是占用的空间。如果输入串的长度为，图灵机的时间消耗不大于，我们称这个语言可以在时间内得到判定。如果是关于的线性函数，我们称该语言可以在线性时间内得到判定；如果是关于的多项式函数，我们称该语言可以在多项式时间内得到判定；如果是关于的指数函数，我们称……后面就不用我多说了吧。

对于那些可以在多项式时间内得到判定的语言，他们组成的集合就是，单词多项式polynomial的首字母，大名鼎鼎的。

是语言的集合，这些语言的判定问题我们俗称问题。

至于那些可以在多项式时间内得到验证的语言，它们的集合就叫做。

什么叫验证？什么叫？直接说太麻烦，让我们看个例子吧。

问题：OrangeCLK 期末论文写不完了，想找人代写。可是这事儿可绝对不能让老师知道，所以一定要找他的死党。OrangeCLK 是个 geek，他居然用数字来表示他和朋友间的好感度。他说了，只有好感度超过 100 的朋友才算死党，现在给你一份包含陈力坤所有朋友好感度信息的数据表格，问他能找到个朋友帮他代写论文吗？

这是一道不折不扣的判断题，而且它在多项式时间内就能做完，图灵机只要一一扫过那些数据，数数有没有个大于 100 的数据就可以了。图灵机可以很聪明地数数，它现在纸带某个空白的地方写上，并且每扫描一个数据就擦除掉，每发现一个满足要求的数据就跑到写的地方给减一。如果能减到 0，图灵机停止运行，OrangeCLK 论文得救，如果图灵机看遍所有数据，原先写的地方还是个正数，那 OrangeCLK 就只能挂科了。好，这里给读者留个题目，图灵机怎么做加减法呢？大家有兴趣就自己动手设计个函数试试吧。

我们看到，给定输入，存在一台图灵机先验证是不是这样的格式，然后执行上述算法，就可以在关于的多项式时间内判断问题的是或否。所以 属于 P。

问题：OrangeCLK 提高了对代写人选的要求，他们不仅都要和 OrangeCLK 关系好，彼此好感度也要超过 100 才行，否则可能会内讧。还是给出好感数据表和需要人数，问能不能找到这样的个人？

先来浇一盆冷水，傻×的 OrangeCLK 死活也找不到这个问题的多项式解法。于是他就捉急了，因为他的智商只能做多项式时间的运算。这时候有一位大神告诉他，咦，你挑这个人就 OK 啦。于是 OrangeCLK 开开心心地把大神给他的人方案一拿，把对好感度数据一查，果真，包括他本人在内的这个人彼此好感度都超过 100，我们看到这个数字显然是多项式的。大神给的人方案，就好比是一串验证辅助串，有了这样一串验证辅助串，由于图灵机对每一个数字大小判断的元操作也是多项式级别，我们就能构造出一台图灵机，基于输入，在多项式时间内验证是否属于。

所有可以借助验证串在多项式时间内验证的语言，组成了集合，对应的问题叫做问题。

中的是 nondeterministic 的意思，意指不确定机。不确定机和上文我描述的图灵机有一点区别，它表头的转换机制不是确定的，看到一组，它可能有几个不同的操作方式，而且每一步都有这样相同多样的操作方式，最后只要有一种碰上停止状态，整个程序就告结束。也可以理解为，所有可以被不确定机在多项式时间内判定的语言集合。和验证版本的定义等价。

我们很在乎多项式，因为多项式是我们可以承受的计算时间。多项式之上是指数，指数级的时间复杂度是几乎没有实际计算价值的。举个例子，如果一个问题对于长度为的输入串需要运行步，那么对于长度为 80 的串，这台图灵机就要跑步，，大概是全宇宙原子总数那么多，宇宙的寿命还不到秒。所以，多项式才意味着可计算，超出多项式，我们就当不会做。

很显然，是的子集，那么，和相等吗？存在一个语言属于却不属于吗？

这就是世界闻名的问题，是21世纪数学最重要的十大问题之一，五大问题之一，三大问题之一，一大问题之一。

太重要了，可也太难了，我们既找不到方法在多项式时间内就能判定 OrangeCLK 能否找齐代写论文的人，也不能证明这样的方法不存在。天下所有的问题，都像这幽灵一般让人捉摸不透。

NPC，问题归约

？哈哈，这可不是打游戏的时候遇到的 NPC，它的全名叫做 NP-Complete，中文雅号完全。和一样，也是一个语言的集合。

我们都聊到了，OrangeCLK 还在纠结找人代写论文的严肃问题。机智の OrangeCLK 发现，他面临的问题其实可以转化。如果把每个人都看成一个点，两人之间的好感度如果超过 100 就连一条边，如此我们就得到了一张数学意义上的图。原问题就转化为，能不能在这张图中找到一个完全子图？看到没有，一个偷鸡摸狗的作弊问题瞬间被转化成了一个高端大气上档次的数学图论问题。数学家们对这个问题可是颇有兴趣，可惜，要找这个问题的多项式解法？他们也不会做。记得我在探讨理论、算法、应用三者之间关系的时候怎么说来着？理论大部分时候都是没用的，它的“精髓”就是把一个大家都不会的问题转化为另一个大家都不会的问题。我们打小从数学书上就学着要化未知为已知，可是人生总是如此的艰难，现实中哪有那么多已知呢？在计算理论研究中，真的勇士，敢于面对惨淡的现实，敢于面对凶残的无知。科学家不断开拓新领域，做着化未知为未知的转化，这种工作，叫问题归约，同时也是在给问题分类。同一类的问题，具有相同的时空性质，整个类的问题都休戚与共同生共死。于是，一个问题得解或者是得证无解，就会推进许多领域大量问题的解决。不管问题我们现在会不会做，大家都致力于打通问题之间的任督二脉，这样在问题的茫茫荒原中，将来只要有一个旷古烁今的灵光一现，大批量的问题都会瞬间得到解决。敢于在一片未知之中闪转腾挪创造科学结构，需要多么大的胆略与魄力！这就是人类伟大的远见卓识壮志雄心。

我们看到，代写论文问题被归约到了完全子图问题。只要我们能在多项式时间内做出完全子图问题，我们也一定能在多项式时间内做出代写论文问题，因为这个归约过程本身的计算也是可以在多项式时间内完成的。

下面我要公布一个让你合不拢下巴的事实：所有问题都可以归约为完全子图问题。

啥？没震惊？那我换个说法，只要我们在多项式时间内解决了完全子图问题，天下所有的问题就都能在多项式时间内解决。没错，是所有！这样和就能画上一个大大的等号，21世纪最大数学难题就可以告破。

原来完全子图问题如此特别，我们有必要引进一个新的类型。刚才说了，计算理论的一项重要工作就是给问题分类。于是应运而生，中的任何一个问题得到多项式解决，就和相等了。

科学家们已经发现了一大堆问题，显然，它们非常争气，都没有被人类解决。

NP 难

这货英文名叫，我这篇文章，有一半动机都是为了这个坑货而写。

这玩意儿坑在哪儿呢？学术界到现在对于居然没有一个统一的定义！各个山头的大佬们众说纷纭各持己见。我今天就来努力梳理一下。

前面讲到我们只讨论判断题，判定问题。现在呢，我们可以考虑解答题了，专业叫法，搜索问题。

图灵机做判断题，无非是停机，并且停在一个接受/拒绝的状态上，根据停机状态来判定答案。而搜索问题要怎么应对呢？这需要图灵机在纸带上写出答案。输入“2+2”，要能输出“4”。简而言之，除了是/非类型的问题，就是搜索问题，意指在茫茫大海中寻找答案。

既然名字叫难，不说比还难，起码不能比容易。怎么度量难易呢？可以用问题归约啊，如果A解决了，B就也可以解决，我们是不是说B不会比A难？换言之，A 至少和 B 一样难。所以难是这么定义的：至少和中最难的问题——问题——一样难。如果一个问题可以在多项式时间内归约为另一个问题，那么就属于难。如果问题能在多项式内解决，则中的某个问题也能解决，进而所有问题都能够在多项式内解决。

乍一看和挺像，区别就在于问题类型。只包括判定问题，难可以包括搜索问题。有一些学派认为难包括普通的判定问题和搜索问题；有一些学派认为难还应该包括不可判定问题比如停机问题；还有一些学派认为难不应该包括判定问题只能讨论搜索问题。这些分类方法都有合理之处，最终谁将胜出，还看历史选择。

但是，总有那么些问题是大家公认属于难的，比如最大完全子图问题：给定一个图，求出它最大完全子图中有多少个节点。很显然，这是一个搜索问题，而且一旦这个问题有多项式解，完全子图也就不在话下了，OrangeCLK 的论文也就得救了。

这里宕开一笔，年幼时看科学，总觉得科学与艺术不同。艺术是审美和表达，充满了主观的想象与个人的判断；而科学是客观和真理，奠基于严密的逻辑和重复的实验。年岁渐长，见识益多，渐渐觉得艺术有十分客观之处，科学也有十分主观之处。审美是有一定普适标准的，音乐、美术、文学、戏剧，美好的作品总是蕴含着跨越种族跨越国界的共同感动。科学也根本不客观，科学的理论到底是建立在条条假设上的逻辑推导和计算演绎，不同人观念不同，持有的先验假设不同，构建出的理论体系也就不一样。相信哪个理论，选择哪个理论，是一件很主观的事，也是一件随着历史流变的事。艺术感动人心，科学可以证伪。这是二者在我心中最核心的价值。

计算理论的发展

刚才探讨的只是计算理论的基石，计算理论主要包括包括形式语言自动机图灵机、可计算性、计算复杂度三个部分。广义说来，算法设计、计算经济学、计算生物学、机器学习理论等都属于理论范畴。刚才我们探讨了计算复杂度的时间维度，事实上也有空间复杂度的相关研究，类似于时间，我们有(PSPACE)，(LOGSPACE)（简称L）等复杂类。

除了图灵机外，另一个常用的计算模型是电路，研究电路的复杂性很多时候比图灵机方便实用，这也是研究的重大方向。

姚期智教授提出了通信复杂性这个领域，描述交换信息、多机器共同运算的复杂性。

现实生活中由于很多问题得不到完美的解决，人们创造性地发明了很多近似算法和随机算法来解决问题。这些算法不一定能得到最优解，但是离最优解差得不远。那么为了度量算法解和最优解的差距，为了度量得出正确解的概率，为了给这些算法一个理论基石，关于近似算法和随机算法那的理论研究也就顺理成章了。

除了电路、通信、近似、随机，广大理论计算机科学研究者还在努力开拓新的领域，把问题归约到越来越遥远的地方。虽然大部分难题都尚未取得进展，但是已经阐发出很多实用算法，对我们的世界改变良多。

量子计算理论也有不错的发展，取得了一系列诸如这样的重要结果，全球各大高校和公司也都在加紧制造量子计算机进行量子计算的实验。清华大学交叉信息院量子信息中心（CQI）在这一领域卓有建树，部分方向领跑全球。

就我个人看来，物理理论也好，计算理论也好，都基于数学但是有超出数学的部分。给全所有定理，数学也无法预测复杂系统的运动情况；给定所有运算规则和其实状态，数学也未必能预测某些问题的计算结果。计算领域和物理领域一样，有一些数学无法解释预测的现象。很多数学家不相信的东西，我们可以选择去相信、去实验。在数学力所不及的地方架起计算理论的新结构，发现计算的规律，是一件多么具有挑战性的事啊！

鸣谢

• 感谢 John Steinberger 的 Brutal and Swift Introduction to Computer Science课程。
• 感谢Michael Sipser的名著Introduction to the Theory of Computation。
• 感谢课程指导老师王跃宣。
• 感谢与我讨论NP-Hard定义的寿鹤鸣。
• 感谢段萌软提出她对理论的看法。
• 感谢读者！