Feasible Mathematics I: A Mathematical Sciences Institute Workshop, Ithaca, New York, June 1989

یک الگوریتم به‌اصطلاح \"موثر\" ممکن است به مقادیر محدود زیادی از منابع زمان و مکان نیاز داشته باشد و بنابراین ممکن است در دنیای واقعی عملی نباشد. یک الگوریتم \"امکان پذیر\" الگوریتمی است که فقط به مقدار محدودی فضا و/یا زمان برای اجرا نیاز دارد. ایده کلی این است که یک الگوریتم عملی، الگوریتمی است که ممکن است در کامپیوترهای امروزی یا حداقل فردا عملی باشد. هیچ آنالوگ قطعی برای تز چرچ وجود ندارد که یک تعریف ریاضی از امکان سنجی ارائه دهد. با این حال، گسترده ترین مدل ریاضی محاسباتی امکان پذیر مورد مطالعه، محاسبه پذیری زمان چند جمله ای است. ریاضیات امکان پذیر هم شامل مطالعه محاسبات امکان پذیر از دیدگاه ریاضی و منطقی و هم پردازش مجدد ریاضیات سنتی از دیدگاه محاسبات امکان پذیر است. تنوع ریاضیات امکان پذیر توسط این نشان داده شده است. مطالب این جلد شامل مقالاتی در مورد قطعات ضعیف حسابی، در مورد توابع نوع بالاتر، در مورد منطق خطی محدود، در مورد تعاریف زیر بازگشتی از کلاس های پیچیدگی، در مورد نظریه مدل محدود، در مورد مدل های محاسبات امکان پذیر برای اعداد واقعی، در مورد فضاهای برداری و ... نظریه بازگشت vVorkshop on Feasible Mathematics توسط موسسه علوم ریاضی حمایت مالی شد و در دانشگاه کرنل، 26 تا 28 ژوئن 1989 برگزار شد.

A so-called "effective" algorithm may require arbitrarily large finite amounts of time and space resources, and hence may not be practical in the real world. A "feasible" algorithm is one which only requires a limited amount of space and/or time for execution; the general idea is that a feasible algorithm is one which may be practical on today's or at least tomorrow's computers. There is no definitive analogue of Church's thesis giving a mathematical definition of feasibility; however, the most widely studied mathematical model of feasible computability is polynomial-time computability. Feasible Mathematics includes both the study of feasible computation from a mathematical and logical point of view and the reworking of traditional mathematics from the point of view of feasible computation. The diversity of Feasible Mathematics is illustrated by the. contents of this volume which includes papers on weak fragments of arithmetic, on higher type functionals, on bounded linear logic, on sub recursive definitions of complexity classes, on finite model theory, on models of feasible computation for real numbers, on vector spaces and on recursion theory. The vVorkshop on Feasible Mathematics was sponsored by the Mathematical Sciences Institute and was held at Cornell University, June 26-28, 1989.