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

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

সংজ্ঞা

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

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

উদাহরণ

• $\lambda x.\,x$ রাশিটিকে যার উপর প্রয়োগ করা হয়, রাশিটির মান তাই হয়। অর্থাৎ $(\lambda x.\,x)\,y\rightarrow _{\beta }y$, ফাংশনটি অভেদ ফাংশন।
• সাধারণভাবে, কোন ফাংশন $f$কে কোন মান $x$এর উপর প্রয়োগ করলে ফলাফল হয় $(f\,x)$, ধরা যাক $f$ হলো ফ্যাকটোরিয়াল ফাংশন, আর $x$এর মান $3$, তাহলে $(f\,x)\rightarrow _{\beta }({\mbox{factorial}}\,3)\rightarrow _{\beta }6$.

বিটা-সংক্ষেপণ

প্রতিস্থাপনের এই পদ্ধতির নাম বিটা-সংক্ষেপণ ($\beta$ reduction), সবসময় যদিও রাশিটি সংক্ষিপ্ত হয় না (আকারে),

$(\lambda x.\,x\,x)\,(\lambda x.\,x\,x)\rightarrow _{\beta }(\lambda x.\,x\,x)\,(\lambda x.\,x\,x)\rightarrow _{\beta }\ldots$

এমনকি আকারে বাড়ে এরকম উদাহরণও খুবই সহজ,

$(\lambda x.\,x\,x\,x)\,(\lambda x.\,x\,x\,x)\rightarrow _{\beta }(\lambda x.\,x\,x\,x)\,(\lambda x.\,x\,x\,x)\,(\lambda x.\,x\,x\,x)\rightarrow _{\beta }\ldots$

তবে কম্পিউটেশনের মূলমন্ত্র যে এই সংক্ষেপনেই নিহিত তাতে কোন সন্দেহ নেই। কোন সংক্ষেপণটি থামবে কোনটি থামবে না তা নির্ণয় করার কোন সাধারণ অ্যালগোরিদম নেই, যার প্রমাণ টুরিং মেশিনের থামা-না-থামা সমস্যা।