نظریہ کمپیوٹیشن

نظریہ کمپیوٹیشن یا نظریہ شمارندگی (انگریزی: Theory of Computation) ریاضیات اور کمپیوٹر سائنس کی ایک شاخ ہے جو یہ معاملہ دیکھتی ہے کہ مسائل کو شمارندگی کی تمثیل میں، الخوارزم کے استعمال سے، کتنی اہلیت سے حل کیا جا سکتا ہے۔ اس میدان کو دو شاخوں میں تقسیم کیا جاتا ہے: نظریہ شمارندیت اور نظریہ پیچیدگی، مگر دونوں شاخیں شمارندگی کے رسمی تمثیل سے معاملہ کرتی ہیں۔

شمارندگی کے بامشقت مطالعہ کے لیے، سائنس دان کمپیوٹروں کے تجرید کا استعمال کرتے ہیں جسے "شمارندگی کا تمثیل" کہتے ہیں۔ بہت سے تمثیلات زیرِ استعمال ہیں، مگر سب سے زیادہ عام امتحان کیا جانے والا ٹیورینگ آلہ ہے۔ سمجھنے کے لیے ٹیورنگ آلہ کو ایک عام کمپیوٹر تصور کیا جا سکتا ہے جس کے پاس لامتناہی میموری کی گنجائش ہو، اگرچہ وہ یادداشت تک رسائی چھوٹے متفرد قتلوں میں کر سکے۔ سائنس دان ٹیورنگ آلہ کا مطالعہ اس لیے کرتے ہیں کیونکہ اسے آسانی سے کلیات کیا جا سکتا ہے، اس کا تحلیل ممکن ہے اور نتائج مثبوت کرنے کے لیے استعمال کیا جا سکتا ہے اور یہ نمائندہ ہے جسے بہت سے لوگ شمارندگی کا سب سے طاقتور ممکن "معقول" تمثیلِ شمارندگی سمجھتے ہیں۔ ہو سکتا ہے کہ یہ لگے کہ امکانی لامتناہی یاداشت اسے غیر حقیقی بنا دیتی ہے، مگر ٹیورنگ آلہ سے کوئی قابلِ فیصلہ مسئلہ ہمیشہ متناہی یاداشت کے استعمال سے حل (فیصلہ) ہو گا۔ اس لیے اصولاً، کوئی مسئلہ جو ٹیورنگ آلہ سے حل (فیصلہ) ہو سکے، کو ایسے کمپیوٹر پر حل کیا جا سکتا ہے جس کی یادداشت یحیط ہو۔

تاریخ

نظریہ شمارندگی کو شمارندی سائنس میں ہر قسم کی تماثیل کی تخلیق سمجھا جا سکتا ہے۔ اس لیے ریاضیات اور منطق کا استعمال کیا جاتا ہے۔ پچھلی صدی میں یہ آزاد نصابی شعبہ بن گیا اور ریاضیات سے علاحدہ سمجھا جانے لگا۔ اس "نئے" شعبہ کے اولین رہنماؤں میں شامل ہیں، الونزو چرچ، ایلن ٹیورنگ، جان وان نیومان اور کلاڈ شینن۔