2 ms·
The formalization of this idea is Rice's Theorem: https://en.wikipedia.org/wiki/Rice%27s_theorem https://en.wikipedia.org/wiki/Rice%27s_theorem
by haldean 10y ago
The formalization of this idea is Rice's Theorem: https://en.wikipedia.org/wiki/Rice%27s_theorem https://en.wikipedia.org/wiki/Rice%27s_theorem
- catnaroek 10y agoRice's theorem is a statement about partial functions, not programs. There exist decidable properties of programs: Is it of size less than N (for any suitable measure)? Does it finish in less than N steps (for a given fixed input)? Two syntactically distinct programs may compute the same partial function.