کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
421995 684999 2008 17 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Kolmogorov Complexity Theory over the Reals
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Kolmogorov Complexity Theory over the Reals
چکیده انگلیسی

Kolmogorov Complexity constitutes an integral part of computability theory, information theory, and computational complexity theory—in the discrete setting of bits and Turing machines. Over real numbers, on the other hand, the BSS-machine (aka real-RAM) has been established as a major model of computation. This real realm has turned out to exhibit natural counterparts to many notions and results in classical complexity and recursion theory; although usually with considerably different proofs. The present work investigates similarities and differences between discrete and real Kolmogorov Complexity as introduced by Montaña and Pardo (1998).

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Electronic Notes in Theoretical Computer Science - Volume 221, 25 December 2008, Pages 153-169