Turing Machines: Classifying for Decidable Problems

  • Thread starter Thread starter Gear300
  • Start date Start date
  • Tags Tags
    Machines Turing
AI Thread Summary
A machine capable of deciding all Turing decidable problems would belong to the class of Turing machines. A problem is considered decidable if there exists an algorithm that can provide an answer, meaning the algorithm (or Turing machine) halts on all inputs, whether accepted or rejected. This aligns with the concept of recursive languages. However, the language of a Universal Turing Machine (UTM) is not recursive; it is classified as recursively enumerable. The discussion emphasizes the need for clarity in formulating questions about decidability and algorithms.
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
In my discussions elsewhere, I've noticed a lot of disagreement regarding AI. A question that comes up is, "Is AI hype?" Unfortunately, when this question is asked, the one asking, as far as I can tell, may mean one of three things which can lead to lots of confusion. I'll list them out now for clarity. 1. Can AI do everything a human can do and how close are we to that? 2. Are corporations and governments using the promise of AI to gain more power for themselves? 3. Are AI and transhumans...
Thread 'ChatGPT Examples, Good and Bad'
I've been experimenting with ChatGPT. Some results are good, some very very bad. I think examples can help expose the properties of this AI. Maybe you can post some of your favorite examples and tell us what they reveal about the properties of this AI. (I had problems with copy/paste of text and formatting, so I'm posting my examples as screen shots. That is a promising start. :smile: But then I provided values V=1, R1=1, R2=2, R3=3 and asked for the value of I. At first, it said...
Back
Top