摘要:主要解决了如下形式的程序的终止性判定的问题:while(x∈Ω)do{x:=(f)(x)}end,其中,x为程序变元,Ω(Ω=(a1,b1‖∪‖a2,b2‖∪…∪‖an,bn),其中,‖∈{(,),[,]},n ∈ N*)是间段并集(f)是一个多项式函数.证明了:当ψ(b1)ψ(a2)>0,…,ψ(bn-1)ψ(an)>0(其中,ψ(x)=(f)(x)-x)时,这类区间上的非线性程序不终止的必要条件是:在Ω内部或者边界上存在不动点.如果不动点仅仅在Ω内部,则上述结果是充要条件.通过添加一定的约束条件,对于仅区间边界有不动点的情况,也给出了判定的方法.对一类多项式函数的终止性给出了完备性的算法(TNPSI).