Skip to main content

Research Repository

Advanced Search

On the Turing Completeness of the Semantic Web

Pourabdollah, Amir; Brailsford, Tim


Amir Pourabdollah


© 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.


Pourabdollah, A., & Brailsford, T. (2014). On the Turing Completeness of the Semantic Web. Theory of Computing Systems, 56(2), 291-308.

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
Keywords relations, model, RDF, hypertext, semantic web
Public URL
Publisher URL