Re: deductive databases

From: <mikharakiri_nospaum_at_yahoo.com>
Date: 18 May 2005 13:17:31 -0700
Message-ID: <1116447451.925075.69070@g14g2000cwa.googlegroups.com>

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? Received on Wed May 18 2005 - 15:17:31 CDT