Re: deductive databases
Date: 18 May 2005 20:30:20 GMT
Message-ID: <slrnd8n9hs.uu.cmenzel_at_philebus.tamu.edu>
On 18 May 2005 13:17:31 -0700, mikharakiri_nospaum_at_yahoo.com said:
>
> 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?
Well, solvability and expressive power are two quite different things. There are many that discuss the differences, expressive and otherwise, between first-order and second-order logic/arithmetic. Google the obvious keywords.
Chris Menzel Received on Wed May 18 2005 - 22:30:20 CEST