Probar una función es un punto fijo

Question

Estoy tomando una clase en la Universidad que implica que demuestra la corrección de los programas de ordenador y estoy muy mal que una de las pruebas, no lo entiendo en absoluto.

¿Alguien puede decirme si mi prueba de realidad tiene sentido, con frecuencia tengo he escrito una prueba, pero por lo general me ha demostrado nada.

Dada esta (T1 es una función que toma a otra función (F) como uno de sus parámetros):

T1(F,x,y) == if y = 0 then x else F(x−1,y−1)

Tuve que sugieren un punto fijo de la solución, me sugirió:

f1(x,y) == x - y

Debido a que T1 es una función recursiva que implementa la resta. Y a continuación tuve que demostrar mi sugerencia fue la correcta.

To show T1(f1) = f1

T1(f1, x, y) == if y = 0 then x else f1(x−1,y−1)

if y = 0 then x
else (x-1) - (y-1)

if y = 0 then x
else x - y - 2

x - y - 2 = f1(x-1,y-1)

x - y = f1(x,y)

¿Mi prueba tiene algunas obvio agujero en lo que no estoy viendo o hay algún error que no puedo ver, creo que funciona, pero no estoy realmente seguro de por qué se demuestra algo?

Answer 1

Estás pensando en el mapa: $$T_1(f,x,y) =\begin{cases} x & \text{if } y=0 \\f(x-1,y-1) & \text{otherwise} \end{casos}, $$ y quiero mostrar que la función $$ f(x,y)=x-y $$ es un punto fijo. Esto equivale a mostrar $$ T_1(f,x,y)=f(x,y)=x-y\ $$ para cualquier $x$ e $y$.

Sólo hay dos casos uno tiene que comprobar, $y=0$ e $y\neq 0$. Si $y=0$, a continuación, $T_1(f,x,0)=x=x-0=f(x,0)$, tal y como la queremos. Si $y\neq 0$, a continuación, $T_1(f,x,y)=f(x-1,y-1)=x-1-y+1=x-y=f(x,y)$, y la prueba está hecho.

No entiendo la programación de la notación que se usa, pero creo que esto es lo que están tratando de hacer. Sin embargo se han evaluado $f(x-1,y-1)$ a $x-y+2$ en lugar de $x-1-y+1=x-y$, posiblemente usted ha olvidado a distribuir el signo menos. Espero que esto ayude!

Answer 2

Su idea es correcta, pero en la forma en que está escrito, yo no lo reconocen como una prueba. Quiere mostrar que $T_1(f_1,x,y)=f_1(x,y)$ para todos los $x$ e $y$ en lo que sea de su dominio. A fin de comenzar con $x$ e $y$, distinguir los casos de $y=0$ e $y\neq0$, y, a continuación, muestran que en ambos casos $T_1(f_1,x,y)=f_1(x,y)$.