目前最火热的大模型公司莫过于
OpenAI
。
OpenAI
首席科学家
Ilya Sutskever
在接受采访时不断暗示，next token prediction 是 GPT 系列大模型成功的关键，但直到 2023 年 8 月，他在伯克利理论计算机科学研究所演讲时才明确透露，GPT 的数学依据是所罗门诺夫归纳法（Solomonoff Induction）。
那么，所罗门诺夫归纳法是什么？其对大模型研究有何重要意义？今年正值所罗门诺夫归纳法诞生 60 周年，人工智能学者尼克，撰写万字长文，解释所罗门诺夫归纳法为何是大语言模型的理论基础，如何解释 GPT 的核心机制 next token prediction。
与此同时，尼克在文章中旁征博引，也介绍了苏联数学家柯尔莫哥洛夫和列文以及美国理论计算机科学家蔡廷等的独立贡献。最后，本文还讨论了这一理论近来的进展、在人工智能领域中可能的应用以及哲学涵义。
科学发展有时理论先行，实践随后；有时则是工程或实验先出成果，理论解释慢慢到来；但也有时是理论和实践纠缠在一起。
自然语言处理（NLP）的历史较为曲折，更像最后一种情况。大语言模型，作为 NLP 的最新进展，除了理论和实践外，还夹杂着商业，这使得澄清历史更加困难。随着大语言模型在工程上的不断进展，有理论意识的工程师们企图寻找其数学基础，以求为大模型的成功提供解释。但很多脱离第一性原理的观察和拟合实在算不上理论基础，反而徒劳为工程师们增加了更多的困惑。
事实上，特立独行的数学家所罗门诺夫（Ray Solomonoff，1926年-2009年）在 1960 年代初期的天才贡献已经为大模型奠定了数学基础。他的原创理论开始被重新发现，至今对工程实践仍具指导作用，并可能为未来指明方向。所罗门诺夫可算得大语言模型的先知。
1956 年麦卡锡（John McCarthy，1927 年-2011 年）和明斯基（Marvin Lee Minsky，1927 年—2016 年）牵头，在贝尔实验室的香农（Claude Elwood Shannon，1916 年—2001 年）和 IBM 的罗切斯特（Nathaniel Rochester, 1919 年—2001 年）支持下在麦卡锡当时任教的达特茅斯学院召开了人工智能夏季研讨会。这次会议标志人工智能作为一门独立学科的建立。会议聚集了一群来自多个不同学科、年轻且野心勃勃的学者。
最认真对待这个会议的就是所罗门诺夫。和其他来来往往的参会者不同，所罗门诺夫在达特茅斯待了整整一个暑假。他 1951 年在芝加哥大学跟随费米主修物理，只得了硕士就离开象牙塔，转往美国东北部（波士顿和纽约一带）开始了他半工半学、快乐但并不富贵的一生。在芝加哥求学期间，对他影响最大的是哲学家卡尔纳普（Rudolf Carnap，1891 年-1970 年）。卡尔纳普那时的主要兴趣是概率论和归纳推理，思想和成果都体现在他 1950 年出版的《概率的逻辑基础》（Logical Foundation of Probability）一书中（见 Carnap-1950），所罗门诺夫深研此书，归纳推理遂成为他毕生的研究方向。
所罗门诺夫（1926 年 7 月 25 日-2009 年 12 月 7 日）
有意思的是，神经网络的奠基者之一皮茨（Walter Pitts，1923 年-1969 年）也受惠于卡尔纳普。而另一位人工智能的开拓者司马贺（Herbert Simon，1916 年-2001 年）在他的回忆录里讲到自己在芝加哥时听过卡尔纳普的数理逻辑课，从而开始萌生对机器定理证明以及更广泛的智能问题的兴趣。这么说来，人工智能的两大流派——逻辑和神经网络——都受教于卡尔纳普（见尼克-2021）。
所罗门诺夫 1952 年左右结识了明斯基和麦卡锡，那时两人还都是普林斯顿大学数学系的博士生。虽然丘奇（Alonzo Church）在那里坐镇逻辑学，但明斯基和麦卡锡的博士论文却都不是关于逻辑的，不过他们毫无疑问都受到了逻辑的强烈熏陶，刚出道时都聚焦逻辑，尤其是递归函数的研究。当时逻辑在美国大学的数学系是新兴学科。递归函数作为数理逻辑的子学科，逐渐演变成现在的可计算性理论，并进一步衍生出计算复杂性。明斯基 1967 年还写过一本早期颇有影响的计算理论教科书 Computation：Finite and Infinite Machines（见 Minsky-1967），在麻省理工还带过几个专做计算理论的学生，其中曼纽尔· 布鲁姆（Manuel Blum）后来因为计算复杂性和密码学的贡献得了图灵奖。明斯基所谓“AI 孵化出计算理论”的说法不无道理。
1953 年夏天，已经博士毕业的麦卡锡和即将博士毕业的明斯基都在贝尔实验室工作，他们都围绕着因为信息论而声名雀起的香农。香农当时的兴趣则是图灵机以及是否可用图灵机作为智能活动的理论基础。那时名气更大的是更长一辈的维纳，他刚出版了一本颇有影响的新书，书名 Cybernetics（控制论）借用自希腊语（舵手），维纳企图以这个新词一统天下，他在书中不时暗示或明示香农的信息论也是受到他的启发。很明显，年轻的香农和更年轻的麦卡锡都不买维纳的账，也不喜欢“控制论”这个词。麦卡锡向香农建议编一本文集，请当时相关的一线研究人员都贡献文章，这本文集直到 1956 年才以《自动机研究》（Automata Studies）为名出版，这个普普通通的书名最后是香农定的，他不喜欢用创造新名词的手段来吸引眼球，但麦卡锡认为这个不显山不露水的书名并没有反映出他们的初衷，这导致他后来坚持用另一个新词“人工智能”来命名这个全新的领域。在这本文集中，麦卡锡本人也贡献了一篇只有 5 页的短文，题为“图灵机定义的逆函数”（The Inversion of Functions Defined by Turing Machines，见 McCarthy-1956）。
麦卡锡在文中讨论了这样一个问题：假设知道一个图灵机的输出，如何猜到其输入。更严谨地：给定一个递归函数（即一个图灵机）fm 及其输出 r（fm(n)=r），如何找到一个“有效”的逆函数 g(m, r) 使得 fm(g(m, r)) = r，这里 m 是图灵机的序号。这个问题就是通过观察一个黑盒子（图灵机）的输出，力图猜出黑盒子的内部构造。最土的办法就是枚举所有能够产生输出的图灵机，但很明显这个办法不一定停机。事实上，在今天大模型的语境里，g(m, r)就是一个大语言模型。麦卡锡意识到这个问题对应于在所有可能的文章中以某种顺序寻找证明（It corresponds to looking for a proof of a conjecture by checking in some order all possible English essays）。麦卡锡认为所有的数学问题都可以表达为用图灵机求逆，这正是所罗门诺夫想解决的归纳推理问题。
达特茅斯会议期间，麦卡锡和所罗门诺夫有了更多的机会进行长时间讨论。所罗门诺夫认为麦卡锡的问题可以转化成：“给定一个序列的初始段，求这个序列的后续”。通过已知的初始段，建模，以模型来预测后续序列。麦卡锡一开始并没有意识到这个思路的重要性，反问了一句：这不就是外插吗？当时在场的人都被麦卡锡的反问卡住了。第二天麦卡锡反应过来，他说所罗门诺夫的问题通俗地说，就是：“假设我们发现一座老房子里有一个计算机正在打印你说的序列，并且已经接近序列的末尾，马上就要打印下一个字符，你敢打赌它会打印正确的字符吗？” 麦卡锡和所罗门诺夫所谓“sequence continuation”，“next word”或者“next symbol”，用今天的话说就是 “next token”。
2006 年达特茅斯会议 50 年周纪念会。左 2 麦卡锡，左 3 明斯基，右 1 所罗门诺夫
其实，这个说法有着更早的起源。法国数学家博雷尔（Félix Édouard Justin Émile Borel，1871 年—1956 年）在 1913 年的文章“Mécanique Statistique et Irréversibilité”（统计力学与不可逆性）中考虑过这样一个问题：让一个猴子在一个打字机上随意地敲字，它能敲出一部《哈姆雷特》吗？博雷尔指出猴子随机敲出一部《哈姆雷特》的概率是 5.02×10
-29
，概率极小，但不是绝对不可能，这被称为“无限猴子定理”（infinite monkey theorem）。阿根廷诗人和作家博尔赫斯（Jorge Luis Borges ，1899年-1986年）在 1944 年出版的短篇小说集《小径分岔的花园》中收录了一篇他的哲理小说（其实更像是散文）“巴比伦图书馆”，文中设想一个完美的图书馆，它可以收藏由字母枚举产生的所有可能的书；事实上，他在 1939 年写过一篇更严肃的哲学文章“总图书馆”（Total Library），回顾了从亚里士多德开始不同阶段思想家对这个理想的各种思辨。
今天看来，大模型不就是走在这个方向吗？大模型的训练力图穷举人类已有的所有知识。如果博尔赫斯的出发点是理性主义的，那么随机猴子肯定是经验主义的，但他们都可以用麦卡锡的求逆统一为某种图灵机的枚举过程。
图灵 1948 年的文章“智能机器”的价值正在被越来越多的人注意到。图灵文中提到了几种机器学习的方法。在通用图灵机中，程序等于数据，于是，所有的程序，就像数据一样，是可以逐一被枚举出来的。这个枚举方法是自己把所有可能的程序都学出来。这就是图灵所谓“主动性”（initiative）（见尼克-2024）。图灵明确表示，所有“学习”都可以归约到这个方法。计算理论告诉我们这个枚举过程不停机，或者说不可计算。
和麦卡锡的讨论，促使所罗门诺夫进一步完善自己的想法，达特茅斯会议结束前，他写好了一篇关于归纳推理的备忘录“An Inductive Inference Machine”，这篇打字稿的日期是 1956 年 8 月 14 日。所罗门诺夫把该打字稿给参会人员传阅。1956 年底他还将一个改进的版本寄给卡内基理工学院工业管理系的司马贺（Herbert Simon）。
所罗门诺夫的工作首次公开发表是在 1960 年加州理工学院召开的“大脑系统与计算机”（Cerebral Systems and Computers）会议上。同年这篇文章作为 Zator 公司报告和美国空军AFOSR报告得到更广泛的流传。1961 年明斯基在一篇影响广泛的文章“Steps Toward Artificial Intelligence”中提到了这项工作（见 Minsky-1961）。所罗门诺夫后来对 1960 年的工作做了进一步修订，以“归纳推理的形式理论”（A Formal Theory of Inductive Inference）为题，于 1964 年正式发表在计算理论的重要刊物《信息与控制》（Information and Control）。因为文章太长，被拆成两部分，在两期分别刊出，前半部分讲理论，后半部分讲了几个实例（见 Solomonoff-1964）。
所罗门诺夫归纳法可以如下定义：给定序列（X
1
, X
2
, …, X
n
）, 预测X
n+1
。归纳推理就是力图找到一个最小的图灵机，可以为（
X
1
, X
2
,
…, X
n
）建模，从而准确地预测后续序列。序列的描述长度就是图灵机的大小，这其实就是麦卡锡最初模糊地意识到的“有效”。例如，如果一个序列是 n个1: （1, 1, 1,…）,那么我们可以写出如下程序输出该序列:
例如，如果我们给出序列（3, 5, 7），会有无穷多种预测后续的结果，其中一种是 9，因为程序有可能打印奇数，如下：
但也许猜的不对，还有一种可能性是 11，因为程序有可能是打印素数的。很明显，打印素数的程序就要比打印奇数的程序复杂很多，也就是说素数的描述长度要大于奇数的描述长度。等等。
监督学习也可以看作是自监督学习的特殊情况。
监督学习（包括分类问题），就是给定序列对（tuple）：
（
X
1
,C
1
）,（
X
2
,C
2
）,…,(
X
n
,C
n
）,以及
X
n+1
，预测 C
n+1
。
学习的过程就是找到拟合函数c=f(x)。
这类问题都可以轻松地转化为自监督学习如下：
给定序列（
X
1
,
C
1
,
X
2
,
C
2
,…,
X
n
,C
n
,
X
n+1
）, 预测
C
n+1
。
这个被麦卡锡刻画为“在下一个字符上下注”（bet on next symbol）的问题，其实就是 GPT 为代表的大语言模型的核心机制：next token prediction。能够对已知数据做出概括的图灵机就是大模型。对于同样的数据集，我们当然期望覆盖数据集的大模型的参数越少越好，换句话说，我们期望找到可以做出概括的最经济的图灵机，即最小的图灵机。在这个意义上，学习可以被当作压缩。参数量和 token 量之间的关系也可借此研究。所罗门诺夫归纳法可能不停机，于是只能用近似算法，放宽对图灵机的“最小性”和预测准确性的限制。所罗门诺夫利用贝叶斯定理推导出序列的先验概率分布。神经网络作为一个通用近似器（universal approximator），可以是实现所罗门诺夫归纳法的一个很好的候选机制。这其实就是今天大模型的进路。
所罗门诺夫想到的另一个要解决的问题，是给定一些句子，看能否学会生成这些句子的语法。此时乔姆斯基（Noam Chomsky）的“语言描述的三种模型”的文章刚刚发表，所罗门诺夫受到启发，把乔姆斯基文法推广成概率文法。他的“归纳推理机”的一种应用场景就是通过输入文本，学会文法，这被他后来称为“文法发现”（discovery of grammar）。
乔姆斯基的先天内生文法（innate grammar）其实就是所罗门诺夫的先验概率分布，只不过乔姆斯基采取了理性主义的立场，而所罗门诺夫无疑是经验主义的。事实上，如果认可丘奇-图灵论题，理性主义和经验主义的区别只是修辞的，而不是本质的。在所罗门诺夫的先验概率分布下，程序的置信度随着其长度指数递减。这就是奥卡姆剃刀，即越短的程序应该有越高的置信度。这一点也可以从经验数据中得到佐证（见Veldhuizen-2005）。在所罗门诺夫的纪念网站（raysolomonoff.com）上，醒目地放着所罗门诺夫的美丽公式：
所罗门诺夫一生没有大富大贵，大部分时间是在自己的咨询公司 Oxbridge（“牛桥”，牛津+剑桥的简称，相当于汉语俗称“清北”）拿政府（空军、海军、ARPA 和 NIH）的研究经费，公司只有他自己一个雇员。他的学术自传“算法概率论的发现”（The Discovery of Algorithmic Probability）1997 年发表在计算理论杂志《计算机与系统科学》（
Journal of Computer and System Sciences
）上（见 Solomonoff-1997），这篇文章后来历经修订，在多处以不同形式发表。最新的一版在他去世后被收录在文集
Randomness Through Computation: Some Answers, More Questions
之中（见Solomonoff-2011）。
历史：
柯尔莫哥洛夫与复杂性
万能的苏联数学家柯尔莫哥洛夫（Andrey Nikolaevich Kolmogorov，1903 年-1987 年），除了对传统数学做出广泛和深刻的贡献外，对计算机科学和信息论的诸多方面，也有直接和间接的影响。
1950 年代初期，香农的信息论和维纳的控制论，通过俄文翻译传入苏联。柯尔莫哥洛夫凭着他敏锐的直觉，意识到信息论的重要性。同时他对控制论则表示出不屑，他认为控制论并没有内在的统一性。这个认识和香农、麦卡锡等参与达特茅斯会议的人对控制论的看法一致。苏联当时的科学发展状况非常复杂。即使地位如柯尔莫哥洛夫，他对遗传学的兴趣也遭到李森科的打压，倒是李森科下台后，柯尔莫哥洛夫还替他说过好话。
柯尔莫哥洛夫对控制论的看法并没有阻挡控制论成为苏联的主流学科。这也许导致苏联在计算机科学以及多少作为计算机科学子学科的人工智能的后知后觉；这肯定也带偏了中国相关学科的发展。控制论在美国没有成为独立的学科，倒是计算机科学成为主导的学科，1960 年代末开始，美国顶流学校纷纷设立计算机系。
控制论的核心概念：反馈，不过是递归函数的一种最简单的特殊情况，不足以作为第一性原理。柯尔莫哥洛夫在为匈牙利数学家罗莎·培特所著《递归函数论》俄译本所写的序言中（莫绍揆先生 1958 年将此书依照俄文版译为中文，其中将“柯尔莫哥洛夫”译为“郭尔莫哥洛夫”，将“图灵”译为“杜令”）指出，一般递归函数和能行可计算性仍需从可构造性的角度进一步考察——他对丘奇-图灵论题也有着深刻洞见（见 Peter-1951）。
无论如何，柯尔莫哥洛夫的切入点是他喜欢的领域：概率论。1965 年，他创办了学术季刊《信息传输问题》（Problems of Information Transmission），这份刊物很快成为苏联在计算理论最重要的阵地。柯尔莫哥洛夫本人在创刊号上发表了 “信息的量化定义的三种方式”（Three Approaches to the Quantitative Definition of Information），从算法的角度研究了概率论和信息论。信息论的核心是研究信息的含量。香农的信息量定义是熵。柯尔莫哥洛夫把信息论的基础分成三种，第一是频率，第二是组合学，第三是算法。柯尔莫哥洛夫对信息论和概率论的评价令人深思：“信息论在逻辑上要先于概率论。而不是以后者为基础。”他认为组合学比频率更加坚实，但最令人信服的是算法。一段信息所包含的信息量，可以用最短的生成这段信息的程序的长度来衡量（见 Kolmogorov-1965）。这就是现在所谓“柯尔莫哥洛夫复杂性”（Kolmogorov Complexity），可定义如下：
KC(x) = min{ℓ(p) : U(p) = x}
即输出字符串x的最短程序p的长度。柯尔莫哥洛夫这篇经典文章只有7页，而后面他写的几篇相关文章甚至更短。这与所罗门诺夫细致但冗长的文章形成鲜明对比。苏联数学家的简洁是他们的一大特色，据说那是因为苏联时期纸张紧缺，但另一种说法是苏联数学家（尤其是大家）就是不太讲究细节，以至于结果的完整证明，需要他们的学生们补齐，有时甚至需要一代人。柯尔莫哥洛夫的KAM（Kolmogorov–Arnold–Moser）理论就是后来由他的学生阿诺德（Vladimir Arnold）和德裔美国数学家 Jürgen Moser 等人完善的，而他关于希尔伯特第十三问题的研究，也是由阿诺德画上句号，这个重要的工作值得另写一篇长文。
可以证明柯尔莫哥洛夫复杂性与程序的表示无关。不同的程序表示，例如：C，Java，Python，或图灵机代码，导致的最短描述之间只差一个常量。这个不变性定理有时也被称为“柯尔莫哥洛夫论题”（Kolmogorov Thesis）。越来越多的证据表明柯尔莫哥洛夫复杂性(如果能算出来的话)要比香农熵更加靠谱，例如一个图的结构熵会因为图的表示不同而变化，而这个图的柯尔莫哥洛夫复杂度应该是不变的。
柯尔莫哥洛夫后来注意到所罗门诺夫的工作，他在 1968 年分别用俄文和英文发表的文章中引用了所罗门诺夫的工作，使得后者在苏联的名声比在西方更加响亮。“柯尔莫哥洛夫复杂性”也被称为“所罗门诺夫复杂性”，或者“所罗门诺夫-柯尔莫哥洛夫-蔡廷复杂性”，偶尔也被称为“描述复杂性”，但计算复杂性理论里有好几个东西都被称为“描述复杂性”，为避免歧义，本文使用最常用的“柯尔莫哥洛夫复杂性”的说法。因为柯尔莫哥洛夫的影响，这门学科也被称为“算法概率论”，或“算法信息论”。
几位苏联学者，其中包括柯尔莫哥洛夫的学生，在伦敦大学皇家哈洛威学院（Royal Holloway）建立了机器学习研究中心（原名Computer Learning Research Centre，后改名 Centre for Machine Learning）。在他们倡导下设立了柯尔莫哥洛夫奖章（Kolmogorov Medal，注意：有别于俄国科学院颁发的柯尔莫哥洛夫奖，Kolmogorov Prize）。所罗门诺夫是第一届柯尔莫哥洛夫奖章获奖人，最近一次（2018 年）的获奖人是以发明支持向量机（Support Vector Machine）著称的苏联犹太裔统计学家弗拉基米尔·瓦普尼克（Vladimir Vapnik）。所罗门诺夫也在伦敦大学皇家哈洛威学院兼职教授。
历史：蔡廷与随机性
阿根廷出生的犹太裔美国理论计算机科学家蔡廷（Greg Chaitin, 1947 年-），有着与众不同的成长经历。他高中就读著名的纽约布朗克斯科学高中（Bronx High School of Science），这个学校贡献过 9 位诺贝尔奖，2 位图灵奖。他的第一篇文章在他 18 岁时发表于IEEE Transactions on Electronic Computers，是关于自动机时钟同步的，这是他高中时的作品，署名单位是哥伦比亚大学工程与应用学院，因为他高中时参加了哥大的荣誉生项目。他高中毕业后，入学纽约城市学院（CCNY）。他在第一学期同时在看三本书：冯诺依曼和摩根士敦合著的《博弈论》，香农和韦弗的《通讯的数学理论》，以及马丁·戴维斯编辑的《不可判定》文集（其中收录了图灵 1936 年开天辟地的文章）。他本科没有毕业就跟随父母回到阿根廷。
蔡廷在很小的时候就访问过 IBM，于是研究逻辑和编程成为他的爱好。他的编程能力使得他在布宜诺斯艾利斯的 IBM 分公司轻易地找到一份程序员的工作。在此期间他研究哥德尔不完全性定理。他第一篇关于最小程序长度的文章发表在《美国计算机学会会刊》（JACM），那时他才 19 岁，独立地把所罗门诺夫归纳法和柯尔莫哥洛夫信息量的思想又以新的方式重新发明了一遍。审稿人已经知道柯尔莫哥洛夫的工作并告知蔡廷，他不懂俄文，但还是在论文发表时以脚注形式承认了柯氏的工作。
蔡廷的出发点是贝里悖论（Berry Paradox）。贝里悖论用英文说就是"The smallest positive integer not definable in under sixty letters"，用中文说是“不可能用少于十九个汉字命名的最小正整数”。这是一种命名悖论。因为贝里悖论和所用的语言载体有关，蔡廷于是决定用函数式编程语言 LISP 以避免混淆。所谓命名一个整数就是给出一个可以输出这个整数的程序。蔡廷的命名就是柯尔莫哥洛夫的描述。绝大多数整数最短的命名方式就是直接打印它们自身，而没有更短的程序表示它们，这些整数被蔡廷称为“无趣的”（uninteresting）、不可理解的（incomprehensible）、不可归约的（irreducible）以及随机的。蔡廷事实上由此证明了柯尔莫哥洛夫复杂度是不可计算的。他当时称之为“不完全性”。
1974 年蔡廷回到美国，在纽约州的 IBM TJ Watson 研究中心工作，先是做访问学者，后来成为永久研究员。有意思的是他刚回到美国后，就准备乘火车前往普林斯顿拜访他的上帝哥德尔。于是 1974 年 4 月的某一天，他鼓足勇气给哥德尔打了个电话，告诉哥德尔他利用贝里悖论也得出了不完全性定理的一个版本。
哥德尔说：“用什么悖论无所谓”（“It doesn’t make any difference which paradox you use!” ）。
蔡廷回答：“是的，但是我的证明指出了不完全性的信息论视角，我很想当面告诉你。”
哥德尔说：“好吧，先把论文寄给我，然后再给我打电话看能不能约上我的时间。”
于是蔡廷把自己刚刚发表在 IEEE Transactions on Information Theory 的文章寄给哥德尔，并再次致电哥德尔，哥德尔看过文章后同意和他见面并约定了时间。但就在他约定的那天下了雪。当他正准备离开办公室去火车站时，电话响了，是哥德尔的秘书，说“哥德尔教授身体不好，很怕雪，今天不到高等研究院上班，见面取消了。”没有见到哥德尔成了蔡廷一生的遗憾。1991 年他被哥德尔的母校维也纳大学邀请演讲，当地报纸把他的照片印在头版，标题是 “比哥德尔还哥德尔！”（ Out-Gödeling Gödel”!）（见Chaitin-2023, 及Wuppuluri & Doria-2020）
蔡廷晚年兴趣转向生物学，出版过有趣的科普著作 Proving Darwin（《证明达尔文》，见 Chaitin-2012）。一个人成名早的特点是他喜欢用熟悉的锤子去敲他碰见的所有钉子，所谓一招鲜吃遍天。他不满生物学缺乏理论基础，用算法信息论解释进化论，并把这个方法称为“元生物学”（metabiology）。一点也不惊奇，他的元生物学的核心思想可以从遗传算法和遗传编程中找到线索。
历史：列文与通用搜索过程
苏联数学家列文（Leonid Levin, 1948 年-）1972 年独立提出了 NP 完全性并证明了几个等价问题（见 Levin-1973）。这篇现在看来极为重要的文章只有两页纸，发表在柯尔莫哥洛夫创办的著名刊物 Problems of Information Transmissions 1973 年第 3 期上。列文是柯尔莫哥洛夫的学生，但由于政治问题，他没有被授予博士学位。1978 年他移民美国，麻省理工学院很快给他补了一个博士，此后他的结果渐为人知。他后来在波士顿大学教书直到退休。2000 年后的计算理论教科书都把原来的库克定理改为库克-列文（Cook-Levin）定理。2012 年他被授予高德纳奖（Knuth Prize）——与面向特定贡献的图灵奖和哥德尔奖不同，高德纳奖更加考虑对整个学科的影响，有点终身成就奖的意思。这算是对他缺失图灵奖的补偿吧。
和他的老师一样，列文的文章也都很短，他 1986 年开创算法平均复杂性分析的文章也只有两页（见 Levin-1986）。有意思的是，列文倾向于认为 P=NP，他肯定是少数派。
在 Levin-1973 中，列文给出了两个定理，定理 1 关于 NP 完全性，而定理 2 当时被忽略了。定理 1 没有详细证明，而定理 2 甚至连说明都没有。文章在列出定理 2 之后就结束了。定理 2 其实和定理 1 的关系不大，或者至少关系并不明显。列文给出了一个通用搜索过程（universal search），这个过程能够求解一个函数的逆，这恰是麦卡锡 1950 年代提出的问题，而所罗门诺夫已经在这个问题上耗了 20 年。
当所罗门诺夫得知列文在苏联的遭遇后，联系了美国的几所学校和多名学者，恳请他们帮助列文。所罗门诺夫把他和列文的学术讨论写成报告（见 Solomonoff-1984），为 Levin-1973 补齐了定理 2 的证明。所罗门诺夫称列文的通用搜索过程为 L-search。
列文的 L-search 在柯尔莫哥洛夫复杂性的基础上加了一个时间的限制，可定义如下:
Kt(x) = min{ℓ(p) + log(time(p)): U(p) = x}
这样列文的复杂性就是可计算的了，也就是说，如果逆函数存在，总可以通过列文的通用搜索过程找到。这和所罗门诺夫更早获得的收敛性定理契合。
列文 1973 年文章第二页。参考文献前是一句鸣谢，鸣谢前即是定理 2 的陈述。
本内特与逻辑深度
物理学家本内特（Charles Bennett, 1943-）因量子计算出名，他是量子密码分发协议 BB84 的第一个 B。他对算法信息论也有杰出贡献，他在 1988 年引入了逻辑深度（logical depth）的概念（见Bennett-1988），定义如下：
LD(x) = min{T(p): ℓ(p) =p*+s ∧U(p) = x}
即近乎最短的程序输出 x 所需的时间。这里 p* 就是柯尔莫哥洛夫复杂性，ℓ(p)就是近乎最短的程序的长度。可以看出，逻辑深度进一步放宽了柯尔莫哥洛夫复杂性对程序最短长度的要求。
如果把归纳看作是压缩的话，逻辑深度考虑的是解压的时间。逻辑深度让我们考虑时间和空间的关系。直觉上，我们会认为时间比空间更“贵”，但目前在计算理论中，我们尚不知多项式时间的类 P 是不是等于多项式空间的类 PSPACE，当然 NP 是 PSPACE 的子集但不知是不是真子集。如果 P≠PSPACE，那么必然存在 PSPACE 中可计算的字符串，其逻辑深度大于多项式。压缩首先考虑的是空间成本，但解压有时间成本。
用大语言模型的话来说，压缩时间是训练时间；柯尔莫哥洛夫复杂度是大模型的参数量；逻辑深度对应于大模型的最短“推理”（inference）时间。顺便说，大模型术语中“推理”（inference）更合适的译法应该是“推断”，推断是统计意义上的，有别于逻辑意义的“推理”（reasoning）。汉语里“推理”常常指后者。况且，大模型中也有逻辑意义的“推理”，例如 CoT（Chain of Thought），而机器定理证明的教科书里时常也不严格区分 inference 和 reasoning。人工智能的逻辑派和统计派，如果都是讲汉语的，估计就打不起来了。
进展和应用
理论计算机科学家李明等的一系列工作，为所罗门诺夫-柯尔莫哥洛夫-蔡廷复杂性的研究做出重要贡献。李明和维特涅（Paul Vitanyi）合著的《柯尔莫哥洛夫复杂性及其应用》（Li-Vitanyi-2019）是这个领域的权威（definitive）参考书和教科书，也被誉为该领域的《圣经》，目前已经出到第 4 版。早期版本有中译本《描述复杂性》（科学出版社，1998），但“描述复杂性”这个译法容易和计算复杂性里各种被称为 Descriptive Complexity 的东西混淆，本文中我们还是使用全名所罗门诺夫-柯尔莫哥洛夫-蔡廷复杂性或柯尔莫哥洛夫复杂性。
