¿Cuándo podemos decir que dos programas son diferentes?

Q1. ¿Cuándo podemos decir que dos programas (escritos en algún lenguaje de programación como C ++) son diferentes?

El primer extremo es decir que dos programas son equivalentes si son idénticos. El otro extremo es decir que dos programas son equivalentes si calculan la misma función (o muestran el mismo comportamiento observable en entornos similares). Pero estos no son buenos: no todos los programas que verifican la primalidad son iguales. Podemos agregar una línea de código sin efecto en el resultado y todavía lo consideraríamos el mismo programa.

Q2 ¿Son los programas y algoritmos el mismo tipo de objeto? Si no, ¿cuál es la definición de un algoritmo y cómo difiere de la definición de un programa? ¿Cuándo podemos decir que dos algoritmos son equivalentes?

P1: Hay muchas nociones de equivalencia del programa (equivalencia de trazas, equivalencia contextual, equivalencia observacional, bisimilaridad) que pueden o no tener en cuenta cosas como el tiempo, el uso de recursos, el no determinismo, la terminación. Se ha trabajado mucho para encontrar nociones utilizables de equivalencia de programas. Por ejemplo: Teorías de equivalencia de programas basadas en operaciones por Andy Pitts . Pero esto apenas rasca la superficie. Esto debería ser útil incluso si está interesado cuando dos programas no son equivalentes. Incluso se puede razonar acerca de los programas que no se detienen (usando bisimulación y coinducción).

P2: Una posible respuesta a parte de esta pregunta es que los programas interactivos no son algoritmos (suponiendo que uno considere un algoritmo para tomar toda su información de una vez, pero esta definición limitada excluye los algoritmos en línea). Un programa podría ser una colección de procesos interactivos que también interactúan con su entorno. Esto ciertamente no coincide con la noción de algoritmo de la teoría de Turing-máquina / recursividad.

El otro extremo es decir que dos programas son equivalentes si calculan la misma función (o muestran el mismo comportamiento observable en entornos similares). Pero estos no son buenos: no todos los programas que verifican la primalidad son iguales. Podemos agregar una línea de código sin efecto en el resultado y todavía lo consideraríamos el mismo programa.

Esto no es un extremo: la equivalencia del programa debe definirse en relación con una noción de observación.

La definición más común en la investigación de PL es la equivalencia contextual. En equivalencia contextual, la idea es que observemos los programas usándolos como componentes de programas más grandes (el contexto). Entonces, si dos programas calculan el mismo valor final para todos los contextos, entonces se consideran iguales. Dado que esta definición cuantifica todos los contextos posibles del programa, es difícil trabajar directamente. Entonces, un programa de investigación típico en PL es encontrar principios de razonamiento compositivo que impliquen equivalencia contextual.

Sin embargo, esta no es la única noción posible de observación. Por ejemplo, podemos decir fácilmente que la memoria, el tiempo o el comportamiento de potencia de un programa es observable. En este caso, se mantienen menos equivalencias de programa, ya que podemos distinguir más programas (por ejemplo, mergesort ahora se puede distinguir de quicksort). Si desea (por ejemplo) diseñar lenguajes inmunes a los ataques de canales de tiempo, o diseñar lenguajes de programación limitados por el espacio, entonces este es el tipo de cosas que debe hacer.

Además, podemos elegir juzgar algunos de los estados intermedios de un cálculo como observables. Esto siempre sucede para los idiomas concurrentes, debido a la posibilidad de interferencia. Pero es posible que desee tomar esta vista incluso para lenguajes secuenciales, por ejemplo, si desea asegurarse de que ningún cómputo almacene datos sin cifrar en la memoria principal, entonces debe considerar las escrituras en la memoria principal como observables.

Básicamente, no existe una noción única de equivalencia del programa; siempre es relativo a la noción de observación que elija, y eso depende de la aplicación que tenga en mente.

P2: Creo que las definiciones teóricas habituales no distinguen realmente entre algoritmos y programas, pero el "algoritmo", como se usa comúnmente, se parece más a una clase de programas. Para mí, un algoritmo es como un programa con algunas subrutinas que no se especifican por completo (es decir, su comportamiento deseado está definido pero no su implementación). Por ejemplo, el algoritmo de eliminación gaussiano realmente no especifica cómo se debe realizar la multiplicación entera.

Lo siento si esto es ingenuo. No hago investigación PL.