网站首页 情感咨询 情感美文 情感百科 情感生活 学习充电 旧版美文
| 标题 | 停机问题 |
| 类别 | 哲学 |
| 释义 | 停机问题 halting problem 递归论研究的重要判定问题之一,即图灵机的停机问题。其内容为:对任意给出的自然数对m,n,判定图灵机Tm在输入为n时是否停机?抽象地讲,一图灵机就是一指令集,即一个相容的程序,一个相容的四元组集合。通过对四元组、四元组有限集的编码,可以对图灵机加以编码。根据枚举定理:所有图灵机的集合是递归可枚举的。因此一切图灵机可以排列成T0,T1,…,Tm(即处于m位置的图灵机),…,使每一个下标都能行地和完全地决定了它对应的机器指令。即每一个下标都能行地和完全地决定了它所对应的机器。停机问题是递归不可解的。其证明方法是:只是证明“对任意自然数n,图灵机Tn当输入为n时是否停机?”是递归不可解的即可。令: f(n)= g(n)= |
| 随便看 |
|
依恋情感网情感百科知识大全收录了49620条情感类百科知识词条,覆盖心理学、哲学、美学等领域,基本涵盖了日常生活中常见问题的详细解释,是情感生活的有利工具。