Supongamos que tenemos la propiedad P que dice si una funcion F esta definida para 1. (no es trivial pues hay funciones parciales no definidas para 1). Ahora tomemos el problema de deicidir si para cualquier algoritmo, este define la propiedad P, i.e. si el algoritmo termina cuando recibe 1 como entrada.
Por el teorema de Rice sabemos que es indecidible....
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment