mikharakiri_nospaum_at_yahoo.com wrote:
> Chris Menzel wrote:
>>On 18 May 2005 12:23:53 -0700, Mikito Harakiri <mikharakiri_nospaum_at_yahoo.com> said:
>>>Chris Menzel wrote:
>>>
>>>>I'm confused by the talk of computation here, but, in the model
>>>>theoretic sense of "expressive power", the TC of a graph is not
>>>>expressible in first-order logic with or without function symbols.
>>>
>>>TC is surely expressible in arithmetics (or less slopily Peano
>>>Arithmetics), right?
>>
>>Second-order PA, yes (presumably in conjunction with some basic graph
>>theoretic apparatus), first-order, no.
>
> Is there a list of problems that are solvable in first order PA? Can I
> solve [systems of] linear equations, for example?
No. You can *express* them, but you cannot *solve* them in the sense
that can "solve" first order queries on a given database by executing
them as SQL (I assume that is how you meant it). In this logic you can
actually formulate undecidable queries.
Received on Wed May 18 2005 - 18:12:56 CDT
