Re: LBA completeness of SPARQL

hi all,

hm... I should read the whole Wikipedia-article before throwing around its 
title in a discussion.

The input length of a linear bounded automaton does not seem to be
restricted. Only the length of tape during computation is restricted to a 
linear function of the input length.

The Wikipedia article about Turing completeness says that real computers
are linear bounded automaton complete. This seems to be false, then.

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