Interval-valued computation

Interval-valued computation

"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: [Nagy & Vályi 2007: 14] 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. [Tajti & Nagy 2008] “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). [Nagy & Vályi 2008]

Notes

References

* cite conference |last=Nagy |first=Benedek |coauthors=Vályi, Sándor |title=Visual reasoning by generalized interval-values and interval temporal logic |pages=13–26 |booktitle=VLL |conference=Proceedings of the VLL 2007 workshop on Visual Languages and Logic |editor=Philip T. Cox & Andrew Fish & John Howse |publisher=CEUR Workshop Proceedings |location=Coeur d'Aléne, Idaho, USA |date=23 September 2007 |format=PDF |url=http://ftp.informatik.rwth-aachen.de/Publications/CEUR-WS/Vol-274/paper2.pdf
* cite journal |last=Nagy |first=Benedek |coauthors=Vályi, Sándor |title=Interval-valued computations and their connection with PSPACE |journal=Theoretical Computer Science (Preface: From Gödel to Einstein: Computability between Logic and Physics) |volume=394 |issue=3 |pages=208–222 |date=April 8, 2008 |url=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
* cite conference |last=Tajti |first=Ákos |coauthors=Nagy, Benedek |title=Solving Tripartite Matching by Interval-valued Computation in Polynomial Time |conference=Computability in Europe 2008. Logic and Theory of Algorithms |conferenceurl=http://www.cs.swan.ac.uk/cie08/ |date=June 20, 2008 |pages=208–222 See short [http://www.cs.swan.ac.uk/cie08/giveabs.php?54 abstract] .

External links

* cite conference |last=Nagy |first=Benedek |coauthors=Vályi, Sándor |title=Visual reasoning by generalized interval-values and interval temporal logic |pages=13–26 |booktitle=VLL |conference=Proceedings of the VLL 2007 workshop on Visual Languages and Logic |editor=Philip T. Cox & Andrew Fish & John Howse |publisher=CEUR Workshop Proceedings |location=Coeur d'Aléne, Idaho, USA |date=23 September 2007 |format=PDF |url=http://ftp.informatik.rwth-aachen.de/Publications/CEUR-WS/Vol-274/paper2.pdf


Wikimedia Foundation. 2010.

Игры ⚽ Поможем сделать НИР

Look at other dictionaries:

  • Interval arithmetic — Interval arithmetic, also called interval mathematics , interval analysis , and interval computation , is a method in mathematics. It has been developed by mathematicians since the 1950s and 1960s as an approach to putting bounds on rounding… …   Wikipedia

  • Many-valued logic — In logic, a many valued logic (also multi or multiple valued logic) is a propositional calculus in which there are more than two truth values. Traditionally, in Aristotle s logical calculus, there were only two possible values (i.e., true and… …   Wikipedia

  • Integral — This article is about the concept of integrals in calculus. For the set of numbers, see integer. For other uses, see Integral (disambiguation). A definite integral of a function can be represented as the signed area of the region bounded by its… …   Wikipedia

  • Exponentiation — Exponent redirects here. For other uses, see Exponent (disambiguation). Exponentiation is a mathematical operation, written as an, involving two numbers, the base a and the exponent (or power) n. When n is a positive integer, exponentiation… …   Wikipedia

  • Non-standard calculus — Abraham Robinson Contents 1 Motivation …   Wikipedia

  • Logarithm — The graph of the logarithm to base 2 crosses the x axis (horizontal axis) at 1 and passes through the points with coordinates (2, 1), (4, 2), and (8, 3) …   Wikipedia

  • Normal distribution — This article is about the univariate normal distribution. For normally distributed vectors, see Multivariate normal distribution. Probability density function The red line is the standard normal distribution Cumulative distribution function …   Wikipedia

  • Argument (complex analysis) — Arg (mathematics) redirects here. For argument of a function, see Argument of a function. Figure 1. This Argand diagram represents the complex numbers lying on a plane. For each point on the plane, arg is the function which returns the angle φ.… …   Wikipedia

  • List of mathematics articles (I) — NOTOC Ia IA automorphism ICER Icosagon Icosahedral 120 cell Icosahedral prism Icosahedral symmetry Icosahedron Icosian Calculus Icosian game Icosidodecadodecahedron Icosidodecahedron Icositetrachoric honeycomb Icositruncated dodecadodecahedron… …   Wikipedia

  • probability theory — Math., Statistics. the theory of analyzing and making statements concerning the probability of the occurrence of uncertain events. Cf. probability (def. 4). [1830 40] * * * Branch of mathematics that deals with analysis of random events.… …   Universalium

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”