丘奇論題

來自 搜狐網 的圖片

丘奇論題是一個科技名詞。

漢字(拼音:hàn zì，注音符號:ㄏㄢˋ ㄗˋ)，又稱中文、中國字、方塊字，是漢語的記錄符號，屬於表意文字的詞素音節文字。世界上最古老的文字之一，已有六千多年的歷史。在形體上逐漸由圖形變為筆畫，象形變為象徵，複雜變為簡單;在造字原則上從表形、表意到形聲。除極個別漢字外(如瓩、兛、兣、呎、嗧等)，都是一個漢字一個音節。 需要注意的是，日本、韓國、朝鮮、越南等國在歷史上都深受漢文化的影響，甚至其語文都存在借用漢語言文字的現象。

目錄

名詞解釋

邱奇論題是一個關於可計算性理論的假設。該假設論述了關於函數特性的，可有效計算的函數值（用更現代的表述來說--在算法上可計算的)。簡單來說，邱奇-圖靈論題認為「任何在算法上可計算的問題同樣可由圖靈機計算」。

假說前提

已知的三種計算過程（遞歸，λ演算和圖靈機）都是等價的--這三種方法定義了同一類函數。這導致數學家和計算機科學家相信可計算性的概念可由上述三種等價的計算過程描述。簡單來講，邱奇-圖靈論題認為如果某種方法（算法）可進行運算，那麼該運算也可被圖靈機執行（也可被遞歸定義的函數或λ函數執行）。

邱奇-圖靈論題是對計算特性進行描述的一種陳述，故而不能被嚴格證明。雖然上面提到的三種計算過程可被證明為等價的，但是邱奇-圖靈論題最根本的前提--聲稱一個函數是「可有效計算的」究竟意味着什麼--在某種意義上是不甚明確的直覺結果。所以，該論題依然是一個假想。

儘管邱奇-圖靈論題不能被證明，它仍然受到近乎全面的接受。

正式闡述

Rosser於1939年對「可有效計算性」進行了如下的解讀：「很明顯CC和RC（邱奇和Rosser的論據）的成立依賴於對『有效性』的嚴格定義。『有效的方法』主要是指該方法的每一步都可被事先確定，而且該方法可在有限的步數之內生成結果」。因此，『有效性』實際上包含兩層含義：

（1）產生一種確定的，或者所需的效果；

（2）能夠產生計算結果。

接下來， 術語「可有效演算的」意味着「由任何直觀上有效的方法產生的」，而術語「可有效計算的」意味着「由圖靈機或任何等價的機械設備產生的」。圖靈本人對此的定義由他在1939年的博士論文「基於有序數的邏輯系統」的腳註中給出：「我們應該使用『可計算函數』來表示一個可被機器計算的函數， 使用『可有效演算的』來指代那些並未特別指明的直觀想法。」

這可以轉述為：任何可有效演算的函數都是可計算函數。

圖靈則是如此描述的：「當一個函數的值可由某種純機械計算步驟得到時， 它就是可有效演算的函數...應該這樣認識： 可計算性和可有效演算性是不同的。」

等價形式

本論題的另外一種說法就是邏輯和數學中的有效或機械方法可由圖靈機來表示。通常我們假定這些方法必須滿足以下的要求：

1.一個方法由有限多簡單和精確的指令組成，這些指令可由有限多的符號來描述。

2.該方法總會在有限的步驟內產生出一個結果。

3.基本上人可以僅用紙張和鉛筆來執行。

4.該方法的執行不需人類的智慧來理解和執行這些指令。

此類方法的一個範例便是用於確定兩個自然數的最大公約數的歐基里德算法。

「有效方法」這個想法在直覺上是清楚的，但卻沒有在形式上加以定義，因為什麼是「一個簡單而精確的指令」和什麼是「執行這些指令所需的智力」這兩個問題並沒有明確的答案。（如需歐幾里得算法之外的範例，請參見數論中的有效結果。）