网站首页  情感咨询  情感美文  情感百科  情感生活  学习充电  旧版美文

请输入您要查询的百科知识:

 

标题 停机问题
类别 哲学
释义 停机问题     halting problem

递归论研究的重要判定问题之一,即图灵机的停机问题。其内容为:对任意给出的自然数对m,n,判定图灵机Tm在输入为n时是否停机?抽象地讲,一图灵机就是一指令集,即一个相容的程序,一个相容的四元组集合。通过对四元组、四元组有限集的编码,可以对图灵机加以编码。根据枚举定理:所有图灵机的集合是递归可枚举的。因此一切图灵机可以排列成T0,T1,…,Tm(即处于m位置的图灵机),…,使每一个下标都能行地和完全地决定了它对应的机器指令。即每一个下标都能行地和完全地决定了它所对应的机器。停机问题是递归不可解的。其证明方法是:只是证明“对任意自然数n,图灵机Tn当输入为n时是否停机?”是递归不可解的即可。令:

f(n)=

若证明了f是图灵不可计算的,也就证明了上列问题是递归不可解的。这一结论也可用反证证明,先假设f为图灵可计算,然后推出矛盾。由于假设f可计算,则可证函数:

g(n)=

也可计算。人们可以算法地描述计算g的过程如下:任给数a,计算f(a)的值,若f(a)=1,则令g(a)=0;若f(a)=0,则令g(a)无定义,即让相应的计算永不停止。至此,由丘奇论题可知g是图灵可计算的。设计算g的程序为Te。现试考察Te对输入e的情况;若Te(e)停机,则由g的定义必有g(e)=0,从而f(e)=1。但由f的定义,应该有Te(e)不停机。另外,若Te(e)不停机,则由g的定义知g(e)是无定义的,从而由g的定义,可得f(e)=0。再由f的定义,应该有Te(e)停机。于是在任何情况下都存在这一矛盾:Te(e)停机,当且仅当,Te(e)不停机。否定前面的假设,故函数f必定是图灵不可计算的。这样也能获得停机问题是递归不可解的结论。停机问题开辟了利用图灵机去解决一般判定问题的途径,所以是递归论中的重要结果。

随便看

 

依恋情感网情感百科知识大全收录了49620条情感类百科知识词条,覆盖心理学、哲学、美学等领域,基本涵盖了日常生活中常见问题的详细解释,是情感生活的有利工具。

 

Copyright © 2002-2024 yiyi18.com All Rights Reserved
更新时间:2025/8/9 22:19:05