Large Language Models and the Extended Church-Turing Thesis

📄 arXiv: 2409.06978v1 📥 PDF

作者: Jiří Wiedermann, Jan van Leeuwen

分类: cs.FL, cs.AI

发布日期: 2024-09-11

备注: In Proceedings NCMA 2024, arXiv:2409.06120

期刊: EPTCS 407, 2024, pp. 198-213

DOI: 10.4204/EPTCS.407.14

💡 一句话要点

分析大型语言模型计算能力，揭示其与扩展丘奇-图灵论题的关联

🎯 匹配领域: 支柱九：具身大模型 (Embodied Foundation Models)

关键词: 大型语言模型 扩展丘奇-图灵论题 计算能力 自动机理论 图灵机 超图灵计算 知识生成

📋 核心要点

  1. 现有理论框架难以充分解释大型语言模型（LLM）的计算能力及其与通用计算模型的联系。
  2. 论文通过将LLM与确定性有限状态转换器和交互式图灵机进行等价，分析其计算能力。
  3. 研究表明，固定LLM等价于有限状态转换器，而进化LLM谱系则等价于带有建议的交互式图灵机。

📝 摘要（中文）

扩展丘奇-图灵论题(ECTT)认为，所有有效的信息处理，包括无界和非均匀交互计算，都可以用带有建议的交互式图灵机来描述。本文探讨了这一论断是否适用于当代大型语言模型(LLM)的能力。从更广泛的角度来看，这个问题需要通过可计算性和计算复杂性理论，特别是自动机理论，来研究LLM的计算能力。为此，我们建立了一系列基本结果。首先，我们认为任何固定的(非自适应的)LLM在计算上等价于一个可能非常大的确定性有限状态转换器。这描述了LLM的基本水平。我们将其扩展到关于LLM模拟空间有界图灵机的关键结果。其次，我们证明了进化LLM的谱系在计算上等价于带有建议的交互式图灵机。后一个发现证实了ECTT对于LLM谱系的有效性。从可计算性的角度来看，这也表明LLM谱系具有超图灵计算能力。因此，在我们的计算模型中，知识生成通常是由LLM谱系实现的非算法过程。最后，我们讨论了我们的发现在几个相关学科和哲学的更广泛背景下的优点。

🔬 方法详解

问题定义：论文旨在研究大型语言模型（LLM）的计算能力，并将其与扩展丘奇-图灵论题（ECTT）联系起来。现有方法难以精确刻画LLM的计算边界，以及LLM在知识生成方面的非算法特性。

核心思路：论文的核心思路是将LLM的计算过程抽象为不同的计算模型，例如确定性有限状态转换器和交互式图灵机。通过建立LLM与这些计算模型之间的等价关系，从而分析LLM的计算能力和局限性。对于进化LLM，则将其视为一个谱系，并分析其与带有建议的交互式图灵机的等价性。

技术框架：论文的技术框架主要包括以下几个部分：1) 将固定的（非自适应的）LLM建模为确定性有限状态转换器；2) 证明LLM可以模拟空间有界的图灵机；3) 将进化LLM的谱系建模为带有建议的交互式图灵机。通过这些建模，论文将LLM的计算能力与已知的计算模型联系起来，从而进行分析。

关键创新：论文的关键创新在于将LLM的计算能力与经典的计算理论联系起来，特别是与扩展丘奇-图灵论题联系起来。通过将LLM建模为确定性有限状态转换器和交互式图灵机，论文提供了一种新的视角来理解LLM的计算能力。此外，论文还提出了进化LLM谱系的概念，并证明其具有超图灵计算能力。

关键设计：论文没有涉及具体的参数设置、损失函数或网络结构等技术细节，而是侧重于从计算理论的角度分析LLM的计算能力。关键在于如何将LLM的输入输出过程抽象为相应的计算模型，并证明它们之间的等价关系。例如，将固定LLM视为一个状态转换系统，其状态由LLM的内部参数决定，输入和输出则对应于状态之间的转换。

🖼️ 关键图片

img_0

📊 实验亮点

论文证明了固定的（非自适应的）LLM在计算上等价于一个确定性有限状态转换器，揭示了其计算能力的上限。更重要的是，论文证明了进化LLM的谱系在计算上等价于带有建议的交互式图灵机，表明LLM谱系可能具有超图灵计算能力，为理解LLM的潜力提供了新的视角。

🎯 应用场景

该研究成果可应用于评估和比较不同LLM的计算能力，指导LLM的设计和优化。此外，该研究对于理解人工智能的本质和局限性，以及探讨知识生成的非算法特性具有重要的理论意义。未来，可以进一步研究LLM在解决特定计算问题上的能力，以及如何利用LLM进行更复杂的计算任务。

📄 摘要（原文）

The Extended Church-Turing Thesis (ECTT) posits that all effective information processing, including unbounded and non-uniform interactive computations, can be described in terms of interactive Turing machines with advice. Does this assertion also apply to the abilities of contemporary large language models (LLMs)? From a broader perspective, this question calls for an investigation of the computational power of LLMs by the classical means of computability and computational complexity theory, especially the theory of automata. Along these lines, we establish a number of fundamental results. Firstly, we argue that any fixed (non-adaptive) LLM is computationally equivalent to a, possibly very large, deterministic finite-state transducer. This characterizes the base level of LLMs. We extend this to a key result concerning the simulation of space-bounded Turing machines by LLMs. Secondly, we show that lineages of evolving LLMs are computationally equivalent to interactive Turing machines with advice. The latter finding confirms the validity of the ECTT for lineages of LLMs. From a computability viewpoint, it also suggests that lineages of LLMs possess super-Turing computational power. Consequently, in our computational model knowledge generation is in general a non-algorithmic process realized by lineages of LLMs. Finally, we discuss the merits of our findings in the broader context of several related disciplines and philosophies.