遞歸可判定的是遞歸可判定的及判定問題（decision problem）如何尋找一種方法，去判定某一個事物是否具有某種屬性的問題。
基本介紹
- 中文名：遞歸可判定的
- 所屬學科：哲學
主要指公式的可證性、普遍有效性和可滿足性。在數理邏輯中，一個判定問題有如下的一般形式：給出一個集合A和一性質P，去尋找一個算法，使它能告知對於集合A中的任何元素a（即aEA），是否具有性質P；或者能證明不可能找到這樣的算法。例如：自然數n是偶數嗎？這裡自然數n組成的集合N，就相當於一般形式中的集合A，“是偶數嗎”？相當於性質P。它構成一個判定問題：可以用符號寫成：
{自然數n是偶數嗎？InEN}
顯然這個判定問題存在一個算法，對於N中的任一個自然n。
則只需用2去除。如果餘數為0，那么n就是偶數；如果餘數為1，n就不是自然數。這一算法適用於一切自然數。給出一個數論謂詞（或一個數論關係），或依賴於若干參數的問題類M（x1…，x，），對任意數a…，anEN，問M（a…，an）是否成立或是否真的判定問題又往往可歸結為給定N的一個子集A，對任意xEN，問x是否屬於A？如能找到一個機械的方法（或算法），用它可對任意a…，anEN，能在有限步內判定M（an…，an）是否成立，或對任意xEN，能在有限步內判定x是否在A中，則稱相應的判定問題是能行可解的。如找不到所要的算法，則稱相應的判定問題是能行不可解的。如果使用了丘奇論點，那末判定問題則成為是否能找到某個遞歸函式的問題，或成為證明某個數論函式是否可計算的問題。令：
Ca（xs，…，x。）=|0若M（x…，x。）成立，11，若M（x…。x。）不成立。
或：
Cx（x）=（9若×在A中，11，若x不在A中）。
若Cu（或CA）是一個遞歸函式（或是可計算的），則稱相應的判定問題M（xx…，x）（或xEA？）是遞歸可解的，或遞歸可判定的。若Cu（或CA）不是一個遞歸函式（或不可計算），則稱相應的判定問題是遞歸不可解的，或遞歸不可判定的。
再令：
Ci（x，…，x）=0.若M（x…，x。）成立，“%1無定義，若M（x，…，x）不成立。
或：
Ci（x）=（0，若x在A中），無定義，若x不在A中。
若Ca（或CA）是一個遞歸部分函式（或是可計算的），則稱相應的判定問題是半可解的，或是半可判定的。
