सङ्गणनासिद्धान्तः
सङ्गणनासिद्धान्तं सैद्धान्तिकसङ्गणकशास्त्रस्य तथा च गणितशास्त्रस्य काचित् शाखाऽस्ति। कस्मिँश्चित् सङ्गणनाप्रादर्शे काञ्चित् कलनविधिमुपयुज्य काचित् समस्या समाधातुं शक्यते न वा तथा च कया दक्षतया सा समाधातुं शक्या इति सङ्गणनासिद्धान्तस्य अधिकरणविषयः। एतस्या विद्यायाः तिस्रः शाखाः सन्ति- स्वचलितसिद्धान्तम्, सङ्गणनीयतासिद्धान्तं, साङ्गणनिकजटिलतासिद्धान्तं चेति।[१]
सङ्गणनायाः विशदाध्ययनार्थं सङ्गणनाशास्त्रिणस्तु सङ्गणकस्य गणितीयप्रतिबिम्बं चिन्तयन्ति, यस्य तु नाम सङ्गणनाप्रादर्श इति। तत्र बहवः सङ्गणनाप्रादर्शाः सन्ति, परन्तु बहुप्रयुक्तस्तु टूरिङ्गयन्त्रम् इति। सङ्गणकशास्त्रिणः टूरिङ्गयन्त्रस्य अध्ययनं कुर्वन्ति यस्मात् एतत् प्रारूपीकरणे सरलम्, एतस्य विश्लेषणं कृत्वा फलानि प्रमाणीकर्तुं शक्यन्ते। यस्माच्च एतद्यन्त्रं शक्ततमस्य तार्किकस्य सङ्गणनाप्रादर्शस्य प्रतिनिधिरस्ति (पश्यतु चर्च-टूरिङ्ग-सिद्धान्तम्)। एतद् भासते यत् सम्भाव्या अनन्ता स्मृतिशक्तिः (या टूरिङ्गयन्त्रे अपेक्ष्यते) कश्चन अप्राप्यः गुणः, परन्तु यदा काचित् निश्चेया समस्या टूरिङ्गयन्त्रेण समाधीयते, तदा केवलस्याः परिमितायाः स्मृतिशक्त्याः आवश्यकता भवति। तस्मात् याऽपि समस्या टूरिङ्गयन्त्रे समाधातुं शक्यते सा तु तादृशे कस्मिँश्चित् सङ्गणकेऽपि समाधातुं शक्यते यस्मिन् परिमितमात्रिका स्मृतिर्भवेत्।
इतिहासः
[सम्पादयतु]सङ्गणनासिद्धान्ते वस्तुतः सङ्गणकशास्त्रान्तर्गतं सर्वप्रकारकानां प्रतिमानानां रचना अन्तर्हिता भवति। तस्मादत्र गणितशास्त्रस्य तर्कशास्त्रस्य च उपयोगः क्रियते। गते शताब्दे एतत् स्वतन्त्रशैक्षणिकक्षेत्रत्वेन प्रतिष्ठितम्। सङ्गणनासिद्धान्तस्य केचित् पुरःगामिनः आसन्- एलोन्जो-चर्चः, एलन्-टूरिंगः, स्टीफन्-क्लीनः, जान्-वान्-न्यूमैनः तथा च क्लाउड्शैननः इत्येते ।
सन्दर्भाः
[सम्पादयतु]- ↑ Sipser