Re: deductive databases
From: Jan Hidders <jan.hidders_at_REMOVETHIS.pandora.be>
Date: Wed, 18 May 2005 23:12:56 GMT
Message-ID: <YZPie.94781$Xa1.5438591_at_phobos.telenet-ops.be>
>>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.
Date: Wed, 18 May 2005 23:12:56 GMT
Message-ID: <YZPie.94781$Xa1.5438591_at_phobos.telenet-ops.be>
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.
- Jan Hidders