# Re: Objects and Relations

From: Marshall <marshall.spight_at_gmail.com>
Date: 1 Feb 2007 11:11:43 -0800

On Feb 1, 9:55 am, "David BL" <davi..._at_iinet.net.au> wrote:
> On Feb 1, 4:16 pm, "Marshall" <marshall.spi..._at_gmail.com> wrote:
>
>
> > I don't quite follow this question. As someone who is used to general
> > purpose programming languages, FOL occasionally feels weak to
> > me.
>
> Check out
>
> http://en.wikipedia.org/wiki/First_order_logic
>
> FOL allows you to express things like Fermat's last theorem, only
> proven true in 1994. Isn't FOL too rich to be regarded as a
> computational model?

Turing completeness represents an upper bound on what is computable. FOL is not Turing complete.

> RA seems much simpler than FOL. I think of it as "arithmetic" with
> (extensional) relations.

It's my weak understanding that there is at least some version of RA that is isomorphic to FOL.

> It seems to me that the join operator doesn't give you a group because
> given relations b,c there is no uniquely defined relation a
> satisfying a |X| b = c. This makes RA more like arithmetic than
> algebra (as a high school student would understand those terms).

I guess. I don't understand what the significance would be, though.

> > > BTW is support for aggregation technically a part of RA or not?
>
> > Mumble. I have no idea what the conventional view is, however
> > we lately have heard from Vadim a demonstration that aggregation
> > is the inverse operation of join, so these days I'd have to say yes.
>
> I'm curious to know how that relates to my comment above.

I don't believe this is a single monolithic entity that is RA. There are many algebras of relations.

However if we have an algebra that includes an operation op, I would expect to include op-1, the inverse operation, in that algebra as well. (Maybe I'm wrong, though; I remain unclean on what *exactly* constitutes an algebra.)

Since aggregation is the inverse operation of join, I would therefore expect to include aggregation in any algebra that included join. So I am saying: aggregation is part of RA.

> > > When we build all sorts of crazy, complicated RA expressions to
> > > perform string processing, can we really expect an optimizer to
> > > generate decent code? Are you saying all the theory currently exists?
>
> > Again I have to specifically disclaim any significant knowledge of
> > query optimizers; it is just not my field. However as I understand
> > it (which is weakly) yes, the theory does currently exist, for a lot
> > of it anyway.
>
> > In general, though, someone who knows exactly what they
> > are doing, and who is building a special-purpose engine, given
> > a tool such as C++, will be able to build something that is
> > better *for that special purpose* than a general-purpose
> > solution will likely be. That difference may only be O(c)
> > though.
>
> The halting problem suggests that the space of all algorithms is too
> much for a compiler to cope with. However I wonder whether that is
> true when we restrict ourselves to useful algorithms. I can imagine
> a compiler being smarter than your average programmer and that may be
> enough. Who knows how clever compilers will be in 100 years time. We
> may be like carrots by comparison.

Heh.

> A particularly interesting question for me is whether computers can
> (in principle) be conscious.

I don't see any reason why not.

I have heard a million arguments on either side of this issue, and the one that impressed me the most goes like this:

If consciousness can be instantiated in three pounds of   fatty meat, there is no reason to believe it cannot be instantiated   in other media as well.

Marshall Received on Thu Feb 01 2007 - 20:11:43 CET

Original text of this message