TE
科技回声
首页24小时热榜最新最佳问答展示工作
GitHubTwitter
首页

科技回声

基于 Next.js 构建的科技新闻平台,提供全球科技新闻和讨论内容。

GitHubTwitter

首页

首页最新最佳问答展示工作

资源链接

HackerNews API原版 HackerNewsNext.js

© 2025 科技回声. 版权所有。

Turing Machines and the Busy Beaver Game

11 点作者 mishkinf大约 10 年前

1 comment

belovedeagle大约 10 年前
I believe there is some confusion in the article about whether non-halting Turing machines are properly called &quot;Turing machines&quot;; that is, the author seems to use the phrase &quot;Turing machine&quot; to refer only to halting machines.<p>&gt; Not each of these ways end up being Turing machines since a Turing machine, by definition, must have a finite number of operations that end with a halting state.<p>By contrast, a more accepted definition of a Turing machine is given:<p>&gt; An n-card Turing machine is a machine that has a control unit (as seen above) that transitions between n discrete states until it reaches the halting-state.<p>Note that this definition states that the Turing machine no longer transitions once it has reached the &quot;halting state&quot; [1] but it should not be read to imply that a machine must actually reach the halting state after finitely many operations.<p>The article could be corrected by replacing &quot;Turing machine&quot; in the problematic statement with &quot;Turing machine which halts&quot;; or by making explicit the notion of a candidate BBTM as a TM which must halt.<p>As for the current reading of the statement, it is incorrect given that there are in fact [4(n+1)]^2n possible binary n-state TMs given the formalization used in the article, although there are many symmetries which could reduce that number.<p>[1] The distinction between &quot;a&quot; halting state and &quot;the&quot; halting state is immaterial, since you can view states which specify &quot;HALT&quot; either as many distinct halting states or all leading to a singular state, halting.