Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userStraight-line instruction sequence completeness for total calculation on cancellation meadows
120
0
0.0
(
0
)
Added by
Inge Bethke
Publication date
2009
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
A combination of program algebra with the theory of meadows is designed leading to a theory of computation in algebraic structures which use in addition to a zero test and copying instructions the instruction set ${x Leftarrow 0, x Leftarrow 1, xLeftarrow -x, xLeftarrow x^{-1}, xLeftarrow x+y, xLeftarrow xcdot y}$. It is proven that total functions on cancellation meadows can be computed by straight-line programs using at most 5 auxiliary variables. A similar result is obtained for signed meadows.
rate research
Read More
We investigate the expressiveness of backward jumps in a framework of formalized sequential programming called program algebra. We show that - if expressiveness is measured in terms of the computability of partial Boolean functions - then backward jumps are superfluous. If we, however, want to prevent explosion of the length of programs, then backward jumps are essential.
Let Q_0 denote the rational numbers expanded to a meadow by totalizing inversion such that 0^{-1}=0. Q_0 can be expanded by a total sign function s that extracts the sign of a rational number. In this paper we discuss an extension Q_0(s ,sqrt) of the signed rationals in which every number has a unique square root.
A meadow is a commutative ring with a total inverse operator satisfying 0^{-1}=0. We show that the class of finite meadows is the closure of the class of Galois fields under finite products. As a corollary, we obtain a unique representation of minimal finite meadows in terms of finite prime fields.
Every partial function from bit strings of a given length to bit strings of a possibly different given length can be computed by a finite instruction sequence that contains only instructions to set and get the content of Boolean registers, forward jump instructions, and a termination instruction. We look for an equivalence relation on instruction sequences of this kind that captures to a reasonable degree the intuitive notion that two instruction sequences express the same algorithm.
Let Q_0 denote the rational numbers expanded to a meadow, that is, after taking its zero-totalized form (0^{-1}=0) as the preferred interpretation. In this paper we consider cancellation meadows, i.e., meadows without proper zero divisors, such as $Q_0$ and prove a generic completeness result. We apply this result to cancellation meadows expanded with differentiation operators, the sign function, and with floor, ceiling and a signed variant of the square root, respectively. We give an equational axiomatization of these operators and thus obtain a finite basis for various expanded cancellation meadows.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
