function - argument termination problem

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
4 messages Options
Reply | Threaded
Open this post in threaded view
|

function - argument termination problem

Γιάννης Μαντζουράτος
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
Reply | Threaded
Open this post in threaded view
|

function - argument termination problem

Rahul Kapoor
> 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
Reply | Threaded
Open this post in threaded view
|

function - argument termination problem

Magnus Therning
In reply to this post by Γιάννης Μαντζουράτος
2009/9/2 ??????? ???????????? <[hidden email]>:

> 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
Reply | Threaded
Open this post in threaded view
|

function - argument termination problem

Chaddaï Fouché
2009/9/2 Magnus Therning <[hidden email]>:
>> 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?