کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
431420 688535 2015 20 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Models of computation for partial functions on the reals
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Models of computation for partial functions on the reals
چکیده انگلیسی


• We compare 4 models of computation for partial functions on the reals.
• These satisfy “domain exhaustion” and continuity assumptions.
• We conjecture they include all elementary functions on the reals.

We compare models of computation for partial functions f:R⇀Rf:R⇀R. We consider four models: two concrete (Grzegorczyk–Lacombe and tracking computability), one abstract (approximability by a While program with “countable choice”) and a new hybrid model: multipolynomial approximability. We show that these four models are equivalent, under the two assumptions:(1)the domain of f is the union of an effective exhaustion, i.e. a sequence of “stages”, each of which is a finite union of disjoint rational open intervals, and(2)f is effectively locally uniformly continuous w.r.t. this exhaustion. These assumptions seem to hold for all unary elementary functions of real analysis, many of which are, of course, partial. We make a conjecture with regard to this.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Logical and Algebraic Methods in Programming - Volume 84, Issue 2, March 2015, Pages 218–237
نویسندگان
, ,