Re: Pequeño simpático ejercicio

Hola,
quería decilerles que este thread se estaba poniendo cada vez mejor,
en especial la 2da parte.
¿Cómo sigue entonces Dani?

2009/9/3 Marcelo Caro <marcecaro@...>:
> Todavía no tengo una respuesta al desafío concreto, si buscamos algo
> estrictamente formal, creo que lo mejor seria usar ternas de hoare,  voy a
> tener que repasar algunos apuntes :)
>
> Respecto a:
>
>>La respuesta genérica ideal a esta pregunta sería un algoritmo que reciba
>> como input dos algoritmos. (y que analice adentro, >no que bombardee con
>> resultados).
>
> Me parece que tal algoritmo no es computable.
>
> Una demostración sencilla es comparar un algoritmo con HALT (un algoritmo
> que no termina), si nuestro comparador dice que algo es equivalente a HALT,
> estariamos ante un algoritmo que predice si algo termina o no, y esto es
> absurdo (prueba por el absurdo).
>
> Bueno espero no estar errado, hace tanto que no me topo con un problema de
> computabilidad en la vida real jejeje
>
>
>
>
>
>
> 2009/9/3 Daniel Gutson <danielgutson@...>
>>
>> Ok ok ok.
>> Cerremos esto para pasar a la segunda parte.
>> SÍ, son equivalentes, en el sentido que para todo par de valores de i,j el
>> resultado coincide. No tiene sentido plantear otra equivalencia que no sea
>> la semántica. Cantidad de loops, no cuenta.
>> Pero el hecho de que sean equivalentes semánticamente, como pudieron
>> oCservar, no fue trivial. (es determinante el hecho de que las operaciones
>> aritméticas NO CAMBIAN los flags de condición, de hecho ese es el chiste,
>> poder hacer una comparación y luego operar selectivamente; en general este
>> comportamiento es de todas las arquitecturas: salvo instrucciones
>> particulares (con sufijos especiales), la manera de modificar los condition
>> flags es con comparaciones, no por resultados aritméticos, osea la vieja y
>> conocida CMP).
>> Ahora bien, y esta es la segunda parte: cómo se podría hacer, para -de
>> alguna manera- "demostrar" la equivalencia entre estos dos programas
>> escritos en lenguajes diferentes? Hint: pueden considerar ideas de
>> test-coverage o white-box testing.
>> La respuesta genérica ideal a esta pregunta sería un algoritmo que reciba
>> como input dos algoritmos. (y que analice adentro, no que bombardee con
>> resultados). Pero aconsejo una respuesta particular a este problema, después
>> generalicemos. Demuéstrenme (usando lógica * ) que los dos programas son
>> equivalentes.
>>   Daniel.
>> * sugiero pensar en usar cosas como la ley de De Morgan.
>> 2009/9/3 Alfredo Ortega <ortegaalfredo@...>
>>>
>>> Tarde, pero voto por que si, si CMP setea los flags como dice el wiki.
>>>
>>> Esos flags que se les agregan a las instrucciones de ARM para evitar
>>> comparaciones adicionales son buenisimos. Debe ser por eso que
>>> patentaron el instruction set y no dejan que nadie se los clone.
>>>
>>> On Sep 3, 12:44 am, "Ing. Esteban D. Papp" <esteban.p...@...>
>>> wrote:
>>> > Son equivalentes, pero la optimización hace que haya una sóla
>>> > comparación en
>>> > lugar de las tres que se ven en C.También hace que en el último ciclo,
>>> > se de
>>> > una vuelta de más que en C no nos imaginaríamos que hace.
>>> >
>>> > salu2
>>> > estebanp
>>>
>>
>>
>>
>
>
>
> --
>           Marcelo
>
> >
>