数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究什么是理论计算机科学中的停机问题？
通常，程序包含长度有限或无限的循环。
程序完成的工作完全取决于提供给程序的输入。
程序可能包含若干不同数量的循环，这些循环可以是线性或嵌套的。
停机问题是在给定任意计算机程序及其输入的情况下，确定或推断该程序是否会停止执行或对于给定输入运行到无限循环的问题。
停机问题表明，编写一个在有限时间内执行并能够确定程序是否会为某个输入停止的计算机程序并不容易。
此外，停机问题从未说过确定给定随机程序是否会停止是不切实际的。
通常，它会提出类似“给定一个随机程序和一个输入，推断给定随机程序在给出该输入时是否会停止”的问题。
编写停机问题
编写停机问题的一个例子如下：
输入 - 程序 P 和字符串 S。
输出 - 如果 P 在 S 上停止，则返回 1。
否则，如果 P 在 S 上进入无限循环，则返回 0。
让我们考虑一个名为 H 的停机问题，它有解决方案。
现在 H 获取以下两个输入：
程序 P
输入 S。
如果 P 在 S 上停止，则 H 的结果为“停止”，否则 H 的结果为“循环”。
H 的图示表示如下：
示例
ATM = {(M,w) | M 是图灵机，并且 M 在输入 w 处停止}。
我们可以构建一个通用图灵机，它可以在任何输入上模拟任何图灵机。
让我们考虑识别交替图灵机 (ATM) 的图灵机：
Recognize-ATM (<M,w>) Simulate M using UTM till it halts If M halts and accept then Accept Else Reject
假设，如果 M 在输入 w 上进入无限循环，则图灵机 Recognize-ATM 将永远运行，这意味着图灵机只是一个识别器，而不是一个判定器。
此问题的判定器将停止对永远循环的模拟。
现在问题是 ATM 是否是图灵机可判定的，这等同于询问我们是否可以判断图灵机 M 是否会在输入 w 上停止。
因此，这两个版本的这个问题通常都被称为停机问题。
更新于：2021年6月14日
25K+ 浏览量
广告