نظریۂ شمارندگی

آزاد دائرۃ المعارف، ویکیپیڈیا سے
:چھلانگ بطرف رہنمائی، تلاش

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

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

تاریخ[ترمیم]

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