Re: Turing-undecidable languages (OT)

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

"Danx" <chris.danx@ntlworld.com> wrote in message
news:da2da981.0205080024.6576be16@posting.google.com...
> "Chad R. Meiners" <crmeiners@hotmail.com> wrote in message
news:<ab9fmh$2qh1$1@msunews.cl.msu.edu>...
> Does that mean that if any problem cannot be expressed recursively,
> then no program can be coded to solve it?  In other words, any problem
> that can be solved without recursion, can also be expressed using
> recursion and any problem that cannot be solved by recursion cannot be
> solved by a computer?

Recursive refers to a set of languages. When we say x is recursive, we mean
x in is the set of recursive languages.  This is why I prefer the term
Turing-decidable.  As to the above question, we must be careful with phrases
"cannot be solved by recursion" because they are vague.  Context free
grammars are recursively defined yet they are less powerful then Turing
Machines, but I guess the best general answer is that Turing Machines can
simulate arbitrary recursion and nonrecursive algorithms can be thought as a
subset of recursive algorithms.  So given that explanation, you can solve X
with recursion if and only if you can solve X with a Turing Machine.