按年被提到
20242024 · 2 次2026
大模型与语言模型›模型表达力与计算理论·arXiv:2411.01992 · cs.LG

Ask, and it shall be given: On the Turing completeness of prompting

Ruizhong Qiu, Zhe Xu, Wenxuan Bao, Hanghang Tong · 2024
开始阅读 ↗PDFalphaXiv 讨论
被提及 · 3 人首次 2024-11-06 · 最近 2025-11-04
3不同的人
2活跃月份
3讨论串
5被引(OpenAlex)
arXiv 摘要(候选层不写导读)

Since the success of GPT, large language models (LLMs) have been revolutionizing machine learning and have initiated the so-called LLM prompting paradigm. In the era of LLMs, people train a single general-purpose LLM and provide the LLM with different prompts to perform different tasks. However, such empirical success largely lacks theoretical understanding. Here, we present the first theoretical study on the LLM prompting paradigm to the best of our knowledge. In this work, we show that prompting is in fact Turing-complete: there exists a finite-size Transformer such that for any computable function, there exists a corresponding prompt following which the Transformer computes the function. Furthermore, we show that even though we use only a single finite-size Transformer, it can still achieve nearly the same complexity bounds as that of the class of all unbounded-size Transformers. Overall, our result reveals that prompting can enable a single finite-size Transformer to be efficiently universal, which establishes a theoretical underpinning for prompt engineering in practice.

候选层:至少 2 个不同的人、在 2 个不同月份提到过,还没到主书架的 3 人 3 个月。没有做立场标注,所以只写“被提及”。

HN 书评

推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及
评论ivraatiems · 2025-11

“That doesn't seem right to me. If I understand it right, your logic is: 1. Humans intellect is Turing computable. 2. LLMs are based on Turing-complete technology. 3. Therefore, LLMs can eventually equal human intellect. But if that is the right chain of assumptions, there's lots of issues with it. First, whether LLMs are Turing complete is a topic of de…”

The Case That A.I. Is Thinking原评论 ↗
被提交为 story · 2 次