Turing Machines & Undecidability

  • Thread starter Thread starter crazyautomata
  • Start date Start date
  • Tags Tags
    Machines Turing
Click For Summary
SUMMARY

The discussion centers on the decidability of the intersection of two languages, L1 and L2, where L1 represents the set of Turing machines that accept any input and L2 represents Turing machines with at most 100 states. It is established that L1 is undecidable due to its relation to the halting problem, while L2 is decidable since the number of states can be counted. The intersection of L1 and L2 remains undecidable, as the properties of L1 dominate the intersection. The discussion also touches on the definitions of undecidable languages and their classifications within the Chomsky hierarchy.

PREREQUISITES
  • Understanding of Turing machines and their encodings
  • Knowledge of decidability and undecidability concepts
  • Familiarity with the halting problem and its implications
  • Basic comprehension of the Chomsky hierarchy of languages
NEXT STEPS
  • Research the implications of the halting problem on Turing machine decidability
  • Study the characteristics of recursively enumerable languages
  • Explore reductions in computability theory
  • Examine the Chomsky hierarchy in detail, focusing on language classifications
USEFUL FOR

This discussion is beneficial for computer science students, theoretical computer scientists, and anyone interested in the foundations of computability and language theory.

crazyautomata
Messages
2
Reaction score
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
I mean partially decidable or recursively enumerable.
 
Aren't they both regular?
 

Similar threads

Comp Sci Problem on undecidable problems
  • · Replies 6 ·
Replies
6
Views
3K
Inductance: Can L1 and L2 be replaced by an equivalent inductor in Figure 4(b)?
  • · Replies 4 ·
Replies
4
Views
2K
Comp Sci When is a problem said to be decidable or undecidable?
  • · Replies 1 ·
Replies
1
Views
2K
Comp Sci Why is NTM Time Complexity Guessing Polynomial?
  • · Replies 2 ·
Replies
2
Views
2K
Design an Infinite NTM for Any Input String: Turing Machine Question
  • · Replies 5 ·
Replies
5
Views
2K
Equations of Motion w/ spring scale
  • · Replies 2 ·
Replies
2
Views
2K
Is the language 0^i10^j decidable?
  • · Replies 1 ·
Replies
1
Views
1K
Engineering Calculating values of impedance in a series/parallel circuit
  • · Replies 4 ·
Replies
4
Views
4K
MHB Can Turing Machine Decidability Extend to Complex Algorithm Outputs?
  • · Replies 1 ·
Replies
1
Views
2K
Turing-recognizable infinite language, decidable subset
  • · Replies 3 ·
Replies
3
Views
3K