Turing machines and decidability

In summary, the discussion is about whether a turing machine M can reach a given state q from a given configuration αsβ, and if this problem is decidable. It is considered to be harder than the halting problem, which is known to be undecidable. The reason for this is that if an algorithm was developed to decide this problem, it could also be used to solve the halting problem. Therefore, it is generally shown to be undecidable by reduction to the halting problem.
  • #1
-EquinoX-
564
1
Okay, so if I have a turing machine so called M, is there a configuration alpha s beta which yields a configuration with state q? If it's decidable can someone explain the algorithm to proceed?
 
Technology news on Phys.org
  • #2
That seems to be clearly harder than the halting problem, which is undecidable.
 
  • #3
can you provide me with more detailed explanation why this is undecideable? I mean more saying than it's harder than the halting problem, as I can see that as well

i've also scanned the question directly from the book in case it helps
 

Attachments

  • 1.JPG
    1.JPG
    16.2 KB · Views: 382
  • #4
and here's my answer so far:

Given the initial state s we can decide whether there exists a configuration αsβ and reading all the instructions of the k-cells of the TM machine that there is a path from that configuration to γqη where q is a given state of M and αβγη εΓ because there must exist a path according to the given instructions to reach from state s to q with the given configuration.

So I'd say it's decideable.. please correct me if I am wrong
 
  • #5
So let's say you produce an algorithm that decides this problem.

I can then feed into your algorithm any turing machine M I like, and along with it feed in state q where I choose q to be the halting state for M. If your algorithm works, then your algorithm will tell me whether or not q is reached, and therefore it will have told me whether M halts. But that would mean you have solved the halting problem, therefore there does not exist any such algorithm.

This is what CRGreathouse means by your problem being "harder than the halting problem", it reduces to the halting problem. If you had an algorithm for deciding this problem then you could use the same algorithm to decide the halting problem. This (reducing the problem given to the halting problem) is generally the standard method for proving undecidability...
 
  • #6
ok now it's clear! thanks guys
 

What is a Turing Machine?

A Turing Machine is a mathematical model of a hypothetical computing machine, proposed by Alan Turing in 1936. It consists of a tape, a read/write head, and a set of rules that determine how the head moves and modifies the tape. It is used to understand the limits of computation and has been instrumental in the development of modern computers.

What is the difference between a Turing Machine and a regular computer?

A Turing Machine is a theoretical construct, while a regular computer is a physical machine that is built and used in everyday life. A Turing Machine has an infinite tape, whereas a computer has finite memory. Additionally, a Turing Machine operates on a set of rules, while a computer can be programmed to perform a wide range of tasks.

What is decidability in relation to Turing Machines?

Decidability refers to the ability to determine whether a given problem can be solved by a Turing Machine. A problem is decidable if there exists an algorithm that can solve it, while a problem is undecidable if no such algorithm exists. The concept of decidability is closely related to the limits of computation and has important implications in computer science and mathematics.

Can a Turing Machine solve any problem?

No, a Turing Machine can only solve problems that are decidable. There are many problems that are undecidable, meaning that there is no algorithm or procedure that can solve them. This was proven by Alan Turing in his famous "halting problem" in 1936.

How are Turing Machines relevant to modern computing?

Turing Machines are the basis of modern computing and have been instrumental in the development of computers. They are used to understand the limits of computation and to determine which problems can and cannot be solved by a computer. Additionally, the concept of a Turing Machine has led to the development of new models of computation, such as quantum computers.

Similar threads

  • Programming and Computer Science
Replies
29
Views
2K
  • Programming and Computer Science
Replies
25
Views
3K
  • Programming and Computer Science
Replies
1
Views
748
  • Programming and Computer Science
Replies
2
Views
717
  • Programming and Computer Science
Replies
2
Views
1K
  • Programming and Computer Science
Replies
1
Views
690
  • Engineering and Comp Sci Homework Help
Replies
2
Views
1K
  • Programming and Computer Science
Replies
3
Views
1K
  • Programming and Computer Science
Replies
2
Views
1K
  • Programming and Computer Science
Replies
2
Views
1K
Back
Top