Turing Machines & Undecidability

In summary, the discussion is about the decidability of the intersection of two languages, L1 and L2, where L1 consists of Turing machines that accept any input and L2 consists of Turing machines with at most 100 states. The conclusion is that L1 is undecidable and L2 is decidable, but the intersection of L1 and L2 is still undecidable and no reduction has been found to solve it. The concept of undecidable languages is also briefly discussed, with a reference to the Chomsky hierarchy.
  • #1
crazyautomata
3
0

Homework Statement



I have a question regarding undecidable languages.
Let L1 = { M | M is an encoding of a Turing machine that accepts any input} and L2 = { M | M is an Turing machine with at most 100 states}. Is L1 intersect L2 decidable?

Homework Equations





The Attempt at a Solution



I think L1 is undeciable and L2 is decidable. Since we can have a many-to-1 reduction from halting to L1 and for L2, we can count the number of states in some encoding. And I guess L1 intersect L2 is still undecidable but I can't find a reduction to any undecidable problems.

Any help will be appreciated!
 
Physics news on Phys.org
  • #3
I mean partially decidable or recursively enumerable.
 
  • #4
Aren't they both regular?
 
  • #5


I would first clarify the definitions of L1 and L2. L1 is the set of all Turing machines that accept any input, while L2 is the set of Turing machines with at most 100 states. Based on these definitions, I agree with the attempt at a solution that L1 is undecidable and L2 is decidable.

To prove that L1 is undecidable, we can use a reduction from the halting problem, which is a well-known undecidable problem. If we could decide whether a Turing machine accepts any input, we could also decide whether a Turing machine halts on a given input, which is impossible.

For L2, we can use a counting algorithm to determine the number of states in a given Turing machine, which means we can effectively check whether a Turing machine has at most 100 states. Therefore, L2 is decidable.

As for L1 intersect L2, we cannot use the same reduction from the halting problem as we did for L1, since now we have the restriction of at most 100 states. However, we can still use a reduction from the halting problem by modifying the Turing machine to have at most 100 states. Therefore, L1 intersect L2 is still undecidable.

In conclusion, L1 is undecidable, L2 is decidable, and L1 intersect L2 is undecidable.
 

1. What is a Turing Machine?

A Turing Machine is a theoretical model of a computer that was proposed by Alan Turing in 1936. It consists of a tape, a head that can read and write symbols on the tape, and a set of rules that dictate the machine's behavior. The tape is divided into cells, each of which can hold one symbol at a time. The machine can move the head left or right along the tape, read the symbol at the current cell, and change the symbol or move the head based on the rules.

2. How is a Turing Machine different from a regular computer?

A Turing Machine is a mathematical abstraction that is not limited by physical constraints such as memory or processing power. It can theoretically solve any problem that is computable, whereas real computers have limitations. Additionally, a Turing Machine operates on a single tape and has a finite set of states, while a real computer has multiple components and can have an infinite number of states.

3. What is the Halting Problem and why is it important?

The Halting Problem is a classic problem in computer science that asks whether a Turing Machine can determine if another Turing Machine will eventually halt (i.e. stop running) or continue running forever. Alan Turing proved that no Turing Machine can solve the Halting Problem for all inputs, meaning there are some problems that are fundamentally unsolvable by computers. This has implications for the limits of computation and the possibility of creating an all-knowing AI.

4. What is meant by "undecidability" in relation to Turing Machines?

Undecidability refers to the concept that there are certain problems that a Turing Machine cannot solve, meaning there is no algorithm that can always provide a correct answer. These problems are said to be undecidable, and the Halting Problem is a prime example. This concept highlights the limitations of computational power and our understanding of the universe.

5. How are Turing Machines used in computer science and other fields?

Turing Machines are primarily used in theoretical computer science as a way to study the limits of computation and explore the concept of computability. They are also used in fields such as artificial intelligence, linguistics, and philosophy to understand the nature of thought and intelligence. Additionally, real computers and programming languages are often modeled after the abstract concept of a Turing Machine, making it a fundamental concept in computer science education.

Similar threads

  • Engineering and Comp Sci Homework Help
Replies
6
Views
2K
  • Engineering and Comp Sci Homework Help
Replies
4
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
2
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
1
Views
856
  • Engineering and Comp Sci Homework Help
Replies
5
Views
2K
  • Engineering and Comp Sci Homework Help
Replies
3
Views
2K
  • Engineering and Comp Sci Homework Help
Replies
2
Views
2K
  • Programming and Computer Science
Replies
29
Views
2K
  • Engineering and Comp Sci Homework Help
Replies
1
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
1
Views
1K
Back
Top