Tools
Tools
Pourabdollah, A. 
ORCID: 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
|
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: |
|
||||
| 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 |
Views
Views per month over past year
Downloads
Downloads per month over past year
