On the Turing completeness of the Semantic Web

Pourabdollah, A ORCID: https://orcid.org/0000-0001-7737-1393 and Brailsford, T, 2015. On the Turing completeness of the Semantic Web. Theory of Computing Systems, 56 (2), pp. 291-308. ISSN 1432-4350

Preview

Text PubSub10619_Pourabdollah.pdf - Post-print Download (886kB) | Preview

Abstract

The evidenced fact that “Linking is as powerful as computing” in a dynamic web context has lead to evaluating Turing completeness for hypertext systems based on their linking model. The same evaluation can be applied to the Semantic Web domain too. RDF is the default data model of the Semantic Web links, so the evaluation comes back to whether or not RDF can support the required computational power at the linking level. RDF represents semantic relationships with explicitly naming the participating triples, however the enumeration is only one method amongst many for representing relations, and not always the most efficient or viable. In this paper we firstly consider that Turing completeness of binary-linked hypertext is realized if and only if the links are dynamic (functional). Ashman’s Binary Relation Model (BRM) showed that binary relations can most usefully be represented with Mili’s pE (predicate-expression) representation, and Moreau and Hall concluded that hypertext systems which use the pE representation as the basis for their linking (relation) activities are Turing-complete. Secondly we consider that RDF –as it is- is a static version of a general ternary relations model, called TRM. We then conclude that the current computing power of the Semantic Web depends on the dynamicity supported by its underlying TRM. The value of this is firstly that RDF’s triples can be considered within a framework and compared to alternatives, such as the TRM version of pE, designated pfE (predicate-function-expression). Secondly, that a system whose relations are represented with pfE is likewise going to be Turing-complete. Thus moving from RDF to a pfE representation of relations would give far greater power and flexibility within the Semantic Web applications.

Item Type:	Journal article
Publication Title:	Theory of Computing Systems
Creators:	Pourabdollah, A. and Brailsford, T.
Publisher:	Springer Science+Business Media
Date:	February 2015
Volume:	56
Number:	2
ISSN:	1432-4350
Identifiers:	Number Type 10.1007/s00224-014-9536-x DOI
Divisions:	Schools > School of Science and Technology
Record created by:	Jill Tomkinson
Date Added:	26 Mar 2018 11:37
Last Modified:	26 Mar 2018 11:37
URI:	https://irep.ntu.ac.uk/id/eprint/33088

Actions (login required)

Edit View

Statistics

Views

Downloads