Results 1 to 10 of about 356 (69)
On capabilities of quantum-mechanical computer models [PDF]
Tehnika, 2022 The work includes the analyses of the theoretical capabilities of quantum-mechanical versus classical computer models in terms of their universality, their application domain, their efficacy in solving the problems and their technological feasibility ...
Simonović Svetomir I.
doaj +1 more source
Constructive Many-one Reduction from the Halting Problem to Semi-unification (Extended Version) [PDF]
Logical Methods in Computer Science, 2023 Semi-unification is the combination of first-order unification and first-order matching. The undecidability of semi-unification has been proven by Kfoury, Tiuryn, and Urzyczyn in the 1990s by Turing reduction from Turing machine immortality (existence of
Andrej Dudenhefner
doaj +1 more source
An Intensional Concurrent Faithful Encoding of Turing Machines [PDF]
Electronic Proceedings in Theoretical Computer Science, 2014 The benchmark for computation is typically given as Turing computability; the ability for a computation to be performed by a Turing Machine. Many languages exploit (indirect) encodings of Turing Machines to demonstrate their ability to support arbitrary ...
Thomas Given-Wilson
doaj +1 more source
Pushdown Automata and Context-Free Grammars in Bisimulation Semantics [PDF]
Logical Methods in Computer Science, 2023 The Turing machine models an old-fashioned computer, that does not interact with the user or with other computers, and only does batch processing. Therefore, we came up with a Reactive Turing Machine that does not have these shortcomings. In the Reactive
Jos C. M. Baeten +2 more
doaj +1 more source
A Formalization and Proof of the Extended Church-Turing Thesis -Extended Abstract- [PDF]
Electronic Proceedings in Theoretical Computer Science, 2012 We prove the Extended Church-Turing Thesis: Every effective algorithm can be efficiently simulated by a Turing machine. This is accomplished by emulating an effective algorithm via an abstract state machine, and simulating such an abstract state machine ...
Nachum Dershowitz, Evgenia Falkovich
doaj +1 more source
Some undecidable problems about the trace-subshift associated to a Turing machine [PDF]
Discrete Mathematics & Theoretical Computer Science, 2015 We consider three problems related to dynamics of one-tape Turing machines: Existence of blocking configurations, surjectivity in the trace, and entropy positiveness. In order to address them, a reversible two-counter machine is simulated by a reversible
Anahí Gajardo +2 more
doaj +1 more source
How Hard Is It to Detect Surveillance? A Formal Study of Panopticons and Their Detectability Problem
Cryptography, 2022 The Panopticon (which means “watcher of everything”) is a well-known prison structure of continuous surveillance and discipline studied by Bentham in 1785. Today, where persistent, massive scale, surveillance is immensely facilitated by new technologies,
Vasiliki Liagkou +3 more
doaj +1 more source
The $\pi$-Calculus is Behaviourally Complete and Orbit-Finitely Executable [PDF]
Logical Methods in Computer Science, 2021 Reactive Turing machines extend classical Turing machines with a facility to model observable interactive behaviour. We call a behaviour (finitely) executable if, and only if, it is equivalent to the behaviour of a (finite) reactive Turing machine.
Bas Luttik, Fei Yang
doaj +1 more source
Quaternionic quantum Turing machines
Frontiers in Physics, 2023 Quaternionic quantum theory is an extension of the standard complex quantum theory. Inspired by this, we study the quaternionic quantum computation using quaternions.
Songsong Dai
doaj +1 more source
Molecular system for an exponentially fast growing programmable synthetic polymer
Scientific Reports, 2023 In this paper, we demonstrate a molecular system for the first active self-assembly linear DNA polymer that exhibits programmable molecular exponential growth in real time, also the first to implement “internal” parallel insertion that does not rely on ...
Nadine Dabby, Alan Barr, Ho-Lin Chen
doaj +1 more source