Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

On Turing Machines

  1. May 18, 2017 #1
    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: May 18, 2017
  2. jcsd
  3. May 21, 2017 at 12:17 AM #2

    jedishrfu

    Staff: Mentor

    Can you rephrase your question a bit?

    Are you looking for actual code in Java or C++ or some generic algorithm?
     
  4. May 21, 2017 at 10:54 AM #3

    QuantumQuest

    User Avatar
    Gold Member

    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: On Turing Machines
  1. Gravitational machines (Replies: 12)

  2. Time machine (Replies: 0)

  3. Time machine (Replies: 0)

Loading...