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

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

সংজ্ঞা

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

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

উদাহরণ

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

প্রয়োগ

গণিত, দর্শন,^[১] ভাষাবিজ্ঞান,^[২]^[৩] এবং কম্পিউটার বিজ্ঞান.^[৪] ল্যাম্‌ডা ক্যালকুলাসের ব্যবহার বিদ্যমান।

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

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

(λ x . x x) (λ x . x x) \to_{β} (λ x . x x) (λ x . x x) \to_{β} \dots

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

(λ x . x x x) (λ x . x x x) \to_{β} (λ x . x x x) (λ x . x x x) (λ x . x x x) \to_{β} \dots

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

স্থির বিন্দু

গণিতে কোন ফাংশন $f$ -এর স্থির বিন্দু বলতে বোঝায় এমন কোন বিন্দু $x$ যার জন্য

f (x) = x

বা ল্যাম্‌ডা ক্যালকুলাসের রীতিতে,

f x = x

যেহেতু ল্যাম্‌ডা ক্যালকুলাসে প্রতিটি রাশিই ফাংশন, তাই এখানে কোন ফাংশনের স্থির বিন্দু নিজেও আরেকটি ফাংশন। লক্ষ্যনীয়, এই ক্যালকুলাসে ফাংশন বাদে অন্য কোন গাণিতিক ধারণা নেই। বস্তুত, চার্চের প্রাথমিক লক্ষ্য ছিল ফাংশনের ধারণাকে গণিতের ভিত্তি হিসেবে দাঁড় করানো।

সাধারণত কোন গাণিতিক ফাংশনের স্থির বিন্দু নাও থাকতে পারে (বা থাকলেও তাকে খুঁজে বের করা একটা গাণিতিক সমস্যা), কিন্তু ল্যামডা ক্যালকুলাসে প্রতিটি রাশিরই স্থির বিন্দু আছে, এই স্থির বিন্দুটি আরেকটি ল্যাম্‌ডা রাশি।

প্রমাণ: $𝐘 = λ f . (λ x . f (x x)) (λ x . f (x x))$ একটি স্থির বিন্দু নির্ণায়ক (ইংলিশে, Fixed Point Combinator),

(𝐘 f)

রাশিটি

f

-এর স্থির বিন্দু।

দেখা যাক, $(𝐘 f) \to_{β} (λ x . f (x x)) (λ x . f (x x)) \to_{β} f ((λ x . f (x x)) (λ x . f (x x))) = f (𝐘 f)$

অর্থাৎ $(𝐘 f)$ এমন একটি ফাংশন যার উপর $f$ -কে প্রয়োগ করলে আবার ঐ ফাংশনটিই ফেরত পাওয়া যায় (স্থির বিন্দুর সংজ্ঞা)।

লক্ষ্যণীয়, এই প্রমাণটি শুধু যে স্থির বিন্দুর অস্তিত্ত্ব দেখায় তাই না, (একটি) স্থির বিন্দু নির্ণয়ও করে দেয়।

স্থির বিন্দু নির্ণায়কের মাধ্যমে ল্যাম্‌ডা ক্যালকুলাসে পুনরাবৃত্ত ফাংশন (Recursive function) প্রকাশ করা যায়।

টাইপ তত্ত্ব এবং ল্যামডা ক্যালকুলাস