Circular Interval-valued Computers and Simulation of (Red-green) Turing Machines

• Autorzy: Nagy Benedek , Vályi Sándor

Identyfikatory

DOI

10.3233/FI-2021-2057

• Języki publikacji: EN

Abstrakty

EN

Interval-valued computing is a kind of massively parallel computing. It operates on specific subsets of the interval [0,1) – unions of subintervals. They serve as basic data units and are called interval-values. It was established in [9], by a rather simple observation, that interval-valued computing, as a digital computing model, has computing power equivalent to Turing machines. However, this equivalence involves an unlimited number of interval-valued variables. In [14], the equivalence with Turing machines is established using a simulation that uses only a fixed number of interval-valued variables and this number depends only on the number of states of the Turing machine – in a logarithmic way. The simulation given there allows us to extend interval-valued computations into infinite length to capture the computing power of red-green Turing machines. In this extension of [14], based on the quasi-periodic techniques used in the simulations in that paper, a reformulation of the interval-valued computations is given, named circular interval-valued computers. This reformulation enforces the finiteness of the number of used interval-valued variables by building the finiteness into the syntax rules.

Słowa kluczowe

EN

unconventional computing; massively parallel computing; interval-valued computing; red-green Turing machines; simulation; hypercomputation

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2021
• Tom: Vol. 181, nr 2-3
• Strony: 213--238
• Opis fizyczny: Bibliogr. 19 poz., rys., tab.

Twórcy

autor

Nagy Benedek

• Department of Mathematics, Eastern Mediterranean University, Famagusta, North Cyprus, via Mersin-10, Turkey

autor

Vályi Sándor

• Institute of Mathematics and Informatics, University of Nyíregyháza, Hungary

Bibliografia

• [1] Hajnal A, Németi I and Székely G. Closed Timelike Curves in Relativistic Computation. Parallel Process. Lett. 2012. 22(3):1240010. doi:10.1142/S0129626412400105.
• [2] Csuhaj-Varjú E, Freund R, Vaszil G. A Connection Between Red-Green Turing Machines and Watson-Crick T0L Systems. In: Durand-Lose J., Nagy B. (eds.) Machines, Computations, and Universality. MCU 2015. Lecture Notes in Computer Science, vol 9288 (2015), Springer, pp. 31-44. doi:10.1007/978-3-319-23111-2_3.
• [3] Csuhaj-Varjú E, Freund R, Vaszil G. Watson-Crick T0L Systems and Red-Green Register Machines. Fundamenta Informaticae 2017. 155(1-2):111-129. doi:10.3233/FI-2017-1578.
• [4] Ershov YL. A hierarchy of sets I, Algebra Logika, 7/1 (1968), 4774 (in Russian). Algebra Logic 7(1) (1968), 2543 (English translation). ID:121369867.
• [5] van Leeuwen J, Wiedermann J. Computation as an unbounded process, Theoretical Computer Science 2012. 429:202-212. doi:10.1016/j.tcs.2011.12.040.
• [6] van Leeuwen J, Wiedermann J. The computational power of Turing’s non-terminating circular a-machines. In: S.B. Cooper, J. van Leeuwen (eds.): Alan Turing - His work and impact, Elsevier, 2013, pp. 80-85.
• [7] Nagy B. An interval-valued computing device. In: CiE 2005, Computability in Europe: New Computational Paradigms, Amsterdam, Netherlands, pp. 166-177 (2005).
• [8] Nagy B, Vályi S. Solving a PSPACE-complete problem by a linear interval-valued computation. In: CiE 2006, Computability in Europe: Logical Approaches to Computational Barriers, University of Wales, Swansea, UK, pp. 216-225 (2006).
• [9] Nagy B, Vályi S. Interval-valued computations and their connection with PSPACE. Theoretical Computer Science 2008. 394(3):208-222. doi:10.1016/j.tcs.2007.12.013.
• [10] Nagy B, Vályi S. Prime factorization by interval-valued computing. Publicationes Mathematicae Debrecen 2011. 79(3):539-551. doi:10.5486/PMD.2011.5134.
• [11] Nagy B, Vályi S. Computing discrete logarithm by interval-valued paradigm. Electronic Proceedings on Theoretical Computer Science 2014. 143:76-86. doi:10.4204/EPTCS.143.7.
• [12] Nagy B, Vályi S. A Characterization of NP Within Interval-Valued Computing. In: Durand-Lose J., Nagy B. (eds.) Machines, Computations, and Universality. MCU 2015. Springer, LNCS, vol 9288 (2015), pp. 164-179. doi:10.1007/978-3-319-23111-2_11.
• [13] Nagy B, Vályi S. A Shift-free Characterization of NP Within Interval-Valued Computing. Fundamenta Informaticae, 2017. 155(1-2):187-207. doi:10.3233/FI-2017-1581.
• [14] Nagy B, Vályi S. An extension of interval-valued computing equivalent to red-green Turing machines, In: Durand-Lose J., Verlan S. (Eds.): Machines, Computations, and Universality: MCU 2018, Springer, LNCS vol 10881 (2018), pp. 137-152. doi:10.1007/978-3-319-92402-1_8.
• [15] Pratt VR, Rabin MO, Stockmeyer LJ. A Characterization of the Power of Vector Machines. Journal of Computer and System Sciences 1976. 12(2):198-221. doi:10.1016/S0022-0000(76)80037-2.
• [16] Turing AM. On Computable Numbers, with an Application to the Entscheidungsproblem, Proceedings of the London Mathematical Society 1937. 42:230-265. Turing Paper 1936.pdf.
• [17] Woods D, Naughton T. An optical model of computation, Theoretical Computer Science 2005. 334(1-3):227-258. doi:10.1016/j.tcs.2004.07.001.
• [18] Wiedermann J, van Leeuwen J. Non-classical Turing machines: extending the notion of computation. Proceedings of NCMA 2017, pp. 29-40.
• [19] Wiedermann J. Characterizing the super-Turing computing power and efficiency of classical fuzzy Turing machines. Theor. Comput. Sci. 2004. 317(1-3):61-69. doi:10.1016/j.tcs.2003.12.004.