Re: LBA completeness of SPARQL

Hello Miguel,

On Tue, Nov 18, 2014 at 04:20:00PM +0100, Miguel wrote:
> To emulate a (space-)bounded Turing machine you need in general to build
> all the configurations, that are exponential on the space bound.

And emulating a time-bounded Turing machine just requires a query linear in
size to the time limit? Simulating N steps requires N nested subselects.

> Another possible view on the topic is allowing SPARQL to generate other
> SPARQL queries (using an RDF serialization as SPIN SPARQL) that are can be
> then executed.

I think it may be possible to generate the query consisting of N nested 
subselects mentioned above literally with a first query using joins on VALUES
and GROUP_CONCAT. 

> A SPARQL query should be able to generate your first query from any input
> (the length of the query itself is linear in respect to the input size).
> So in this scenario you could in fact emulate any linear (space-)bounded
> Turing machine with three queries.

Ah! Nice! :-)

> A way (among other possible extensions) to achieve full Turing-completeness
> with SPARQL is finally through the definition of recursive SPARQL views.

If all sorts of extra stuff is allowed, how about my idea on using side
effects in query federation? http://brunni.de/sparql_abuse.html

So are these statements correct?

-SPARQL is not Turing-complete

-My examples for emulation (generate all state transitions or use nested
 subselects and limit number of steps) do not show that is is Turing-complete
 because a SPARQL engine running on a real Turing machine would still not be
 able to emulate a real Turing machine. This is in turn because you have to
 select a space/time-limit before you start the emulation.

-Whether an emulation has a constant, linear or exponential amount of overhead
 is not relevant for Turing-completeness or linear bounded automaton
 completeness.

Regards,

Michael Brunnbauer

-- 
++  Michael Brunnbauer
++  netEstate GmbH
++  Geisenhausener Straße 11a
++  81379 München
++  Tel +49 89 32 19 77 80
++  Fax +49 89 32 19 77 89 
++  E-Mail brunni@netestate.de
++  http://www.netestate.de/
++
++  Sitz: München, HRB Nr.142452 (Handelsregister B München)
++  USt-IdNr. DE221033342
++  Geschäftsführer: Michael Brunnbauer, Franz Brunnbauer
++  Prokurist: Dipl. Kfm. (Univ.) Markus Hendel