From: Miguel <miguel.ceriani@gmail.com>

Date: Tue, 18 Nov 2014 16:20:00 +0100

Message-ID: <CALWU=RtjnL4MRFHwHyTLtmvxkqsTxe9z_MjjDi8HLCEx7u_G2g@mail.gmail.com>

To: Michael Brunnbauer <brunni@netestate.de>

Cc: "public-sparql-dev@w3.org" <public-sparql-dev@w3.org>

Date: Tue, 18 Nov 2014 16:20:00 +0100

Message-ID: <CALWU=RtjnL4MRFHwHyTLtmvxkqsTxe9z_MjjDi8HLCEx7u_G2g@mail.gmail.com>

To: Michael Brunnbauer <brunni@netestate.de>

Cc: "public-sparql-dev@w3.org" <public-sparql-dev@w3.org>

Hi Michael and all, I've been thinking a bit at it, cause it is related to my work. While I was writing the email I've seen you clarified that you were emulating a generic fixed tape-size Turing machine and not a generic linear (space-)bound Turing machine. So basically you are talking about constant (space-)bound Turing machines, that have the same expressive power of finite state automata. But as I have got inspired about the possibility of emulating (space-)bound Turing machines, I am sharing my thoughts on the topic to whoever may be interested. Many people proposed systems with SPARQL CONSTRUCT views that could be cascaded to intensionally define new RDF "virtual" graphs. Other systems, among them the one I work on, use pipelines of queries in a similar fashion. So, it seems interesting to me to discuss the expressiveness of a finite sequence of SPARQL queries. To the purpose of expressiveness, the problem of considering a set of SPARQL CONSTRUCT views (possibly defined one over another, but non-recursive) or a sequence of SPARQL update operations on a graph store should be the same. To emulate a (space-)bounded Turing machine you need in general to build all the configurations, that are exponential on the space bound. So, to emulate any linear (space-)bounded Turing machine you would need to generate a number of configurations exponential in respect to the input. To the best of my knowledge, the output triples of any SPARQL query have cardinality at most polynomial respect to the input triples. So I don't think any finite sequence of SPARQL queries can generate an exponential number of configurations and thus emulate a generic linear (space-)bounded Turing machine. I think it could be possible instead to emulate any (poly?-)log-space-bounded Turing machine (to have a space bound smaller than the input size the input tape is considered "read-only", while there is another smaller read-write tape). 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. 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. A way (among other possible extensions) to achieve full Turing-completeness with SPARQL is finally through the definition of recursive SPARQL views. Best Regards, Miguel Ceriani On Nov 18, 2014, at 11:40 AM, Michael Brunnbauer <brunni@netestate.de> 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 HendelReceived on Tuesday, 18 November 2014 15:20:51 UTC

*
This archive was generated by hypermail 2.3.1
: Tuesday, 6 January 2015 20:15:52 UTC
*