ল্যাম্‌ডা ক্যালকুলাস

ল্যামডা ক্যালকুলাস (λ-calculus) কম্পিউটারের আচরণ অধ্যয়নের জন্য জনপ্রিয় একটি গাণিতিক ব্যবস্থা। আলোনযো চার্চ তার তাত্ত্বিক গবেষণায় কম্পিউটেবল ফাংশনের ধারণাকে এর মাধ্যমে প্রকাশ করেন। চার্চ-টুরিং প্রকল্প দাবী করে যে, যে কোন কম্পিউটিং সমস্যাকে এর মাধ্যমে (বা টুরিং মেশিনের মাধ্যমে) প্রকাশ করা যায়।

সংজ্ঞা

ল্যামডা ক্যালকুলাস হলো ল্যামডা রাশিমালার বিজ্ঞান, যেখানে ল্যামডা রাশিগুলো মূলত এক প্যারামিটারবিশিষ্ট ফাংশন, যারা প্যারামিটার হিসেবে অপর কোন ল্যামডা রাশি নেয়, এবং এর ফলাফল আরেকটি ল্যামডা রাশি। গঠনগতভাবে ল্যামডা রাশিগুলো হল

• চলক যাকে একটি অক্ষর দিয়ে প্রকাশ করা হয়, যেমন $x$ (আসলে এই চলকটিও একটি ফাংশন (সকল ল্যামডা রাশিই যেহেতু ফাংশন) কিন্তু একে কারো উপর প্রয়োগ করা হয় নি)।
• প্রয়োগ একটি ল্যামডা রাশিকে আরেকটি ল্যামডা রাশির উপর প্রয়োগ করা যায়। প্রয়োগ বুঝাতে যাকে প্রয়োগ করা হচ্ছে এবং যার উপর প্রয়োগ করা হচ্ছে সেই রাশি দুইটিকে পরপর লেখা হয়, যেমন $(MN)$, যেখানে $M$কে $N$এর উপর প্রয়োগ করা হচ্ছে। সম্পূর্ণ রাশিটির মান হল এই প্রয়োগের ফলাফল রাশিটি।
• অ্যাবস্ট্রাকশন একটি ল্যামডা রাশি থেকে যখন কোন একটি চলককে সরিয়ে নেয়া হয় তখন এরকম একটি ফাংশন হয় যাকে অন্য কোন রাশির উপর প্রয়োগ করলে রাশিটির মান হবে ঐ চলককে ঐ রাশিটি দিয়ে প্রতিস্থাপন করলে যেই রাশিটি পাওয়া যায়। কোন রাশি $M$ থেকে কোন চলক $x$ কে সরিয়ে নিলে যে ফাংশনটি পাওয়া যায় তাকে লেখা হয় $\lambda x.\,M$, একে অন্য কোন রাশি $N$ এর উপর প্রয়োগ করলে পাওয়া যায় $M[x:=N]$, অর্থাৎ $M$

এ সকল $x$কে $N$ দিয়ে প্রতিস্থাপন করলে যে রাশিটি পাওয়া যায়।