पुनरावर्ती और पुनरावर्ती संख्यात्मक भाषाओं के बीच अंतर क्या है

Question

मैं सोच रहा था कि पुनरावर्ती और पुनरावर्ती संख्यात्मक भाषाओं के बीच क्या अंतर है और ट्यूरिंग मशीनों के मामले में क्या अंतर है। मुझे पता है कि पुनरावर्ती संख्यात्मक भाषाएं रिकर्सिव भाषाओं का सबसेट हैं लेकिन मुझे इससे परे अंतर के बारे में निश्चित नहीं है। आर एक (उचित) आरई का उपसमुच्चय होती है:

Answer 1

आप संबंध आर और के बीच आरई पीछे की ओर है। असल में, एक पुनरावर्ती भाषा वह है जिसके लिए आपके पास कुल निर्णायक होता है।

पुनरावर्ती संख्यात्मक भाषाओं की परिभाषा को याद करें, जिसके लिए आंशिक decider मौजूद है; यानी, एक ट्यूरिंग मशीन जो आपके वर्णमाला पर एक शब्द इनपुट के रूप में दी गई है, या तो आपकी भाषा के अनुसार शब्द को सही तरीके से स्वीकार/अस्वीकार कर देगी, या यदि शब्द आपकी भाषा में नहीं है, तो यह हमेशा के लिए लूप हो सकता है।

इसके विपरीत एक पुनरावर्ती भाषा एक है जिसके लिए कुल निर्णायक मौजूद है, यानी वह जो कभी लूप नहीं करेगा, और हमेशा स्वीकार्य या अस्वीकार करने वाली स्थिति में रुक जाएगा।

इन दो परिभाषाओं को एक-दूसरे के बगल में रखते हुए, यह स्पष्ट है कि एक पुनरावर्ती भाषा भी पुनरावर्ती रूप से गणना योग्य है, क्योंकि कुल निर्णायक भी आंशिक है (यह सही उत्तर के साथ रोकने के बजाय लूप को कभी भी "चुनता नहीं")।