丘奇论题查看源代码讨论查看历史

来自 搜狐网 的图片

丘奇论题是一个科技名词。

汉字(拼音:hàn zì，注音符号:ㄏㄢˋ ㄗˋ)，又称中文、中国字、方块字，是汉语的记录符号，属于表意文字的词素音节文字。世界上最古老的文字之一，已有六千多年的历史。在形体上逐渐由图形变为笔画，象形变为象征，复杂变为简单;在造字原则上从表形、表意到形声。除极个别汉字外(如瓩、兛、兣、呎、嗧等)，都是一个汉字一个音节。 需要注意的是，日本、韩国、朝鲜、越南等国在历史上都深受汉文化的影响，甚至其语文都存在借用汉语言文字的现象。

名词解释

邱奇论题是一个关于可计算性理论的假设。该假设论述了关于函数特性的，可有效计算的函数值（用更现代的表述来说--在算法上可计算的)。简单来说，邱奇-图灵论题认为“任何在算法上可计算的问题同样可由图灵机计算”。

假说前提

已知的三种计算过程（递归，λ演算和图灵机）都是等价的--这三种方法定义了同一类函数。这导致数学家和计算机科学家相信可计算性的概念可由上述三种等价的计算过程描述。简单来讲，邱奇-图灵论题认为如果某种方法（算法）可进行运算，那么该运算也可被图灵机执行（也可被递归定义的函数或λ函数执行）。

邱奇-图灵论题是对计算特性进行描述的一种陈述，故而不能被严格证明。虽然上面提到的三种计算过程可被证明为等价的，但是邱奇-图灵论题最根本的前提--声称一个函数是“可有效计算的”究竟意味着什么--在某种意义上是不甚明确的直觉结果。所以，该论题依然是一个假想。

尽管邱奇-图灵论题不能被证明，它仍然受到近乎全面的接受。

正式阐述

Rosser于1939年对“可有效计算性”进行了如下的解读：“很明显CC和RC（邱奇和Rosser的论据）的成立依赖于对‘有效性’的严格定义。‘有效的方法’主要是指该方法的每一步都可被事先确定，而且该方法可在有限的步数之内生成结果”。因此，‘有效性’实际上包含两层含义：

（1）产生一种确定的，或者所需的效果；

（2）能够产生计算结果。

接下来， 术语“可有效演算的”意味着“由任何直观上有效的方法产生的”，而术语“可有效计算的”意味着“由图灵机或任何等价的机械设备产生的”。图灵本人对此的定义由他在1939年的博士论文“基于有序数的逻辑系统”的脚注中给出：“我们应该使用‘可计算函数’来表示一个可被机器计算的函数， 使用‘可有效演算的’来指代那些并未特别指明的直观想法。”

这可以转述为：任何可有效演算的函数都是可计算函数。

图灵则是如此描述的：“当一个函数的值可由某种纯机械计算步骤得到时， 它就是可有效演算的函数...应该这样认识： 可计算性和可有效演算性是不同的。”

等价形式

本论题的另外一种说法就是逻辑和数学中的有效或机械方法可由图灵机来表示。通常我们假定这些方法必须满足以下的要求：

1.一个方法由有限多简单和精确的指令组成，这些指令可由有限多的符号来描述。

2.该方法总会在有限的步骤内产生出一个结果。

3.基本上人可以仅用纸张和铅笔来执行。

4.该方法的执行不需人类的智慧来理解和执行这些指令。

此类方法的一个范例便是用于确定两个自然数的最大公约数的欧基里德算法。

“有效方法”这个想法在直觉上是清楚的，但却没有在形式上加以定义，因为什么是“一个简单而精确的指令”和什么是“执行这些指令所需的智力”这两个问题并没有明确的答案。（如需欧几里得算法之外的范例，请参见数论中的有效结果。）