User loginNavigation |
On the importance of Turing completenessIn taking a graduate class in theoretical computer science, I developed a question that was never answered in a way that I felt comfortable with accepting, and now I can't stop thinking about it. We discussed that most computer languages are Turing complete, but did not discuss why that is necessary. When I asked, I got an answer of the type: because there are problems only solvable by Turing complete languages. Yet, I feel no examples coming immediately to mind. Pushdown-automata or stacks are always decidable, and there is an enormous amount of problems that can be solved using them. Also, very many practical problems can be solved in the form of a graph. Yet, many other problems can be solved with primitive recursion which is also decidable. So, I still feel like I am missing something; what are the practical benefits of making a language Turing complete? Or to ask another side of the question: what practical benefits would be lost by not being Turing complete? Any help on this one, I would tremendously appreciate. By jdgallag at 2008-06-11 16:49 | LtU Forum | previous forum topic | next forum topic | other blogs | 46606 reads
|
Browse archivesActive forum topics |
Recent comments
4 days 17 hours ago
1 week 2 days ago
1 week 3 days ago
1 week 3 days ago
2 weeks 1 day ago
2 weeks 4 days ago
2 weeks 4 days ago
2 weeks 4 days ago
4 weeks 20 min ago
4 weeks 1 day ago