De hecho, dicho programa resolvería todas las matemáticas (o al menos los sistemas formales). Prácticamente todas las propiedades no triviales de las máquinas (programas) de Turing son indecidibles, lo cual es desafortunado (o afortunado, dependiendo de su perspectiva) porque resolverían todas las matemáticas (o al menos los sistemas formales). Incluso decidir si un programa toma tiempo constante o lineal podría usarse para este fin. Podría escribir un programa que pase tiempo buscando una prueba de un enunciado y se detenga si lo encuentra. Si la declaración es un teorema en su sistema formal, el tiempo de ejecución será constante, de lo contrario es lineal.
Sin embargo, para un tamaño de entrada dado n, ciertamente es posible calcular el número de pasos de tiempo requeridos para un programa en el peor de los casos, siempre que se detenga. Hacemos esto simplemente simulando el programa en todas las entradas y calculando la cantidad máxima de pasos necesarios.
- ¿Cuáles son los problemas actuales que enfrentan los algoritmos de identificación automática de números de clúster?
- Algoritmos: ¿Cómo encuentro un elemento en una secuencia que sea más pequeño que mi número en la secuencia, a la izquierda de mi número y a la derecha de todos esos elementos?
- ¿Qué enfoque debería usarse para resolver esta pregunta sobre hackerrank?
- ¿Existen campamentos de programación a tiempo completo en Europa para mejorar la programación o las estructuras de datos y habilidades de algoritmos?
- ¿Qué son los algoritmos gráficos?
