Estoy leyendo un artículo sobre diferentes evaluation strategies (he vinculado el artículo en wiki, pero estoy leyendo otro que no está en inglés). Y dice que a diferencia de las estrategias call-by-name y call-by-need, la estrategia call-by-value es y noTuring complete.¿Por qué la estrategia de evaluación call-by-value no está completa?
¿Alguien puede explicar, por qué es así? Si es posible, agregue un ejemplo de pls.
Disputo el reclamo en el artículo que está leyendo. (No me pagan por esto, así que voy a proporcionar un argumento sugerente, no una prueba.)
Es bien sabido que, al menos bajo la reducción de orden normal (también llamada por nombre), el cálculo lambda puro es Turing-completo. Pero si miramos el artículo seminal de John Reynolds Definitional Interpreters for Higher-Order Programming Languages, podemos ver que Reynolds discute extensamente la diferencia entre llamada por nombre y llamada por valor. Una parte crítica del argumento es que para hacer una distinción adecuada, podemos transformar un programa en estilo de continuación de paso. La transformación de CPS es diferente para llamada por necesidad y llamada por valor, pero los términos transformados resultantes se pueden evaluar en cualquier estilo.
Aquí viene el argumento: escriba un programa lambda-calculus que simula una máquina de Turing, luego CPS lo transforma usando la transformación CBN, y puede evaluar el código resultante usando una estrategia de reducción de CBV. ¡Explosión! Turing-completo.
En la práctica, apuesto a que puede escribir un programa CBV para emular una máquina de Turing; probablemente sea suficiente para elegir un combinador de punto fijo adecuado, como Θ por ejemplo. (El más famoso combinador Y funciona sólo bajo una estrategia de reducción de llamada por nombre, es decir, reducción de orden normal.)
responsabilidad: No he estudiado cálculo lambda en mucho tiempo, y estoy seguro de que hay hay varios detalles incorrectos en el argumento anterior. Pero estoy seguro de la sustancia. No sería la primera vez que descubrí algo descaradamente mal en los recursos en línea sobre la teoría del lenguaje de programación.
Su pregunta no tiene mucho sentido sin hacer referencia a un lenguaje específico, pero haré todo lo posible para responder con respecto al cálculo de Urantped Lambda.
La existencia de un combinador de punto fijo llamado por valor (es decir, "combinador Y") para el cálculo lambda sin tipo parece refutar la afirmación básica (ver: Fixed Point Combinator). La existencia de un combinador de este tipo rompe una fuerte normalización, lo que sugiere que hay al menos un lenguaje que está completo y que utiliza una estrategia de evaluación llamada por valor.
Es mucho más probable que afecte a la integridad total de un idioma la existencia (o la falta de) un sistema de tipo. Por ejemplo, el cálculo lambda simplemente tipado no puede codificar un combinador de punto fijo, y está fuertemente normalizado (es decir, todos los términos bien tipados se reducen a un valor), sin embargo, esto es cierto independientemente de la estrategia de evaluación empleada. Más bien, es una consecuencia del sistema de tipos.
¿Qué artículo? _ – kennytm
@KennyTM: Estoy tratando de encontrar la fuente en las referencias al final del artículo. Puedo darle un enlace si lo desea, pero está en ruso. – Roman
Un artículo en ruso es mejor que nada. Yo no, pero alguien puede leer ruso. – kennytm