设p(x，…，x，y，…，y)(m、n≥0)是整系数多项式，谓词p(x，…，x，y，…，y)=0
称为多项式谓词；谓词
称为刁番图谓词。
刁番图谓词的外延集
称作刁番图集。
显然，多项式谓词都是递归的(事实上都是原始递归的)，因而刁番图谓词都是半可判定的(刁番图集都是递归可枚举集)。
现已知道，每个半可判定的谓词也都是刁番图谓词，每个递归可枚举集也都是刁番图集。(参见戴维斯-普特南-罗宾逊-马蒂亚塞维奇定理。)
