Turing Machines: Classifying for Decidable Problems

  • Thread starter Thread starter Gear300
  • Start date Start date
  • Tags Tags
    Machines Turing
Gear300
Messages
1,209
Reaction score
9
It's been a while since I've done this, but the question spurred on. Is there any sort of named class that a machine that can decide on all Turing decidable problems would belong to?

Edit: Actually, I guess it would be Turing if you could program it to decide on a particular problem.
 
Last edited:
Computer science news on Phys.org
Can you rephrase your question a bit?

Are you looking for actual code in Java or C++ or some generic algorithm?
 
Gear300 said:
It's been a while since I've done this, but the question spurred on. Is there any sort of named class that a machine that can decide on all Turing decidable problems would belong to?

Edit: Actually, I guess it would be Turing if you could program it to decide on a particular problem.

You must put your question in a more clear way as jedishrfu points out. A problem is decidable if there is an algorithm to answer it. As you may know an algorithm - formally speaking, is a TM that halts on all inputs whether accepted or not. So, effectively a decidable problem is equivalent to a recursive language. Now, just by guesswork, is your question about a UTM (Universal Turing Machine)? Because in this case the language ##L_{u}## of UTM is not recursive but recursively enumerable.
 
  • Like
Likes fresh_42

Similar threads

  • · Replies 11 ·
Replies
11
Views
2K
  • · Replies 9 ·
Replies
9
Views
3K
Replies
29
Views
5K
Replies
1
Views
2K
  • · Replies 6 ·
Replies
6
Views
3K
Replies
6
Views
8K
  • · Replies 9 ·
Replies
9
Views
2K
  • · Replies 14 ·
Replies
14
Views
2K
  • · Replies 2 ·
Replies
2
Views
2K
  • · Replies 3 ·
Replies
3
Views
3K