اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدStraight-line instruction sequence completeness for total calculation on cancellation meadows
124
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
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.
قيم البحث
اقرأ أيضاً
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 ju
mps 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 ju
mp 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.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
