Turing-undecidable languages (OT)

["Chad R. Meiners" <crmeiners@hotmail.com>]

<tmoran@acm.org> wrote in message
news:7mWB8.6827$0z6.115522658@newssvr21.news.prodigy.com...
>   If someone says "I'll write a program to do such and such", how should
> he act differently if told:
> a) that's recursively undecidable
> or
> b) your program may get stuck in an infinite loop

This is an excellent question.  First, let's rephrase your question to:

If some says, "I'll am going to write a program Y that solves problem X",
how should he act if told

a) X is not recursive.  (This is the same as Robert's recursively
undecidable)
b) Program Y may get stuck in an infinite loop.

In case a, Y cannot exist.
Case b depends solely on what you meant by "may get stuck in an infinite
loop".  In fact the pragmatics of b can either be X is recursive or X is not
recursive.  So the only thing the programmer can do if told b is ask for
clarification.

-CRM