ऐसी भाषाएं हैं जो एक ट्यूरिंग मशीन संभाल सकती है कि एलबीए नहीं कर सकता है, लेकिन क्या कोई उपयोगी, व्यावहारिक समस्याएं हैं जो एलबीए हल नहीं कर सकती हैं लेकिन टीएम कर सकते हैं?ट्यूरिंग मशीनों की तुलना में लीनियर बाउंड ऑटोमाटा की उपयोगी सीमाएं क्या हैं?
एक एलबीए एक सीमित टेप के साथ सिर्फ एक ट्यूरिंग मशीन है, और वास्तविक कंप्यूटरों में सीमित भंडारण होता है, इसलिए मुझे ऐसा लगता है कि एलबीए नहीं कर सकता व्यावहारिक महत्व के कुछ भी नहीं है। को छोड़कर इस तथ्य के लिए कि एक रैखिक बाउंड ऑटोमैटॉन में केवल एक सीमित टेप नहीं है, लेकिन आकार के साथ एक टेप जो इनपुट के आकार का रैखिक कार्य है। क्या परिमितता की रैखिकता एलबीए को किसी तरह से प्रतिबंधित करती है?
क्या ऐसी समस्याएं हैं जिनके साथ कोई एलबीए सामना नहीं कर सकता है, लेकिन एक घातीय रूप से बाध्य Automaton (यदि ऐसी चीजें मौजूद हैं)?
टीएम कितनी तेजी से हो सकता है? – Beta
टीएम हैं जो वर्तमान में 1 बीएफ (बिगाफ्लॉप) से अधिक है। सैद्धांतिक रूप से, आप उससे ज्यादा तेज नहीं हो सकते हैं! – RAL
@ रॉबर्ट लैम्ब: बहुत मजाकिया, लेकिन मेरा सवाल गंभीर था। चूंकि एक टीएम नहीं बनाया जा सकता है, इसलिए हमें कुछ संदर्भ बिंदु चाहिए यदि हम "व्यावहारिक" समस्याओं के बारे में पूछने जा रहे हैं। – Beta