On the Turing Completeness of the Semantic Web

Pourabdollah, Amir; Brailsford, Tim

Abstract

© 2014, Springer Science+Business Media New York. 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.

• Journal Article Type: Article
• Acceptance Date: Mar 8, 2014
• Online Publication Date: Mar 8, 2014
• Publication Date: Jan 1, 2014
• Deposit Date: Aug 14, 2018
• Journal: Theory of Computing Systems
• Print ISSN: 1432-4350
• Electronic ISSN: 1433-0490
• Publisher: Springer (part of Springer Nature)
• Peer Reviewed: Peer Reviewed
• Volume: 56
• Issue: 2
• Pages: 291-308
• DOI: https://doi.org/10.1007/s00224-014-9536-x
• Keywords: relations, model, RDF, hypertext, semantic web
• Public URL: https://uwe-repository.worktribe.com/output/838282
• Publisher URL: https://doi.org/10.1007/s00224-014-9536-x
• Contract Date: Aug 14, 2018