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 bru...@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 bru...@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
pgpzlcDb26NDP.pgp
Description: PGP signature
