Moreover, inherent in the definition of a normal algorithm are a number of ideas used in programming languages aimed at handling symbolic information – for example, in Refal. Normal algorithms have proved to be a convenient means for the construction of many sections of constructive mathematics. A version of the Church-Turing thesis formulated in relation to the normal algorithm is called the "principle of normalization." Īny normal algorithm is equivalent to some Turing machine, and vice versa – any Turing machine is equivalent to some normal algorithm. Simple substitution formulas are represented by strings of the form L → D. The scheme of a normal algorithm is a finite ordered set of so-called substitution formulas, each of which can be simple or final. The definition of any normal algorithm consists of two parts: the definition of the alphabet of the algorithm (the algorithm will be applied to strings of these alphabet symbols), and the definition of its scheme. Normal algorithms are verbal, that is, intended to be applied to strings in different alphabets.
0 Comments
Leave a Reply. |