直觀可計算函式

tion)一種數論函式.函式f稱為直觀可計算的，是指存在一個算法，依這個算法，可以機械地求出函式f在各個自變數x處的函式值.f (x ).例如，用通常的歐幾里得算法，可以機械地求出任何兩個自然數n和m的最大公因子d fin, m).從而，函式}l.zydC.z,y)就是一個直觀可計算的函式.值得指出的是，由於這裡的“算法”、“機械的”等都不是嚴格定義的概念，因此，函式的“直觀可計算性”概念並不是精確定義的概念.此外，一個函式f是直觀可計算的，只要求存在一個計算f的算法，並不要求已具體給出這種算法(在許多情形，往往比證明其存在性要困難得多).例如，函式f C.z >-{。(哥德巴赫猜想成立)，I1(哥德巴赫猜想不成立).目前尚不知道計算函式f的算法，但由於哥德巴赫猜想總是成立(此時f.恆取0值)或不成立(此時f總取1值)，因此f是一個常值函式，因此，計算f算法總是有的.從而f是一個直觀可計算函式.但真正要找到計算f的算法，必須解決哥德巴赫猜想問題.