Cabe señalar que el esquema de un proceso computacional en su comprensión moderna – escribir un programa en un lenguaje de alto nivel, traducirlo a un lenguaje de máquina y ejecutarlo por una computadora – tiene una base teórica en el teorema de un algoritmo universal. Con cualquier definición precisa de algoritmos, cada algoritmo puede especificarse mediante su propia definición, que es un objeto constructivo. Este objeto constructivo puede ser codificado algorítmicamente en un sentido significativo (y al mismo tiempo bastante simple y natural) por el tipo de objetos estructurales que son procesados por estos algoritmos para conocer Que es un algoritmo.
Por ejemplo, la definición de un algoritmo se puede escribir como una palabra en algún alfabeto, y si tomamos la definición de un algoritmo en el que solo se consideran números naturales, tal palabra se puede representar naturalmente como un número en un sistema numérico. cuya base es el número de letras del alfabeto. Luego hay un algoritmo universal U que procesa cualquier par ( ϕ , P ), donde ϕ es un objeto constructivo llamado registro o programa (con respecto a U ) del algoritmo ϕ , como resultado de aplicar ϕ a P… Un algoritmo universal no se puede definir en todas partes. Si tenemos en cuenta sólo los objetos estructurales, el algoritmo es natural para identificarse con su programa con respecto a una U . Los problemas de la teoría y la práctica de la programación moderna demuestran que tal identificación es limitada. Uno de los problemas más difíciles que surgen en este caso es la restauración del algoritmo según el programa específico que lo implementa. Si el concepto de un algoritmo que procesa objetos estructurales reales puede considerarse definido de manera inequívoca, entonces su generalización a objetos de tipos superiores permite numerosas variantes que no son equivalentes entre sí.
La generalización de la teoría de algoritmos para cálculos abstractos y objetos de orden superior es una de las principales direcciones de investigación en la teoría moderna de algoritmos. Otra área más importante de su desarrollo es la teoría de la complejidad computacional, que considera los problemas de estimación de los recursos necesarios para el funcionamiento de los algoritmos, cuyas bases fueron sentadas por A. N. Kolmogorov y A. A. Markov y S. Kalmar.
Sobre la base de la teoría de la complejidad, A. N. Kolmogorov, L. A. Levin, P. Martin-Lof y otros desarrollaron una teoría algorítmica de probabilidad. La base de esta teoría fue la definición significativa de una secuencia aleatoria según R. Mises. Una secuencia binaria es aleatoria si no se puede seleccionar una secuencia con una frecuencia diferente de ceros y unos. Por ejemplo, la secuencia 0 , 1 , 0 , 1… no es una coincidencia, ya que la secuencia de sus miembros pares consta de una unidad. En matemáticas clásicas, tal definición está vacía. A. N. Kolmogorov lo refinó proponiendo considerar solo permutaciones algorítmicas de subconjuntos de miembros de una secuencia dada. Resultó que la aleatoriedad está asociada con la complejidad de la definición. La complejidad de los fragmentos de una secuencia aleatoria es proporcional a la duración de su registro. Entonces, los objetos significativamente aleatorios son aproximaciones a secuencias aleatorias. Para cualquier conjunto de programas con complejidad limitada, es posible construir un algoritmo universal acotado que los ejecute todos sin errores, pero su complejidad será inconmensurablemente mayor que la complejidad de los programas ejecutables. Además, es posible construir un proceso algorítmico que amplíe el algoritmo universal limitado para que incluir cualquier programa presentado no incluido en esta clase, pero la complejidad del método genérico será aún mayor. Ya un paso de este proceso de diagonalización lleva mucho más allá del alcance de la clase de funciones que se consideran realmente computables.
Cabe señalar que la tesis de Church contiene un supuesto ontológico importante: la imposibilidad de contemplar la eternidad. Por tanto, en la relatividad general (en particular, en el universo de Gödel, en el que el tiempo puede ir en círculo), hay mundos en los que, volando a través de un agujero negro giratorio, se puede calcular una función algorítmicamente no computable. La clase de funciones que se pueden calcular en tales Universos se llama hiperaritmética. Es indefinible en aritmética y solo se puede definir en análisis.
RESPUESTAS