Large Language Models and the Extended Church-Turing Thesis

• URL: http://arxiv.org/abs/2409.06978v1
• Date: Wed, 11 Sep 2024 03:09:55 GMT
• Title: Large Language Models and the Extended Church-Turing Thesis
• Authors: Jiří Wiedermann, Jan van Leeuwen,
• Abstract summary: We investigate the computational power of large language models (LLMs) by the classical means of computability and computational complexity theory. We show that any fixed (non-adaptive) LLM is computationally equivalent to a, possibly very large, deterministic finite-state transducer. We discuss the merits of our findings in the broader context of several related disciplines and philosophies.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• DeeR-VLA: Dynamic Inference of Multimodal Large Language Models for Efficient Robot Execution [114.61347672265076]
  Development of MLLMs for real-world robots is challenging due to the typically limited computation and memory capacities available on robotic platforms. We propose a Dynamic Early-Exit Framework for Robotic Vision-Language-Action Model (DeeR) that automatically adjusts the size of the activated MLLM. DeeR demonstrates significant reductions in computational costs of LLM by 5.2-6.5x and GPU memory of LLM by 2-6x without compromising performance.
  arXiv  Detail & Related papers  (2024-11-04T18:26:08Z)
• SplitLLM: Collaborative Inference of LLMs for Model Placement and Throughput Optimization [8.121663525764294]
  Large language models (LLMs) play a crucial role in our daily lives due to their ability to understand and generate human-like text. In this report, we design a collaborative inference architecture between a server and its clients to alleviate the throughput limit. We show in the experiments that we are able to efficiently distribute the workload allowing for roughly 1/3 reduction in the server workload.
  arXiv  Detail & Related papers  (2024-10-14T17:38:41Z)
• Interpreting and Improving Large Language Models in Arithmetic Calculation [72.19753146621429]
  Large language models (LLMs) have demonstrated remarkable potential across numerous applications. In this work, we delve into uncovering a specific mechanism by which LLMs execute calculations. We investigate the potential benefits of selectively fine-tuning these essential heads/MLPs to boost the LLMs' computational performance.
  arXiv  Detail & Related papers  (2024-09-03T07:01:46Z)
• Does Reasoning Emerge? Examining the Probabilities of Causation in Large Language Models [6.922021128239465]
  Recent advances in AI have been driven by the capabilities of large language models (LLMs) This paper introduces a framework that is both theoretical and practical, aimed at assessing how effectively LLMs are able to replicate real-world reasoning mechanisms.
  arXiv  Detail & Related papers  (2024-08-15T15:19:11Z)
• On the Representational Capacity of Neural Language Models with Chain-of-Thought Reasoning [87.73401758641089]
  Chain-of-thought (CoT) reasoning has improved the performance of modern language models (LMs) We show that LMs can represent the same family of distributions over strings as probabilistic Turing machines.
  arXiv  Detail & Related papers  (2024-06-20T10:59:02Z)
• Evaluating LLMs' Mathematical Reasoning in Financial Document Question Answering [53.56653281752486]
  This study explores Large Language Models' mathematical reasoning on four financial question-answering datasets. We focus on sensitivity to table complexity and performance variations with an increasing number of arithmetic reasoning steps. We introduce a novel prompting technique tailored to semi-structured documents, matching or outperforming other baselines in performance.
  arXiv  Detail & Related papers  (2024-02-17T05:10:18Z)
• Rethinking Interpretability in the Era of Large Language Models [76.1947554386879]
  Large language models (LLMs) have demonstrated remarkable capabilities across a wide array of tasks. The capability to explain in natural language allows LLMs to expand the scale and complexity of patterns that can be given to a human. These new capabilities raise new challenges, such as hallucinated explanations and immense computational costs.
  arXiv  Detail & Related papers  (2024-01-30T17:38:54Z)
• On the Representational Capacity of Recurrent Neural Language Models [56.19166912044362]
  We show that a rationally weighted RLM with computation time can simulate any deterministic probabilistic Turing machine (PTM) with rationally weighted transitions. We also provide a lower bound by showing that under the restriction to real-time computation, such models can simulate deterministic real-time rational PTMs.
  arXiv  Detail & Related papers  (2023-10-19T17:39:47Z)
• Fast Quantum Algorithm for Attention Computation [18.44025861624981]
  Large language models (LLMs) have demonstrated exceptional performance across a wide range of tasks. The attention scheme plays a crucial role in the architecture of large language models (LLMs) It is well-known that quantum machine computation has certain computational advantages compared to the classical machine.
  arXiv  Detail & Related papers  (2023-07-16T14:00:42Z)
• Response Length Perception and Sequence Scheduling: An LLM-Empowered LLM Inference Pipeline [22.08897444328099]
  Large language models (LLMs) have revolutionized the field of AI, demonstrating unprecedented capacity across various tasks. In this paper, we propose an efficient LLM inference pipeline that harnesses the power of LLMs.
  arXiv  Detail & Related papers  (2023-05-22T15:36:06Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.