Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn the information carried by programs about the objects they compute
219
0
0.0
(
0
)
Added by
Mathieu Hoyrup
Publication date
2014
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
In computability theory and computable analysis, finite programs can compute infinite objects. Presenting a computable object via any program for it, provides at least as much information as presenting the object itself, written on an infinite tape. What additional information do programs provide? We characterize this additional information to be any upper bound on the Kolmogorov complexity of the object. Hence we identify the exact relationship between Markov-computability and Type-2-computability. We then use this relationship to obtain several results characterizing the computational and topological structure of Markov-semidecidable sets.
rate research
Read More
We apply a paraconsistent logic to reason about fractions.
Most modern (classical) programming languages support recursion. Recursion has also been successfully applied to the design of several quantum algorithms and introduced in a couple of quantum programming languages. So, it can be expected that recursion will become one of the fundamental paradigms of quantum programming. Several program logics have been developed for verification of quantum while-programs. However, there are as yet no general methods for reasoning about (mutual) recursive procedures and ancilla quantum data structure in quantum computing (with measurement). We fill the gap in this paper by proposing a parameterized quantum assertion logic and, based on which, designing a quantum Hoare logic for verifying parameterized recursive quantum programs with ancilla data and probabilistic control. The quantum Hoare logic can be used to prove partial, total, and even probabilistic correctness (by reducing to total correctness) of those quantum programs. In particular, two counterexamples for illustrating incompleteness of non-parameterized assertions in verifying recursive procedures, and, one counterexample for showing the failure of reasoning with exact probabilities based on partial correctness, are constructed. The effectiveness of our logic is shown by three main examples -- recursive quantum Markov chain (with probabilistic control), fixed-point Grovers search, and recursive quantum Fourier sampling.
We consider the proof complexity of the minimal complete fragment, KS, of standard deep inference systems for propositional logic. To examine the size of proofs we employ atomic flows, diagrams that trace structural changes through a proof but ignore logical information. As results we obtain a polynomial simulation
The correct by construction paradigm is an important component of modern Formal Methods, and here we use the probabilistic Guarded-Command Language $mathit{pGCL}$ to illustrate its application to $mathit{probabilistic}$ programming. $mathit{pGCL}$ extends Dijkstras guarded-command language $mathit{GCL}$ with probabilistic choice, and is equipped with a correctness-preserving refinement relation $(sqsubseteq)$ that enables compact, abstract specifications of probabilistic properties to be transformed gradually to concrete, executable code by applying mathematical insights in a systematic and layered way. Characteristically for correctness by construction, as far as possible the reasoning in each refinement-step layer does not depend on earlier layers, and does not affect later ones. We demonstrate the technique by deriving a fair-coin implementation of any given discrete probability distribution. In the special case of simulating a fair die, our correct-by-construction algorithm turns out to be within spitting distance of Knuth and Yaos optimal solution.
We show experimentally that a continuous, linear, dielectric antenna in which a superluminal polarization-current distribution accelerates can be used to transmit a broadband signal that is reproduced in a comprehensible form at a chosen target distance and angle. The requirement for this exact correspondence between broadcast and received signals is that each moving point in the polarization-current distribution approaches the target at the speed of light at all times during its transit along the antenna. This results in a one-to-one correspondence between the time at which each point on the moving polarization current enters the antenna and the time at which {it all} of the radiation emitted by this particular point during its transit through the antenna arrives simultaneously at the target. This has the effect of reproducing the desired time dependence of the original broadcast signal. For other observer/detector positions, the time dependence of the signal is scrambled, due to the non-trivial relationship between emission (retarded) time and reception time. This technique represents a contrast to conventional radio transmission methods; in most examples of the latter, signals are broadcast with little or no directivity, selectivity of reception being achieved through the use of narrow frequency bands. In place of this, the current paper uses a spread of frequencies to transmit information to a particular location; the signal is weaker and has a scrambled time dependence elsewhere. We point out the possible relevance of this mechanism to 5G neighbourhood networks. This work also constitutes a ground-based astrophysics experiment that gives strong clues towards the emission mechanism of pulsars.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
