Rice's theorem
Considering algorithmically not solvable problem is easy to see that almost all of them related to samozastosovnistyu - a situation where the algorithm operates with its own description. In applied theory of algorithms can solve that, because the concept is far from samozastosovnosti algorithmic practice, the not solvable in it will never happen. However, it is not.
Rice's theorem: Let C - any class calculated functions of one variable, non-trivial in the sense that there is a function belonging to C, and functions that do not belong to S. Then there is no algorithm that would be the number x defined functions fx , fx is a Class C or not (then say that the set {x | fx is C} is not solved).
With Rice's theorem implies that the number computed by the function can not tell if this function is constant, intermittent, limited, or contains, among its values given number. It seems that nothing is impossible to know and everything in the world - not solvable. On the other hand, does not contradict Theorem Rice the obvious fact that the number of Turing machine can always learn, for example, whether it contains more than 10 teams or not. In order to understand the meaning of Rice's theorem, it should first recall that the number's function f - is the number of algorithm that computes f; in turn, the number of algorithm uniquely recovers its description, and different numbers correspond to different algorithms.For functions this is not true: if х is'nt y fx and fy are the same function. In Theorem Rice involved as algorithms and functions that need to be clearly distinguished. Class C - a class of functions, while fx mean "function that calculates algorithm Ах ."
Thus, the value of Rice's theorem is that the description of the algorithm's nothing you can learn about the properties of functions, which he calculates. In particular, it appears not solvable problem of equivalence of algorithms: two algorithms given can not be set, they calculated the same function or not. Number of teams - this property does not function, and describe the algorithm, Rice's theorem is not applicable. An experienced programmer knows that the text of a complex program without running it into work, it is difficult to understand what it does without hypotheses about what she should do, if this understanding is reached and, each time differently, systematic method here does not exist. On the other hand, the text can be found algorithmic method syntax errors, that is to install these or other properties of the algorithm description. Syntactic properties of the algorithm - it features texts that describe it, that the properties of finite words in a fixed alphabet. Semantic properties of algorithms related to the fact that he does, they naturally described in terms of functions and equivalence classes of functions that are calculated algorithms. Obviously, in the process of debugging syntax errors are found quickly, all unpleasantness associated with the analysis of semantics an not established program that attempts to determine what it does instead of doing what was planned.
Informal interpretation of Rice's theorem: "Algorithm for syntax did not know about its semantics." The expression "do not know" - this is an exaggeration. His exact equivalent of "no single algorithm that allows to know."
Some of the problems not solvable general theory of algorithms are defined interpretation in practice of programming. Not solvable also occurs in other theories: machine, languages and grammars. From a theoretical point of view, not solvable - not failure, but scientific fact. If it is important to deal with a solvable problem, you need to clear about two things: no general algorithm that solves this problem does not mean that in each case can not succeed; not solvable appearance - this is usually the result of excessive generality problem .
Considering algorithmically not solvable problem is easy to see that almost all of them related to samozastosovnistyu - a situation where the algorithm operates with its own description. In applied theory of algorithms can solve that, because the concept is far from samozastosovnosti algorithmic practice, the not solvable in it will never happen. However, it is not.
Rice's theorem: Let C - any class calculated functions of one variable, non-trivial in the sense that there is a function belonging to C, and functions that do not belong to S. Then there is no algorithm that would be the number x defined functions fx , fx is a Class C or not (then say that the set {x | fx is C} is not solved).
With Rice's theorem implies that the number computed by the function can not tell if this function is constant, intermittent, limited, or contains, among its values given number. It seems that nothing is impossible to know and everything in the world - not solvable. On the other hand, does not contradict Theorem Rice the obvious fact that the number of Turing machine can always learn, for example, whether it contains more than 10 teams or not. In order to understand the meaning of Rice's theorem, it should first recall that the number's function f - is the number of algorithm that computes f; in turn, the number of algorithm uniquely recovers its description, and different numbers correspond to different algorithms.For functions this is not true: if х is'nt y fx and fy are the same function. In Theorem Rice involved as algorithms and functions that need to be clearly distinguished. Class C - a class of functions, while fx mean "function that calculates algorithm Ах ."
Thus, the value of Rice's theorem is that the description of the algorithm's nothing you can learn about the properties of functions, which he calculates. In particular, it appears not solvable problem of equivalence of algorithms: two algorithms given can not be set, they calculated the same function or not. Number of teams - this property does not function, and describe the algorithm, Rice's theorem is not applicable. An experienced programmer knows that the text of a complex program without running it into work, it is difficult to understand what it does without hypotheses about what she should do, if this understanding is reached and, each time differently, systematic method here does not exist. On the other hand, the text can be found algorithmic method syntax errors, that is to install these or other properties of the algorithm description. Syntactic properties of the algorithm - it features texts that describe it, that the properties of finite words in a fixed alphabet. Semantic properties of algorithms related to the fact that he does, they naturally described in terms of functions and equivalence classes of functions that are calculated algorithms. Obviously, in the process of debugging syntax errors are found quickly, all unpleasantness associated with the analysis of semantics an not established program that attempts to determine what it does instead of doing what was planned.
Informal interpretation of Rice's theorem: "Algorithm for syntax did not know about its semantics." The expression "do not know" - this is an exaggeration. His exact equivalent of "no single algorithm that allows to know."
Some of the problems not solvable general theory of algorithms are defined interpretation in practice of programming. Not solvable also occurs in other theories: machine, languages and grammars. From a theoretical point of view, not solvable - not failure, but scientific fact. If it is important to deal with a solvable problem, you need to clear about two things: no general algorithm that solves this problem does not mean that in each case can not succeed; not solvable appearance - this is usually the result of excessive generality problem .
No comments:
Post a Comment