Re: Turing-undecidable languages (OT)

[dewar@gnat.com (Robert Dewar)]

"Chad R. Meiners" <crmeiners@hotmail.com> wrote in message news:<abe7ir$2ktu$1@msunews.cl.msu.edu>...
> I tried to clarify Robert's statement and answer some other questions as
> they poped up.  But as far as attacking Tom's idea of randoming generating
> sorting algoritms with predefined time and space bounds, I would do no such
> thing because placing bounds on algorithms is one way to change the halting
> problem to make it decidable.

True, but a problem that is theoretically recursively
undecidable over infinite inputs is typically practically
unsolvable if the only bound is available memory, available disk space
etc. So appealing to this is not particularly
interesting in practice. Yes, of course we know that from
a theoretical point of view, any bounding of a problem
changes things completely.

For example, there are many problems that are NP complete,
but as soon as you limit the size, they are theoretically
trivial. For example, consider the problem of coloring
an N node graph on a RAM machine with unit time access to
memory. If you limit N to googol**googol, then there is
a trivial algorithm that yields whether the graph can be
colored with M colors (again limit M), by simple table 
lookup in unit time. But that is not particularly interesting and in
practice, coloring is still hard :-)