电影《模仿游戏》(The Imitation Game)的走红让公众的注意力集中到了20世纪最重要的数学家之一艾伦·图灵(Alan Turing)身上。这部电影讲述了图灵在战争时期的密码破译和个人生活。我也对他对科学的独特贡献和他对MATLAB的影响感兴趣®．
图灵机
1936年，作为剑桥大学国王学院的一名24岁的学生，图灵发表了一篇后来成为现代计算机科学基础的论文:《论可计算数及其在计算机科学中的应用》Entscheidungsproblem粗略地说，Entscheidungsproblem，或《终止问题》问"有没有可能开始一个永远不会结束的证明"1928年，伟大的德国数学家大卫·希尔伯特(David Hilbert)首次提出了这个问题。希尔伯特向数学家提出挑战，要求他们将数学证明的概念形式化，并确定是否有可能陈述一个既不能证明也不能证伪的命题。
图灵通过引入理论机器使证明的概念形式化。这台机器有有限数量的状态和一个无限的磁带，包含有限但无限数量的0和1。一组规则(我们今天称之为它的程序)将使机器从磁带中读取一个0或1，然后可能将其擦除并在其位置上写入一个新的符号，将磁带向左或向右移动一个位置，并转换到一个新的状态。这就是机器所能做的。图灵证明，这样的机器能够证明任何可以用更复杂的形式证明的东西。
当图灵发表他的论文时，他在数学逻辑领域还完全不为人知。他的做法是前所未有的。他用他的形式主义来证明希尔伯特Entscheidungsproblem没有解——换句话说，有可能陈述数学命题，其尝试的证明永不终止。
我们现在所知的“图灵机”的含义远远超出了这个深奥的结果。它们是现代计算机科学的基础，事实上，也是我们今天使用的实际计算机的理论基础。
图灵的论文发表于1936年，与另一篇关于Entscheidungsproblem由美国逻辑学家阿隆佐·丘奇，普林斯顿大学教授提出。图灵花了两年时间在丘奇手下工作，并在普林斯顿大学获得了博士学位。在此期间，他还建立了机电二进制乘法器的四个阶段中的三个阶段，并开始了他的密码学研究。
布莱切利公园和英格玛
1939年，图灵回到英国，加入了布莱切利公园新成立的绝密政府代码和密码学校。这个组织的任务是破译德国军队用于与战场上的部队，特别是海上uboat上的部队通信的密码。其中一个密码使用了德国密码机Enigma。
英格玛机器的早期模型自20世纪20年代开始使用，所以它们的基本原理并不是秘密。德国军方最初使用的模型细节是由波兰密码局的波兰数学家玛丽安·雷杰夫斯基(Marian Rejewski)在1931年逆向设计的。这台机器有一个类似打字机的键盘，一个插板，三个转子，一个反射器和一个显示板。当按下一个键时，该字母的电信号通过插板、三个转子和反射器。然后，它通过反方向的转子返回，并通过插板返回，在那里它照亮显示器上的加密字符。然后至少有一个旋翼转动，以便下一个字符使用不同的电路。
每天，从一组5个转子中选出3个。它们的初始位置是根据消息开头传输的代码设置的。这些设置与插接板和反射器的设置一起决定了消息加密。可能的初始配置的数量几乎是1.6×1017．
在波兰情报部门的基础上，图灵设计了一种机电机器，被称为炸弹机。此机器将消除生成解密消息的配置，这些消息未能包含指定的婴儿床，或给出明文。例如，数字通常是拼出来的，所以单词“静脉，表示“一个”，是一个经常使用的婴儿床。
图灵的团队在解密德国信息方面非常成功，以至于英国军方不得不掩饰他们的回应，以掩盖他们来自截获通信的事实。
炸弹机还不是一台成熟的计算机——它没有内存，通过设置开关和插入接线来“编程”，它的逻辑单元是继电器。
自动计算引擎
战争一结束，许多国家的大学和研究实验室就开始建造存储程序电子计算机。1946年2月，当图灵在特丁顿的国家物理实验室(NPL)工作时，他展示了自己的存储程序机设计，他称之为ACE(自动计算引擎)。
ACE的设计是基于图灵在可计算性方面的理论工作，以及他在布莱切利公园(Bletchley Park)的密码破译经验，在那里他参与了巨像(Colossus)机器的开发。巨像是用来帮助德国洛伦兹密码的密码分析。它通常被认为是世界上第一台数字计算机，但由于它没有内存，所以不是存储程序计算机;它是由纸带、插头和开关编写的。图灵希望ACE可以由建造巨像的工程团队来制造，但《官方保密法》阻止他解释他对ACE的设计可以实际实现。
图灵对ACE的设计比其他地方提出的机器设计要雄心勃勃得多。它包括一种叫做缩写计算机指令的早期形式的编程语言，图灵相信大部分工作可以在子程序中完成，不同的子程序集用于不同的任务。他的ACE的确是受到通用图灵机的启发。
国家物理实验室的管理层并不知道布莱切利公园的计算成果，他们不愿意批准图灵精心设计的项目。
图灵对官僚主义的拖延感到沮丧，最终离开了国家物理实验室。1948年，他接受了曼彻斯特大学的一个职位，那里的计算机发展速度更快。
对矩阵计算越来越感兴趣
1947年，当图灵还在国家物理实验室工作时，他写了一篇题为《矩阵处理中的舍入误差》的论文。那时还没有人有使用自动数字计算机的实际经验。在此之前，所有的计算都是手工完成的。虽然论文中使用的术语与我们今天使用的不太一样，但13节的标题可以作为现代矩阵计算课程的教学大纲。
例如，第3节是“矩阵的三角分辨率”。主要结果是
三角形分辨率定理。
如果矩阵的主余子式一个都是非奇异的，那么下三角矩阵有唯一的单位吗l，为唯一对角矩阵D，具有非零对角线元素，以及唯一的单位三角矩阵U这样A = ldu．
当我们吸收D成U这就变成了陆函数的MATLAB。这个结果不是图灵独创的。它也出现在冯·诺伊曼和戈德斯坦1947年的另一篇论文中，图灵参考了这篇论文，在此之前，它也出现在其他论文中。
第四节是“排除法”。用文字描述了高斯消去，并与LDU“分辨率”相关。事实上，解决了一组n讨论了涉及\(\frac{1}{3}n³+ O\左(n²\右)\)乘法的方程。但书中没有提到转向的必要性。
在第8节“病态矩阵和方程”中，图灵首次在文献中使用了术语“条件数”，并介绍了它的一些性质。然而，这个定义并不是用我们现在所说的相容矩阵范数来表示的。
John Todd在20世纪50年代的一系列论文中提出了矩阵规范和条件数的概念。其他几位作者也写了关于条件数的文章。到1959年，当我和托德在加州理工学院学习数值分析时，这个概念已经有了坚实的基础。我不记得他有没有提到图灵。现在我们有规范，气孔导度,气孔导度在MATLAB。
图灵论文的最后四个部分涉及四舍五入误差。图灵的整个分析都是基于一个由ε表示的量，ε是消元过程中产生的误差。这种错误可以在手工计算中观察和控制，但在具有固定字长的现代机器上的自动计算中却不能。因为图灵不关心旋转和缩放，他的分析没有考虑ε在消除过程中可能增长的可能性。
王牌飞行员
图灵离开国家物理实验室后，他的助手j·h·威尔金森接管了这个团队。ACE的简化版本被称为Pilot ACE，取代了完整的机器。1950年5月，ACE试验机的第一个程序开始运行，同年12月，ACE试验机正式进行了演示。威尔金森设计并制造了算术器。由于图灵的设计意味着乘法是在子程序中完成的，威尔金森能够在他意识到这是可取的时候立即引入浮点算术。
Pilot ACE的主存储器使用水银延迟线。起初，内存只有128个32位字。后来扩展到354个单词。1954年增加了一个4096字的鼓。
这台机器最初是用于实验的，但它非常有用，所以一直运行了好几年。英国广播公司(BBC)公布的一个应用程序涉及模拟彗星喷气式客机的金属疲劳。英国电气公司生产了一种名为DEUCE的商用版本的飞行员ACE。在1955年到1964年间，总共制造了33台ACE试验台。
威尔金森和MATLAB的开端
吉姆·威尔金森继续领导ACE试点项目，并继续进行数值分析工作。他后来成为了矩阵计算领域的世界领先权威。他对矩阵特征值算法的研究作为一系列论文发表，与不同的合著者，在Numerische Mathematik．作品最终被收了起来手册自动计算，卷二，线性代数， 1971年，与合著者克里斯蒂安·赖因施合著。
威尔金森的Algol程序手册由阿贡国家实验室的一个小组翻译成Fortran语言。这个版本成为EISPACK(特征系统包)。我参与了EISPACK项目。我编写了MATLAB的第一个版本，这样我的学生就可以在不编写Fortran的情况下访问包。
我从没见过图灵。他去世时我才15岁。我想知道他会怎么看待MATLAB。
介绍MATLAB Enigma仿真器
作者:Corey Lagunowich和Seth Popinchalk, MathWorks
尽管恩尼格玛机是一个纯粹的机电设备，但破解它的代码的愿望引发了软件工程领域最早的一些创新。如果用软件代替硬件，Enigma会是什么样子?
为了找到答案，我们开发了一个MATLAB应用程序来模拟Enigma机器(图1)。巧合的是，9台Enigma机器——世界上最大的收藏之一——在马萨诸塞州纳蒂克的第二次世界大战博物馆展出。这里距离MathWorks总部只有两英里。在我们开发应用的时候博物馆给了我们其中一个。
图1所示。Enigma M3模拟器MATLAB应用程序。
图2展示了M3英格玛机的关键部件。按下一个按键，电流就会流过一个插板、三个转子和一个反射器，点亮按键上方的一个字母灯。每个单独的插头、转子和反射器只执行简单的替换密码，但当它们一起使用时，就有超过1.5万亿种可能的组合，而且至少有一个转子每按一次键就会旋转一个位置，产生另一个组合，解密它们的信息是一个巨大的挑战。
图2。英格玛机器内部。反射器和旋翼排列字母表中的字母，对信息进行编码或解码。
所有的Enigma加密组件在MATLAB中建模为排列矩阵。例如，右边的转子，它总是随着每一次按键而旋转，由
I =眼睛(26);Right = 'BDFHJLCPRTXVZNYEIWGAKMUSQO';[~，p] = sort(右);R = I(p，:);
附加的排列矩阵，l，C，F,P，对于左转子和中心转子，反射器和插板，都是用类似的代码创建的，用其他字符串初始化。
为了模拟转子前进的影响，利用MATLAB对排列矩阵进行了修正circshift函数。
R = circshift(R，[-1，-1]);
一系列if-then语句决定在每次按键时哪个转子前进。
单个字符cin在键盘上键入的字符被转换为逻辑列向量鑫与
Xin =逻辑(零(26,1));k = cin-'A'+1;Xin (k) = 1;
现在是整个加密过程，转换输入鑫到输出xout，使用矩阵左除法来模拟电流通过转子在出站方向的路径，并使用矩阵乘法来模拟入站路径。
M = l * c * r * p;xout = M\F*M*xin;
反射器矩阵F实际上是一个对称的排列矩阵，所以这个矩阵最终定义了这个变换，M \ F * M，也是对称的。这就是为什么解码Enigma信息的过程使用与编码相同的初始设置。
要完成该过程，使用检索输出字符
k = find(xout)+'A'-1;Cout = char(k);
MATLAB Enigma M3模拟器可用于下载从MATLAB中心的文件交换。
供进一步阅读和观看
安德鲁·霍奇斯艾伦·图灵:谜机伦敦兰登书屋和普林斯顿大学出版社，www.turing.org.uk的书．
克利夫·莫勒，吉姆·威尔金森，克利夫角博客，mathworks.com/cleve-wilkinson．
“飞行员王牌”。v = Sf28IJmm-P4 youtube.com/watch ?．这段罕见的视频讲述了威尔金森和迈克·伍格尔在1982年回忆飞行员ACE计算机的故事。我把它推荐给任何对计算史感兴趣的人。
1©2015 The MathWorks, Inc.根据GNU自由文档许可证1.2版或由自由软件基金会发布的任何更高版本的条款，授予复制、分发和/或修改本文档的权限;没有不变章节，没有封面文本，也没有封底文本。许可证的副本包含在题为“GNU自由文档许可证”的章节中。
文章刊登于MathWorks新闻与笔记．
