网站首页 楼盘 > 楼盘优惠 > 正文
导读
想必现在有很多小伙伴对于停机问题证明方面的知识都比较想要了解，那么今天小好小编就为大家收集了一些关于停机问题证明方面的知识分享给
想必现在有很多小伙伴对于停机问题证明方面的知识都比较想要了解，那么今天小好小编就为大家收集了一些关于停机问题证明方面的知识分享给大家，希望大家会喜欢哦。
1、证明一个图灵机是否会停机：图灵会停机，即对任意的输入，我们都能判断其是否停机。
2、我们都知道图灵机都能通过encode过程得到一个code，假设有这么一台图灵机Mm,m是其编号，只需证明无法判断Mm在m上是否停机不可解即可得证。
3、假设我们有一个图灵机C，它的作用是copy自身，即对输入m，得到（m,m）。
4、又构造另一个图灵机D，对于D，如果带子上1的个数大于1就停机，否则不停机。
5、构造一个函数h，h（x,y）=1 如果图灵机Mx在y上停机，否则h(x,y)=2。
6、第一步我们将C和h联合起来得到图灵机G(G的作用可以看成对于输入m，得到h（m,m），即Mm在m上停机时输出1，否则输出2)；第二步将G和D联合起来得到M，编号为m。
7、根据上面的构造可知，Mm在m上停机，当且仅当Mm在m上不停机，矛盾，所以得证！。
本文到此结束，希望对大家有所帮助。
版权说明： 本文由用户上传，如有侵权请联系删除！
- 上一篇： 肉丝跑蛋最正宗的做法（肉丝跑蛋怎么做）
- 下一篇： 男生费纸是什么意思（宅男费纸是什么意思）
猜你喜欢：
- 2022-09-15 母姓的历史（母姓的来历）
- 2022-09-15 酷酷跑兑换码（天天酷跑cdk兑换码怎么获得）
- 2022-09-15 我叫mt网游（网游mt什么意思）
- 2022-09-15 6年免检车行驶证需要盖章吗（6年免检行驶证要盖章吗）
- 2022-09-15 托克逊杏花节是几月几号（托克逊杏花节是几号）
- 2022-09-15 红外青轴是什么（青轴是什么）
- 2022-09-15 南造云子是否真实存在知乎（南造云子是否真实存在）
- 2022-09-15 大人吓着了有什么症状怎么叫魂（大人吓掉魂有什么症状）
最新文章：
- 2023-07-02 怎么选择好羊奶（挑选优质羊奶 如何挑选优质羊奶）
- 2023-07-02 最完整木质结构的古代皇宫建筑群（木质结构古代皇宫建筑群是什么）
- 2023-07-02 红木家具如何挑选
- 2023-07-02 卫生间太暗怎么装修（卫生间太暗怎么办）
- 2023-07-02 窗户贴膜怎么贴才好（窗户贴膜怎么贴）
- 2023-07-02 保险丝熔断的原因初中物理（保险丝熔断的原因是什么）
- 2023-07-02 左眼皮一直跳怎么回事女生（左眼皮一直跳怎么回事）
- 2023-07-02 狗狗乱拉便便怎么办（狗狗乱拉粑粑怎么办）
- 2023-07-02 金毛皮肤病是什么样子（金毛狗狗的皮肤病要如何处理）
- 2023-07-02 榆木家具怎么样（榆木家具怎么保养）
- 2023-07-02 煤气灶保养小常识（煤气灶如何保养）
- 2023-07-02 好听不易撞的网名二字带特殊符号（2020特殊符号网名）
- 2023-07-02 小区房子地基下沉怎么办（地基下沉怎么办）
- 2023-07-02 怎样除猫猫身上的跳蚤（怎么除掉猫身上的跳蚤）
- 2023-07-02 五险一金指什么工厂（五险一金指什么）
- 2023-07-02 空调选购技巧（空调机如何选购）