Markov algorithm - Revision history

Xleviator: Include link to game, A=B, where you write these. I can't find an official webpage, so this uses the link to steam.

2024-12-25T04:17:33Z

Include link to game, A=B, where you write these. I can't find an official webpage, so this uses the link to steam.

← Previous revision		Revision as of 04:17, 25 December 2024
Line 105:		Line 105:
	* [https://web.archive.org/web/20060217113205/http://nic-nac-project.de/~jcm/index.php?nav=projects Markov algorithm interpreter]		* [https://web.archive.org/web/20060217113205/http://nic-nac-project.de/~jcm/index.php?nav=projects Markov algorithm interpreter]
	* [http://rosettacode.org/wiki/Execute_a_Markov_algorithm Markov algorithm interpreters at Rosetta-Code]		* [http://rosettacode.org/wiki/Execute_a_Markov_algorithm Markov algorithm interpreters at Rosetta-Code]
			* [https://store.steampowered.com/app/1720850/AB/ A=B, a game about writing substitution rules for a Markov algorithm]

	{{Strings}}		{{Strings}}

Comp.arch at 22:07, 2 December 2024

2024-12-02T22:07:20Z

← Previous revision		Revision as of 22:07, 2 December 2024
Line 22:		Line 22:
	For other examples, see below.		For 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."		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 are a number of ideas used in programming languages aimed at handling symbolic information{{snd}}for example, in [[Refal]].		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 are a number of ideas used in programming languages aimed at handling symbolic information{{snd}}for example, in [[Refal]].

Citation bot: Altered issue. Formatted dashes. | Use this bot. Report bugs. | Suggested by Dominic3203 | Category:Models of computation | #UCB_Category 114/125

2024-11-08T15:34:15Z

Altered issue. Formatted dashes. | Use this bot. Report bugs. | Suggested by Dominic3203 | Category:Models of computation | #UCB_Category 114/125

← Previous revision		Revision as of 15:34, 8 November 2024
Line 97:		Line 97:
	==References==		==References==
	* Caracciolo di Forino, A. ''String processing languages and generalized Markov algorithms.'' In Symbol manipulation languages and techniques, D. G. Bobrow (Ed.), North-Holland Publ. Co., Amsterdam, the Netherlands, 1968, pp. 191–206.		* Caracciolo di Forino, A. ''String processing languages and generalized Markov algorithms.'' In Symbol manipulation languages and techniques, D. G. Bobrow (Ed.), North-Holland Publ. Co., Amsterdam, the Netherlands, 1968, pp. 191–206.
	* [[Andrey Markov (Soviet mathematician)\|Andrey Andreevich Markov (1903-1979)]] 1960. ''The Theory of Algorithms.'' American Mathematical Society Translations, series 2, 15, 1-14. (Translation from the Russian, Trudy Instituta im. Steklova 38 (1951) 176-189<ref>{{Cite journal \|last=Kushner \|first=Boris A. \|date=1999-05-28 \|title=Markov's constructive analysis; a participant's view \|url=https://core.ac.uk/works/41825477 \|journal=Theoretical Computer Science \|language=en \|volume=219 \|issue=~~1-2~~ \|pages=268, 284 \|doi=10.1016/S0304-3975(98)00291-6\|doi-access=free }}</ref>)		* [[Andrey Markov (Soviet mathematician)\|Andrey Andreevich Markov (1903-1979)]] 1960. ''The Theory of Algorithms.'' American Mathematical Society Translations, series 2, 15, 1-14. (Translation from the Russian, Trudy Instituta im. Steklova 38 (1951) 176-189<ref>{{Cite journal \|last=Kushner \|first=Boris A. \|date=1999-05-28 \|title=Markov's constructive analysis; a participant's view \|url=https://core.ac.uk/works/41825477 \|journal=Theoretical Computer Science \|language=en \|volume=219 \|issue=1–2 \|pages=268, 284 \|doi=10.1016/S0304-3975(98)00291-6\|doi-access=free }}</ref>)
	<references />		<references />

Explicit: Removing link(s) Wikipedia:Articles for deletion/Thue (programming language) (2nd nomination) closed as delete (XFDcloser)

2024-06-24T00:41:53Z

Removing link(s) Wikipedia:Articles for deletion/Thue (programming language) (2nd nomination) closed as delete (XFDcloser)

← Previous revision		Revision as of 00:41, 24 June 2024
Line 93:		Line 93:

	==See also==		==See also==
	* [[Thue (programming language)]]
	* [[Formal grammar]]		* [[Formal grammar]]

2A04:EE41:3:129D:10DD:FBF8:AC02:2932: /* Description */

2023-08-31T19:05:45Z

Description

← Previous revision		Revision as of 19:05, 31 August 2023
Line 9:		Line 9:
	Normal algorithms are verbal, that is, intended to be applied to strings in different alphabets.		Normal algorithms are verbal, that is, intended to be applied to strings in different alphabets.

	The definition of any normal algorithm consists of two parts: an ''alphabet'', which is a set of symbols, and a ''scheme''. The algorithm is applied to strings of symbols of the alphabet. The scheme is a finite ordered set of ''substitution formulas''. Each formula can be either ''simple'' or ''final''. Simple substitution formulas are represented by strings of the form <math>L\to D</math>, where <math>L</math> and <math>D</math> are two arbitrary strings in the alphabet. Similarly, final substitution formulas are represented by strings of the form <math>L\to\cdot D</math>~~, where <math>L</math> and <math>D</math> are two arbitrary strings in the alphabet of the algorithm~~.		The definition of any normal algorithm consists of two parts: an ''alphabet'', which is a set of symbols, and a ''scheme''. The algorithm is applied to strings of symbols of the alphabet. The scheme is a finite ordered set of ''substitution formulas''. Each formula can be either ''simple'' or ''final''. Simple substitution formulas are represented by strings of the form <math>L\to D</math>, where <math>L</math> and <math>D</math> are two arbitrary strings in the alphabet. Similarly, final substitution formulas are represented by strings of the form <math>L\to\cdot D</math>.

	Here is an example of a normal algorithm scheme in the five-letter alphabet <math>\|*abc</math>:		Here is an example of a normal algorithm scheme in the five-letter alphabet <math>\|*abc</math>:

2A04:EE41:3:129D:10DD:FBF8:AC02:2932: clarified, untangled words

2023-08-31T19:04:39Z

clarified, untangled words

← Previous revision		Revision as of 19:04, 31 August 2023
Line 9:		Line 9:
	Normal algorithms are verbal, that is, intended to be applied to strings in different alphabets.		Normal algorithms are verbal, that is, intended to be applied to strings in different alphabets.

	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''~~. The scheme ~~of a normal algorithm~~ is a finite ordered set of ~~so-called~~ ''substitution formulas'', ~~each~~ ~~of which~~ can be ''simple'' or ''final''. Simple substitution formulas are represented by strings of the form <math>L\to D</math>, where <math>L</math> and <math>D</math> are two arbitrary strings in the alphabet ~~of the algorithm (called, respectively, the left and right sides of the formula substitution)~~. Similarly, final substitution formulas are represented by strings of the form <math>L\to\cdot D</math>, where <math>L</math> and <math>D</math> are two arbitrary strings in the alphabet of the algorithm. This assumes that the auxiliary characters <math>\to</math> and <math>\to\cdot</math> do not belong to the alphabet of the algorithm (otherwise two other characters to perform their role as the dividers of the left and right sides, which are not in the algorithm's alphabet, should be selected).		The definition of any normal algorithm consists of two parts: an ''alphabet'', which is a set of symbols, and a ''scheme''. The algorithm is applied to strings of symbols of the alphabet. The scheme is a finite ordered set of ''substitution formulas''. Each formula can be either ''simple'' or ''final''. Simple substitution formulas are represented by strings of the form <math>L\to D</math>, where <math>L</math> and <math>D</math> are two arbitrary strings in the alphabet. Similarly, final substitution formulas are represented by strings of the form <math>L\to\cdot D</math>, where <math>L</math> and <math>D</math> are two arbitrary strings in the alphabet of the algorithm.

	Here is an example of a normal algorithm scheme in the five-letter alphabet <math>\|*abc</math>:		Here is an example of a normal algorithm scheme in the five-letter alphabet <math>\|*abc</math>:

Dicklyon: case fix (via WP:JWB)

2023-08-23T21:04:34Z

case fix (via WP:JWB)

← Previous revision		Revision as of 21:04, 23 August 2023
Line 97:		Line 97:

	==References==		==References==
	* Caracciolo di Forino, A. ''String processing languages and generalized Markov algorithms.'' In Symbol manipulation languages and techniques, D. G. Bobrow (Ed.), North-Holland Publ. Co., Amsterdam, ~~The~~ Netherlands, 1968, pp. 191–206.		* Caracciolo di Forino, A. ''String processing languages and generalized Markov algorithms.'' In Symbol manipulation languages and techniques, D. G. Bobrow (Ed.), North-Holland Publ. Co., Amsterdam, the Netherlands, 1968, pp. 191–206.
	* [[Andrey Markov (Soviet mathematician)\|Andrey Andreevich Markov (1903-1979)]] 1960. ''The Theory of Algorithms.'' American Mathematical Society Translations, series 2, 15, 1-14. (Translation from the Russian, Trudy Instituta im. Steklova 38 (1951) 176-189<ref>{{Cite journal \|last=Kushner \|first=Boris A. \|date=1999-05-28 \|title=Markov's constructive analysis; a participant's view \|url=https://core.ac.uk/works/41825477 \|journal=Theoretical Computer Science \|language=en \|volume=219 \|issue=1-2 \|pages=268, 284 \|doi=10.1016/S0304-3975(98)00291-6\|doi-access=free }}</ref>)		* [[Andrey Markov (Soviet mathematician)\|Andrey Andreevich Markov (1903-1979)]] 1960. ''The Theory of Algorithms.'' American Mathematical Society Translations, series 2, 15, 1-14. (Translation from the Russian, Trudy Instituta im. Steklova 38 (1951) 176-189<ref>{{Cite journal \|last=Kushner \|first=Boris A. \|date=1999-05-28 \|title=Markov's constructive analysis; a participant's view \|url=https://core.ac.uk/works/41825477 \|journal=Theoretical Computer Science \|language=en \|volume=219 \|issue=1-2 \|pages=268, 284 \|doi=10.1016/S0304-3975(98)00291-6\|doi-access=free }}</ref>)
	<references />		<references />

Jarble: adding Template:Strings

2023-05-31T20:20:13Z

adding Template:Strings

← Previous revision		Revision as of 20:20, 31 May 2023
Line 106:		Line 106:
	* [https://web.archive.org/web/20060217113205/http://nic-nac-project.de/~jcm/index.php?nav=projects Markov algorithm interpreter]		* [https://web.archive.org/web/20060217113205/http://nic-nac-project.de/~jcm/index.php?nav=projects Markov algorithm interpreter]
	* [http://rosettacode.org/wiki/Execute_a_Markov_algorithm Markov algorithm interpreters at Rosetta-Code]		* [http://rosettacode.org/wiki/Execute_a_Markov_algorithm Markov algorithm interpreters at Rosetta-Code]
			{{Strings}}

	[[Category:Theory of computation]]		[[Category:Theory of computation]]

OAbot: Open access bot: doi added to citation with #oabot.

2023-01-29T21:59:27Z

Open access bot: doi added to citation with #oabot.

← Previous revision		Revision as of 21:59, 29 January 2023
Line 98:		Line 98:
	==References==		==References==
	* Caracciolo di Forino, A. ''String processing languages and generalized Markov algorithms.'' In Symbol manipulation languages and techniques, D. G. Bobrow (Ed.), North-Holland Publ. Co., Amsterdam, The Netherlands, 1968, pp. 191–206.		* Caracciolo di Forino, A. ''String processing languages and generalized Markov algorithms.'' In Symbol manipulation languages and techniques, D. G. Bobrow (Ed.), North-Holland Publ. Co., Amsterdam, The Netherlands, 1968, pp. 191–206.
	* [[Andrey Markov (Soviet mathematician)\|Andrey Andreevich Markov (1903-1979)]] 1960. ''The Theory of Algorithms.'' American Mathematical Society Translations, series 2, 15, 1-14. (Translation from the Russian, Trudy Instituta im. Steklova 38 (1951) 176-189<ref>{{Cite journal \|last=Kushner \|first=Boris A. \|date=1999-05-28 \|title=Markov's constructive analysis; a participant's view \|url=https://core.ac.uk/works/41825477 \|journal=Theoretical Computer Science \|language=en \|volume=219 \|issue=1-2 \|pages=268, 284 \|doi=10.1016/S0304-3975(98)00291-6}}</ref>)		* [[Andrey Markov (Soviet mathematician)\|Andrey Andreevich Markov (1903-1979)]] 1960. ''The Theory of Algorithms.'' American Mathematical Society Translations, series 2, 15, 1-14. (Translation from the Russian, Trudy Instituta im. Steklova 38 (1951) 176-189<ref>{{Cite journal \|last=Kushner \|first=Boris A. \|date=1999-05-28 \|title=Markov's constructive analysis; a participant's view \|url=https://core.ac.uk/works/41825477 \|journal=Theoretical Computer Science \|language=en \|volume=219 \|issue=1-2 \|pages=268, 284 \|doi=10.1016/S0304-3975(98)00291-6\|doi-access=free }}</ref>)
	<references />		<references />

MarMi wiki: /* References */ ref. to 1951

2022-06-21T18:47:38Z

References: ref. to 1951

← Previous revision		Revision as of 18:47, 21 June 2022
Line 98:		Line 98:
	==References==		==References==
	* Caracciolo di Forino, A. ''String processing languages and generalized Markov algorithms.'' In Symbol manipulation languages and techniques, D. G. Bobrow (Ed.), North-Holland Publ. Co., Amsterdam, The Netherlands, 1968, pp. 191–206.		* Caracciolo di Forino, A. ''String processing languages and generalized Markov algorithms.'' In Symbol manipulation languages and techniques, D. G. Bobrow (Ed.), North-Holland Publ. Co., Amsterdam, The Netherlands, 1968, pp. 191–206.
	* [[Andrey Markov (Soviet mathematician)\|Andrey Andreevich Markov (1903-1979)]] 1960. ''The Theory of Algorithms.'' American Mathematical Society Translations, series 2, 15, 1-14. (Translation from the Russian, Trudy Instituta im. Steklova 38 (1951) 176-189)		* [[Andrey Markov (Soviet mathematician)\|Andrey Andreevich Markov (1903-1979)]] 1960. ''The Theory of Algorithms.'' American Mathematical Society Translations, series 2, 15, 1-14. (Translation from the Russian, Trudy Instituta im. Steklova 38 (1951) 176-189<ref>{{Cite journal \|last=Kushner \|first=Boris A. \|date=1999-05-28 \|title=Markov's constructive analysis; a participant's view \|url=https://core.ac.uk/works/41825477 \|journal=Theoretical Computer Science \|language=en \|volume=219 \|issue=1-2 \|pages=268, 284 \|doi=10.1016/S0304-3975(98)00291-6}}</ref>)
			<references />

	==External links==		==External links==