Algoritmo normal

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 10 de noviembre de 2021; las comprobaciones requieren 2 ediciones .

Un algoritmo normal (algoritmo) de Markov ( NAM , también un algoritmo de Markov ) es una de las formas estándar de definir formalmente el concepto de un algoritmo (otro método bien conocido es una máquina de Turing ). El concepto de algoritmo normal fue introducido por A. A. Markov (junior) a fines de la década de 1940 en trabajos sobre la irresolubilidad de algunos problemas en la teoría de cálculos asociativos. La ortografía y pronunciación tradicional de la palabra "algori f m" en este término también se remonta a su autor, quien durante muchos años impartió un curso de lógica matemática en la Facultad de Mecánica y Matemáticas de la Universidad Estatal de Moscú .

El algoritmo normal describe un método de reescritura de cadenas, similar a las gramáticas formales . NAM es un lenguaje completo de Turing , lo que lo hace equivalente en poder expresivo a una máquina de Turing y, por lo tanto, a los lenguajes de programación modernos. El lenguaje de programación funcional Refal se creó sobre la base de NAM .

Descripción

Los algoritmos normales son verbales, es decir, están destinados a ser aplicados a palabras en varios alfabetos.

La definición de cualquier algoritmo normal consta de dos partes: la definición del alfabeto del algoritmo (a las palabras a partir de cuyos caracteres se aplicará el algoritmo) y la definición de su esquema . El esquema de un algoritmo normal es un conjunto ordenado finito de las llamadas fórmulas de sustitución , cada una de las cuales puede ser simple o final . Las fórmulas de sustitución simple son palabras de la forma , donde y son dos palabras arbitrarias en el alfabeto del algoritmo (llamadas, respectivamente, los lados izquierdo y derecho de la fórmula de sustitución). De manera similar, las fórmulas de sustitución finales son palabras de la forma , donde y son dos palabras arbitrarias en el alfabeto del algoritmo. Se supone que las letras auxiliares y no pertenecen al alfabeto del algoritmo (de lo contrario, se deben elegir otras dos letras para que desempeñen el papel de separador entre las partes izquierda y derecha). $L a D$ $L$ $D$ $L\a\cdot D$ $L$ $D$ $\a$ $\a \cdot$

Un ejemplo de un esquema de algoritmo normal en un alfabeto de cinco letras es el esquema $|*abc$

$\left\{{\begin{matriz}|b&\a &ba|\\ab&\a &ba\\b&\a &\\{*}|&\a &b*&\\{*}&\a &c&\ \|c&\to &c\\ac&\to &c|\\c&\to \cdot \end{matriz}}\right.$

El proceso de aplicar el algoritmo normal a una palabra arbitraria en el alfabeto de este algoritmo es una secuencia discreta de pasos elementales, que consta de lo siguiente. Sea la palabra obtenida en el paso anterior del algoritmo (o la palabra original si el paso actual es el primero). Si entre las fórmulas de sustitución no hay ninguna cuyo lado izquierdo esté incluido en , entonces el trabajo del algoritmo se considera completado y el resultado de este trabajo es la palabra . De lo contrario, entre las fórmulas de sustitución, cuya parte izquierda está incluida en , se selecciona la primera. Si esta fórmula de sustitución tiene la forma , entonces de todas las representaciones posibles de la palabra en la forma , se elige una que sea la más corta, después de lo cual el algoritmo se considera completado con el resultado . Si esta fórmula de sustitución tiene la forma , entonces de todas las representaciones posibles de la palabra en la forma , se selecciona la que es la más corta, después de lo cual la palabra se considera el resultado del paso actual, sujeto a un procesamiento adicional en el siguiente paso. $V$ $V'$ $V$ $V'$ $V'$ $V'$ $L\a\cdot D$ $V'$ $RLS$ $R$ $RDS$ $L a D$ $V'$ $RLS$ $R$ $RDS$

Por ejemplo, en el transcurso del proceso de aplicación del algoritmo con el esquema indicado anteriormente , las palabras , , , , , , , , y aparecen secuencialmente a la palabra , luego de lo cual el algoritmo termina con el resultado . Vea más ejemplos a continuación. $|*||$ $|b*|$ $ba|*|$ $un|*|$ $a|b*$ $aba|*$ $bea|*$ $aa|*$ $aa|c$ $ac$ $ca|$ $c||$ $||$

Cualquier algoritmo normal es equivalente a alguna máquina de Turing , y viceversa, cualquier máquina de Turing es equivalente a algún algoritmo normal. Una variante de la tesis de Church-Turing , formulada en relación con los algoritmos normales, se denomina comúnmente "principio de normalización".

Los algoritmos normales han demostrado ser una herramienta conveniente para construir muchas ramas de las matemáticas constructivas . Además, las ideas inherentes a la definición del algoritmo normal se utilizan en varios lenguajes de programación orientados al procesamiento de información simbólica, por ejemplo, en el lenguaje Refal .

Ejemplos

Ejemplo 1

Usando el algoritmo de Markov para transformaciones en cadenas.

Alfabeto:

{ a ... i, A ... I, "espacio", "punto" }

Normas:

A → naranja
kg a kilogramo
M → tienda
T → volumen
tienda →. puesto (fórmula final)
en ese puesto → en ese mercado

línea de origen:

Compré kg Aov en T M.

Cuando se ejecuta el algoritmo, la cadena sufre los siguientes cambios:

Compré un kg de naranjas en T M.
Compré un kilo de naranjas en T.M.
Compré un kilo de naranjas en la tienda T.
Compré un kilo de naranjas en esa tienda.
Compré un kilo de naranjas en ese puesto.

Esto completa la ejecución del algoritmo (ya que se alcanzará la fórmula No. 5, que hicimos definitiva).

Ejemplo 2

Este algoritmo convierte números binarios en " únicos " (en los que el registro de un número entero no negativo N es una cadena de N palos). Por ejemplo, el número binario 101 se convierte en 5 palos: |||||.

Alfabeto:

{ 0, 1, | }

Normas:

1 → 0|
|0 → 0||
0 → "" (cadena vacía)

línea de origen:

101

Actuación:

0|01
0|00|
00||0|
00|0|||
000|||||
00|||||
0|||||
|||||

Véase también

Otros implementadores abstractos y sistemas informáticos formales

Lenguajes basados en algoritmos normales

REFAL
jueves

Otros algoritmos

Algoritmo de operador

Enlaces

diccionarios y enciclopedias	gran ruso