Re: LBA completeness of SPARQL

hi all,

maybe the point is that if a real Turing machine (with infinite tape and time)
runs a SPARQL engine, you cannot emulate a real Turing machine using the
SPARQL engine because you have to choose a limit for tape or time first?

Regards,

Michael Brunnbauer

On Tue, Nov 18, 2014 at 11:40:41AM +0100, Michael Brunnbauer wrote:
> 
> hi all,
> 
> has the question if SPARQL is linear bounded automaton complete (or Turing
> complete in the colloquial sense) been settled? I am a bit confused about
> the fine points. How about this:
> 
> http://www.brunni.de/sparql_abuse.html#turing
> 
> > By putting a limit on the tape size, we can emulate a Turing machine with one SPARQL UPDATE query followed by one normal SPARQL query - in a quite impractical way. The basic idea is to generate all possible state transitions and then to search through them with property paths.
> [...]
> > If the first SPARQL UPDATE query generates all state transitions for a universal linear bounded automaton (a Turing machine with finite tape emulating a Turing machine described on its tape), you can execute any program that fits into the tape just by doing the second query.
> >
> > This does not seem to be feasible with modern hardware (e.G. a tape size of 40 bits for the universal Turing machine) and even if it were, the calculations enabled by this would only be able to manipulate a handful of bits. 
> 
> A friend says this is cheating because it combines impractically big resources
> for the SPARQL engine (at least in the universal case) with impractically small
> computations enabled by it.
> 
> Also, the exact wording maybe has to be that 
> 
> 1) the combination of two queries
> 
> or
> 
> 2) one query and a (hypothetical) endpoint with the pre-generated state
>    transitions for the universal case
>  
> are linear bounded automaton complete.
> 
> There seems to be another option for emulation of a Turing machine: Put a 
> limit N on the number of computation steps and construct a query with at least
> N nested subselects using operators like IF().
> 
> Would this constitute 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



-- 
++  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