چرچ، آلونزو (۱۹۰۳ـ۱۹۹۵)

از ویکیجو | دانشنامه آزاد پارسی
(تغییرمسیر از آلونزو چرچ)

چِرچ، آلونزو (۱۹۰۳ـ۱۹۹۵)(Church, Alonzo)

ریاضی‌دان امریکایی. در ۱۹۳۶، نخستن تعریف دقیق از تابع محاسبه‌پذیر[۱] را عرضه کرد و به‌همین سبب، سهم بسزایی در توسعه و تکامل اسلوب‌مند نظریۀ الگوریتم‌ها[۲] دارد. حل مسئلۀ الگوریتمی[۳] مستلزم ساختن الگوریتمی است که مسئلۀ عضویت در مجموعۀ مفروضی را نسبت به مجموعۀ دیگر حل کند. اگر نتوان چنین الگوریتمی ساخت، مسئله حل‌ناپذیر است. چرچ با استفاده از تز آلن تورینگ[۴]، ریاضی‌دان انگلیسی، ثابت کرد که هیچ الگوریتمی برای رده‌ای از مسائل حساب مقدماتی وجود ندارد. قضایایی که حل‌ناپذیری[۵] چنین مسائلی را ثابت می‌کنند از مهم‌ترین قضایا در نظریۀ الگوریتم‌هایند و قضیۀ چرچ[۶] اولین قضیه از این نوع است. او همچنین حل‌ناپذیری مسئله تشخیص صدق و کذب را برای مجموعۀ همۀ گزاره‌های صادقِ[۷] منطق محمولات[۸] ثابت کرد. چرچ در پرینستون[۹] درس خواند، ۴۰ سال در آن‌جا ماند، و استاد ریاضیات و فلسفه شد. در ۱۹۶۷، به دانشگاه کالیفرنیا در لوس‌آنجلس رفت.



  1. calculable function
  2. theory of algorithms
  3. algorithmic problem
  4. Alan Turing
  5. unsolvability
  6. Church’s theorem
  7. true propositions
  8. predicate logic
  9. Princeton