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

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

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

تاریخ

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