Hello, Is it possible to implement in haskell a function f (A) such that if A does not ever terminate then f always terminates, and if A always terminates then f does not ever terminate? I've been thinking it for a while, with no results unfortunately. the actual problem is that i can think of no way to force both ifs: a function that always terminates independently from its argument could be f (a) = 1, and a function that does not terminate even if its argument terminates could be: f (a) = f (a + 1), but i can't figure out a "hybrid" version... Is there any idea on this? Thanks in advance :-), yannis
Is it possible to implement in haskell a function f (A) such that if A does not ever terminate then f always terminates, and if A always terminates then f does not ever terminate?
Is the argument A itself another function? If so, such a function does not exist. See http://en.wikipedia.org/wiki/Halting_problem for more details. Rahul
2009/9/2 Γιάννης Μαντζουράτος
Hello,
Is it possible to implement in haskell a function f (A) such that if A does not ever terminate then f always terminates, and if A always terminates then f does not ever terminate? I've been thinking it for a while, with no results unfortunately. the actual problem is that i can think of no way to force both ifs: a function that always terminates independently from its argument could be f (a) = 1, and a function that does not terminate even if its argument terminates could be: f (a) = f (a + 1), but i can't figure out a "hybrid" version... Is there any idea on this?
Thanks in advance :-),
Isn't this the halting problem? /M -- Magnus Therning (OpenPGP: 0xAB4DFBA4) magnus＠therning．org Jabber: magnus＠therning．org http://therning.org/magnus identi.ca|twitter: magthe
2009/9/2 Magnus Therning
Is it possible to implement in haskell a function f (A) such that if A does not ever terminate then f always terminates, and if A always terminates then f does not ever terminate?
Thanks in advance :-),
Isn't this the halting problem?
It is, since to ensure that f terminates and evaluates to a given value for every A that do not terminate it must be able to determine that it don't terminate in finite time, thus solving the halting problem. In other words this can't be written in Haskell and a fortiori can't be written on a computer in any language. -- Jedaï
participants (4)
-
Chaddaï Fouché -
Magnus Therning -
Rahul Kapoor -
Γιάννης Μαντζουράτος