История изменений

http://www.andrew.cmu.edu/user/avigad/Teaching/candi_notes.pdf

Theorem 3.3.8 (Rice’s theorem) Let C be any set of partial computable functions, and let A = {n | ϕn ∈ C}. If A is computable, then either C is ∅ or C is the set of all the partial computable functions.

An index set is a set A with the property that if n and m are indices which “compute” the same function, then either both n and m are in A, or neither is. It is not hard to see that the set A in the theorem has this property. Conversely, if A is an index set and C is the set of functions computed by these indices, then A = {n | ϕn ∈ C}.

With this terminology, Rice’s theorem is equivalent to saying that no nontrivial index set is decidable. To understand what the theorem says, it is helpful to emphasize the distinction between programs (say, in your favorite programming language) and the functions they compute. There are certainly questions about programs (indices), which are syntactic objects, that are computable: does this program have more than 150 symbols? does it have more than 22 lines? Does it have a “while” statement? Does the string “hello world” every appear in the argument to a “print” statement? Rice’s theorem says that no nontrivial question about the program’s behavior is computable. This includes questions like these: does the program halt on input 0? Does it ever halt? Does it ever output an even number?

С равенство частичных функций, то есть программ, та же история.

http://www.andrew.cmu.edu/user/avigad/Teaching/candi_notes.pdf

Theorem 3.3.8 (Rice’s theorem) Let C be any set of partial computable functions, and let A = {n | ϕn ∈ C}. If A is computable, then either C is ∅ or C is the set of all the partial computable functions.

An index set is a set A with the property that if n and m are indices which “compute” the same function, then either both n and m are in A, or neither is. It is not hard to see that the set A in the theorem has this property. Conversely, if A is an index set and C is the set of functions computed by these indices, then A = {n | ϕn ∈ C}.

With this terminology, Rice’s theorem is equivalent to saying that no nontrivial index set is decidable. To understand what the theorem says, it is helpful to emphasize the distinction between programs (say, in your favorite programming language) and the functions they compute. There are certainly questions about programs (indices), which are syntactic objects, that are computable: does this program have more than 150 symbols? does it have more than 22 lines? Does it have a “while” statement? Does the string “hello world” every appear in the argument to a “print” statement? Rice’s theorem says that no nontrivial question about the program’s behavior is computable. This includes questions like these: does the program halt on

input 0? Does it ever halt? Does it ever output an even number?

С равенство частичных функций, то есть программ, та же история.