Interval-valued computation
From Wikipedia, the free encyclopedia
 |
This article is an orphan, as few or no other articles link to it. Please introduce links to this page from other articles related to it. (February 2009) |
Interval-valued computation is a special kind of theoretical models for computation. It is capable of working on “interval-valued bytes”: special subsets of the unit interval. If such computers were realized, their computation power would be much greater than that of functioning, "implementable" computers. As such, there are no architectures for their physical implementations.
Only special subsets of the unit interval are considered, the restrictions are of finite nature, causing that the computation power of this paradigm fits into the framework of Church-Turing thesis:[1] unlike real computation, interval-valued computation is not capable of hypercomputation, is not corresponding to an unrestricted ideal analog computer.
Such a model of computation is capable of solving NP-complete problems like tripartite matching.[2] “The validity problem of quantified propositional formulae is decidable by a linear interval-valued computation. As a consequence, all polynomial space problems are decidable by a polynomial interval-valued computation. Furthermore, it is proven that PSPACE coincides with the class of languages which are decidable by a restricted polynomial interval-valued computation” (links added).[3]
[edit] Notes
[edit] References
- Nagy, Benedek; Vályi, Sándor (23 September 2007). "Visual reasoning by generalized interval-values and interval temporal logic" (PDF) in Proceedings of the VLL 2007 workshop on Visual Languages and Logic. Philip T. Cox & Andrew Fish & John Howse VLL: 13–26, Coeur d'Aléne, Idaho, USA: CEUR Workshop Proceedings.
- Nagy, Benedek; Vályi, Sándor (April 8, 2008). "Interval-valued computations and their connection with PSPACE". Theoretical Computer Science (Preface: From Gödel to Einstein: Computability between Logic and Physics) 394 (3): 208–222. http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6V1G-4RDS46X-2&_user=10&_rdoc=1&_fmt=&_orig=search&_sort=d&view=c&_acct=C000050221&_version=1&_urlVersion=0&_userid=10&md5=88688a8f0efc70b7e0f2e882a29ec29c.
- Tajti, Ákos; Nagy, Benedek (June 20, 2008). "Solving Tripartite Matching by Interval-valued Computation in Polynomial Time" in Computability in Europe 2008. Logic and Theory of Algorithms.: 208–222. See short abstract or the full article.
[edit] External links
- Nagy, Benedek; Vályi, Sándor (23 September 2007). "Visual reasoning by generalized interval-values and interval temporal logic" (PDF) in Proceedings of the VLL 2007 workshop on Visual Languages and Logic. Philip T. Cox & Andrew Fish & John Howse VLL: 13–26, Coeur d'Aléne, Idaho, USA: CEUR Workshop Proceedings.
 |
This computer science article is a stub. You can help Wikipedia by expanding it. |
