No. Cualquier combinador de punto fijo, bueno, implementa puntos fijos y, por lo tanto, puede producir los términos lambda definidos recursivamente que desee.
Si desea algún término [matemática] T [/ matemática] tal que [matemática] T = e [/ matemática], donde [matemática] e [/ matemática] es alguna expresión que posiblemente se refiera a [matemática] T [/ matemática], entonces lo que quiere es, por definición, un punto fijo de la función [math] \ lambda Te [/ math].
Y si desea un punto fijo de una función [matemática] f [/ matemática], bueno, [matemática] U f [/ matemática] para cualquier combinador de punto fijo [matemática] U [/ matemática] hará el trabajo, por La definición de lo que es ser un combinador de punto fijo.
- ¿Cómo va NP-hard dentro de NP-complete? Si encontramos un algoritmo no determinista para NP-hard, ¿sería un NP-complete?
- ¿Por qué la gente encuentra divertida la programación / codificación, pero no las matemáticas?
- ¿Cuáles son algunos procesos que realizamos con computadoras que no se encuentran bajo el formalismo de la máquina de Turing?
- ¿Cuál es el significado del teorema de Valiant?
- Si el universo es una simulación, ¿no estaría sujeto al problema de detención?
¿En qué sentido dice que el combinador [matemático] \ Theta [/ matemático] de Turing es más poderoso que el combinador Y?
Podríamos hablar más estrictamente sobre “puntos reducidos”, llamando a [matemáticas] T [/ matemáticas] un punto reducido de [matemáticas] f [/ matemáticas] si [matemáticas] T [/ matemáticas] de hecho beta-reduce a [matemáticas] f (T) [/ math], en lugar de ser simplemente beta equivalente a [math] f (T) [/ math]. Por supuesto, cada punto reducido es un punto fijo, pero no al revés.
A veces se señala que [math] \ Theta [/ math] de Turing tiene la propiedad de que [math] \ Theta f [/ math] no es solo un punto fijo de [math] f [/ math] sino que de hecho es un ” punto reducido “de [matemáticas] f [/ matemáticas], mientras que [matemáticas] Y f [/ matemáticas] en realidad no es un punto reducido de [matemáticas] f [/ matemáticas] (sin embargo, [matemáticas] Y f [/ matemáticas] se reduce a un punto reducido de [matemáticas] f [/ matemáticas]; la propiedad de ser un punto reducido simplemente no respeta la equivalencia beta de los términos). Pero no describiría esto como [math] \ Theta [/ math] siendo “más poderoso” un combinador de punto fijo que [math] Y [/ math].
Tenga en cuenta que la propiedad de ser un combinador de punto fijo es esencialmente la propiedad de satisfacer una determinada ecuación recursiva; [math] U [/ math] es un combinador de punto fijo solo en caso de que [math] U [/ math] sea extensionalmente equivalente a [math] \ lambda ff (U f) [/ math] (y if [math] U [ / math] de hecho se reduce a [math] \ lambda ff (U f) [/ math], entonces es además un combinador de “punto reducido”). Y, de hecho, el [matemático] \ Theta [/ matemático] de Turing es precisamente lo que obtendría al usar el combinador [matemático] Y [/ matemático] para resolver esa ecuación recursiva. Por lo tanto, cualquier cosa que pueda obtener a través de [math] \ Theta [/ math] de Turing puede considerarse como derivada en última instancia del combinador [math] Y [/ math] de todos modos.
[También es cierto que ni los [math] Y [/ math] ni los [math] \ Theta [/ math] combinadores como se presentan aquí terminarán en una entrada bajo una estrategia de evaluación de llamada por valor, mientras que otro punto fijo los combinadores pueden (básicamente, tomar cualquier combinador de punto fijo [matemática] U [/ matemática] y eta-expandirla a [matemática] \ lambda f. \ lambda x. (U f) x [/ matemática] para formar un combinador de punto fijo que puede interpretar definiciones recursivas de funciones en un contexto de llamada por valor). Una vez más, sin embargo, no describiría esto como una cuestión de que el resultado sea un combinador de punto fijo “más poderoso”; solo uno más susceptible a una estrategia de evaluación particular]
