0

我们知道问题是“<em>这个图灵机在那个输入上是否至少采取了这个有限数量的步骤?” 是可判定的,因为它总是回答,如果机器达到给定的步数,它会说,如果在此之前停止,它会说否。

现在这是我的疑问:如果它在达到那么多步骤之前就停止了——即输入要么(1)被接受,要么(2)被拒绝,或者(3)如果它没有停止而是进入无限循环——那么,当我们在情况(3)中时,我们如何确定它总是在那个循环中?我的意思是,如果它不是永远运行,而是在某个时间点退出循环,那么它可能会超过所要求的步骤数,现在可以做出决定,这在以前是不可能的。如果是这样,那么当我们知道被困在一个循环中我们将无法对结果发表任何意见时,我们怎么能得出结论是可以判定的呢?

4

2 回答 2

0

(当我编辑它时,我已经或多或少地回答了你的问题。)

问题是,将图灵机M、数字N和值X作为输入并返回yesno的决策系统(图灵机、算法或任何其他等效形式)完全控制其执行方式MX上。它一步一步地模拟它。因此它可以运行M(X)的一步,增加一个指令计数器,将其与N进行比较,一旦达到给定的步数,它就会停止并返回yes。此时,模拟机M无需处于最终状态,实际上完全计算M(X)很可能发散。我们不在乎,因为我们只运行前N 步。

于 2021-10-19T20:09:31.150 回答
-1

很可能是“条件结构没有得到足够的调试/开发,以至于多个条件经常相互冲突……错误报告不是确定的,所以它使用半抽象概念作为“可判定”和“不可判定”

作为一个半例子,我几年前在 vbs 中写了一个“64 位 rom 内存”模拟器,因为我试图管理内存单元,其中 i/o 读/写位置归属,使用许多公式和条件来设置转换从十进制到二进制和所有操作、索引等。

我也遇到了错误,因为条件不完美。为什么?因为该程序有一些未解决的有些武断的结果,可能会导致:

print.debug "decidable"

On Error Resume h

h:

print.debug "undecidable"

这是一个范围明确且结果值得商榷的例子。

继续回答您的问题:>“那么我们如何得出结论它是可判定的??”

维基百科:图灵机由艾伦·图灵于 1936 年发明,他称其为“a-machine”(自动机器)。使用这个模型,图灵能够回答两个否定的问题:

是否存在可以确定其磁带上的任意机器是否为“循环”(例如,冻结或无法继续其计算任务)的机器?

是否存在可以确定其磁带上的任意机器是否曾经打印给定符号的机器?

因此,通过对能够进行任意计算的非常简单的设备进行数学描述,他能够证明一般计算的属性——特别是(“决策问题”)的不可计算性。

于 2021-10-19T12:58:19.333 回答