pou*_*def 52 computer-science halting-problem
每当人们询问与编程有关的暂停问题时,人们会回答:"如果你只是添加一个循环,那么你就有了停止程序,因此无法自动完成任务 "
说得通.如果你的程序有一个无限循环,那么当你的程序运行时,你无法知道程序是否仍在处理输入,或者它是否只是无限循环.
但其中一些似乎反直觉.如果我正在编写一个暂停问题求解器,它将源代码作为输入,那该怎么办？rascher@localhost$ ./haltingSolver source.c
如果我的代码(source.c)看起来像这样:
for (;;) { /* infinite loop */ }
看起来我的程序看起来很容易."查看循环,看看条件.如果条件只是基于文字而没有变量,那么你总是知道循环的结果.如果有变量(例如while(x <10)),看看是否这些变量是永远修改的.如果没有,那么你总是知道循环的结果."
当然,这些检查不会是微不足道的(计算指针算术等),但这似乎不可能.例如:
int x = 0
while (x < 10) {}
可以检测到.以及 - 尽管不是轻微的:
int x = 0
while (x < 10)
{
x++;
if (x == 10)
{
x = 0
}
}
那么用户输入呢？这就是踢球者,这就是让程序无法预测的原因.
int x = 0;
while (x < 10)
{
scanf("%d", &x); /* ignoring infinite scanf loop oddities */
}
现在我的程序可以说:"如果用户输入10或更高,程序将停止.在所有其他输入,它将再次循环."
这意味着,即使有数百个输入,也应该能够列出程序停止的条件.实际上,当我编写程序时,我总是确保有人能够终止它!我并不是说由此产生的条件清单是微不足道的,但对我来说似乎并不可能.您可以从用户那里获取输入,使用它们来计算指针索引等等 - 但这只会增加条件的数量以确保程序终止,不会使它们无法枚举.
那么停止问题究竟是什么呢？我不能理解我们不能写一个问题来检测无限循环的想法？或者,为什么"循环"这样一个经常被引用的例子呢？
UPDATE
那么,让我稍微改变一下这个问题:什么是适用于计算机的暂停问题？然后我会回复一些评论:
很多人都说程序必须能够处理"任意输入".但在计算机中,从来没有任何输入.如果我只输入一个字节的数据,那么我只有2 ^ 8个可能的输入.所以,作为一个例子:
int c = getchar()
switch (c) {
case 'q':
/* quit the program */
}
突然间,我刚刚解释了所有的可能性.如果c位模式为0x71,则执行一项操作.对于所有其他模式,它会做其他事情.即使是接受任意字符串输入的程序也绝不是"任意的",因为资源是有限的,这意味着虽然"任意"理论适用......但它与实践并不完全一对一.
人们引用的另一个例子是:
while (n != 1)
if (n & 1 == 1)
n = 3 * n + 1;
else
n /= 2;
如果n是32位整数...那么我可以在视觉上告诉你这是否会停止.
我想这个编辑不是要求任何东西,但我见过的最有说服力的例子就是这个:
假设您有神奇的程序/方法来确定程序停止.
public bool DeterminesHalt(string filename, string[] args){
//runs whatever program you tell it do, passing any args
//returns true if the program halts, false if it doesn't
}
现在让我们说我们写一小段代码,比如......
public static void Main(string[] args){
string filename = Console.ReadLine(); //read in file to run from user
if(DeterminesHalt(filename, args))
for(;;);
else
return;
}
因此,对于这个例子,我们可以编写一个程序来完成与我们神奇的停止方法完全相反的程序.如果我们以某种方式确定给定的程序将停止,我们只是跳进一个无限循环; 否则,如果我们确定程序处于无限循环中,我们就会结束程序.
然后再次,如果你故意写一个包含无限循环的程序......"解决停止问题"有点没有实际意义,不是吗？
Bob*_*oss 51
编辑(比原始答案晚得多):Good Math, Mark Math的 MarkCC 最近用具体的例子写了一篇关于 Halting问题的精彩讨论.
暂停问题基本上是一种正式的方式,询问你是否可以判断任意程序是否最终会停止.
换句话说,你能编写一个名为halting oracle的程序,HaltingOracle(程序,输入),如果程序(输入)最终会停止,它返回true,如果不能,则返回false？
答案是:不,你不能.
跟进关于停止问题的输入是否相关或红鲱鱼的问题:是的,输入很重要.此外,似乎有一些混乱,因为我看到"无限"被用于"任意"更正确的地方.
实际示例:想象一下,您正在QA职位上工作,并且您将编写一个暂停检查程序(也称为oracle),该程序将确认开发团队编写的任意程序(D)以及结尾提供的任意输入-user(I),程序D最终会在输入I时停止.
提示经理的声音:"好吧,那些愚蠢的用户,让我们确保无论他们输入什么垃圾,我们的服务器任务都永远不会以无限循环结束.这样做,代码猴!"
这似乎是一个好主意,对吗？你不希望你的服务器挂起,对吗？
暂停问题告诉你的是你正在接受一项无法解决的任务.相反,在这种特殊情况下,您需要规划超过阈值时间并准备取消它们的任务.
Mark使用代码而不是输入来说明问题:
def Deciever(i):
oracle = i[0]
in = i[1]
if oracle(Deceiver, i):
while True:
continue
else:
return i
在我在评论中的讨论中,我采用了恶意输入操作的方式来强制解决无法解决的问题.马克的例子更加优雅,使用停止的神谕击败自己:
因此,欺骗者的输入实际上是两个元素的列表:第一个是提议的暂停oracle.第二个是另一个输入.停止杀手做的是问Oracle:"你认为我会停止输入吗？".如果oracle说"是的,你会停止",那么程序会进入无限循环.如果神谕说"不,你不会停止",那么它就会停止.所以无论神谕说什么,都是错的.
换句话说,在没有作弊,重新格式化输入,可数/不可数无限或任何其他干扰的情况下,马克编写了一段代码,可以击败任何暂停的oracle程序.你不能写一个oracle回答是否Deceiver永远停止的问题.
原始答案:
来自伟大的维基百科:
在可计算性理论中,暂停问题是一个决策问题,可以表述如下:给定程序和有限输入的描述,在给定输入的情况下,确定程序是否完成运行或将永远运行.
Alan Turing在1936年证明,不存在解决所有可能的程序输入对的暂停问题的通用算法.我们说暂停问题对于图灵机来说是不可判定的.Copeland(2004)将实际停止问题归因于Martin Davis.
其中一个关键点是您无法控制程序或输入.你被交给那些人,你可以自己回答这个问题.
另请注意,图灵机是有效可计算性模型的基础.换句话说,您在现代计算机语言中所做的一切都可以映射回这些原型图灵机.结果,停止问题在任何有用的现代语言中都是不可判定的.
Gra*_*oob 29
这里有一个简单的解释,证明停止问题是不可判定的.
假设您有一个程序H,它计算程序是否停止.H有两个参数,第一个是程序的描述,P,第二个是输入,如果P在输入I上停止,则H返回true,否则返回false.
现在编写一个程序p2,它接受另一个程序p3的描述.p2调用H(p3,p3),然后如果H返回true则循环,否则停止.
当我们运行p2(p2)时会发生什么？
它必须同时循环和停止,导致宇宙爆炸.
有一个OK证明维基百科上的暂停问题.
为了说明,为什么仅仅将一些技术应用于循环是不够的,请考虑以下程序(伪代码):
int main()
{
//Unbounded length integer
Number i = 3;
while(true)
{
//example: GetUniquePositiveDivisiors(6) = [1, 2, 3], ...(5) = 1, ...(10) = 1, 2, 5, etc.
Number[] divisiors = GetUniquePositiveDivisiors(i);
Number sum = 0;
foreach(Number divisor in divisiors) sum += divisor;
if(sum == i) break;
i+=2;
}
}
你能想到一种方法,如果这段代码停止会返回true,否则会返回false？
仔细想想.
如果你有机会争夺菲尔兹奖牌,那么想象一下这些问题的代码来代替上述问题.
"如果你只是添加一个循环,你就有了暂停程序,因此无法自动完成任务"
听起来有人过分概括了暂停问题的应用.有许多特定的循环可以证明终止.存在可以对广泛的程序执行终止检查的研究.例如在Coq中,您仅限于可以证明终止的程序.微软有一个名为Terminator的研究项目,它使用各种近似来证明程序将终止.
但是,请记住,暂停问题不只是玩具示例.这些都没有解决一般的"停止问题",因为它们不适用于每个程序.
问题是停止问题说存在程序,你无法知道它们是否会在不运行它们的情况下终止,这意味着你可能永远无法完成它们是否会停止.
可以停止或不停止的程序示例(在Haskell中):
collatz 1 = ()
collatz !n | odd n = collatz (3 * n + 1)
| otherwise = collatz (n `div` 2)
或者更方便的东西:
while (n != 1)
if (n & 1 == 1)
n = 3 * n + 1;
else
n /= 2;
给定每个> = 1的整数,这个程序会停止吗？嗯,它到目前为止已经奏效了,但是没有定理说它会停止每个整数.我们有一个猜想,因为Lothar Collatz可以追溯到1937年,但它没有证据.
图灵的一个很好的例子是自我指涉 - 假设有一个程序可以检查另一个程序并确定它是否会停止.将停止程序检查器ITSELF送入停止程序检查器 - 它应该怎么做？
参考子句"人们回应"如果你只是添加一个循环,你就有了停止程序,因此你无法自动执行任务"",我将添加这个细节:
那些说你不能通过算法计算任意程序是否会停止的帖子对图灵机来说是完全正确的.
问题是,并非所有程序都需要图灵机.这些程序可以使用概念上"较弱"的机器来计算 - 例如,正则表达式可以完全由有限状态机实现,它总是在输入时停止.不是很好吗？
我打赌,当人们说"添加一个循环"时,他们试图表达这样的想法:当一个程序足够复杂时,它需要一个图灵机,因此停止问题(作为一个想法)适用.
这可能与问题略有不同,但我相信,鉴于问题的细节,这值得指出.:)