Wyniki wyszukiwania - BazTech

Ograniczanie wyników

3 Fundamenta Informaticae

Powiadomienia systemowe

Sesja wygasła!

Znaleziono wyników: 3

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: hypercomputation

Sortuj według:

Ogranicz wyniki do:

Physical Computational Complexity and First-order Logic

Whyman Richard

Fundamenta Informaticae

2021

Vol. 181, nr 2-3

129--161

We present the concept of a theory machine, which is an atemporal computational formalism that is deployable within an arbitrary logical system. Theory machines are intended to capture computation on an arbitrary system, both physical and unphysical, including quantum computers, Blum-Shub-Smale machines, and infinite time Turing machines. We demonstrate that for finite problems, the computational power of any device characterisable by a finite first-order theory machine is equivalent to that of a Turing machine. Whereas for infinite problems, their computational power is equivalent to that of a type-2 machine. We then develop a concept of complexity for theory machines, and prove that the class of problems decidable by a finite first order theory machine with polynomial resources is equal to 𝒩𝒫 ∩ co-𝒩𝒫.

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

Nagy Benedek, Vályi Sándor

Fundamenta Informaticae

2021

Vol. 181, nr 2-3

213--238

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.

On Hypercomputation, Universal and Diagonalization Complete Problems

Eberbach E.

Fundamenta Informaticae

2015

Vol. 139, nr 4

329--346

In the paper we define the class of hypercomputation complete and hard undecidable problems. We prove that typical unsolvable problems are decidable in infinity. We hypothesize that all undecidable problems can be reduced in infinity to each other, i.e., they are H-complete (hypercomputation complete). We propose also two other classes: U-complete (universal complete) and D-complete (diagonalization complete) that use asymptotic reduction and allow separate non- RE and RE non-recursive undecidable classes.