Markov algorithm: Difference between revisions

Revision as of 15:24, 18 November 2016

Revision as of 04:33, 16 February 2017

Line 18:

For example, during the process of applying the algorithm to the scheme diagram above the word <math>|*||</math> consistently emerging the words <math>|b*|</math>, <math>ba|*|</math>, <math>a|*|</math>, <math>a|b*</math>, <math>aba|*</math>, <math>baa|*</math>, <math>aa|*</math>, <math>aa|c</math>, <math>aac</math>, <math>ac|</math> и <math>c||</math>, after which the algorithm stops with the result <math>||</math>. Other examples, see below.

Any normal algorithm is equivalent to some [[Turing machine]], and vice versa – {{snd}}any [[Turing machine]] is equivalent to some normal algorithm. A version of the [[Church-Turing thesis]] formulated in relation to the normal algorithm is called the "principle of normalization."

Normal algorithms have proved to be a convenient means for the construction of many sections of [[constructive mathematics]]. Moreover, inherent in the definition of a normal algorithm used in a number of ideas aimed at handling symbolic information programming languages - {{snd}}for example, in [[Refal]].

==Algorithm==