Turing Machines & Undecidability

  • Thread starter Thread starter crazyautomata
  • Start date Start date
  • Tags Tags
    Machines Turing
AI Thread Summary
The discussion focuses on the decidability of the intersection of two languages, L1 and L2, where L1 is the set of Turing machine encodings that accept any input and L2 consists of 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 is suggested to remain undecidable, but the poster struggles to find a reduction to demonstrate this. There is also confusion regarding the definitions of undecidable languages and their classifications within the Chomsky hierarchy. The conversation highlights the complexities of understanding decidability in the context of Turing machines.
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
Views
2K
Inductance: Can L1 and L2 be replaced by an equivalent inductor in Figure 4(b)?
Replies
4
Views
2K
Comp Sci When is a problem said to be decidable or undecidable?
Replies
1
Views
2K
Comp Sci Why is NTM Time Complexity Guessing Polynomial?
Replies
2
Views
2K
Design an Infinite NTM for Any Input String: Turing Machine Question
Replies
5
Views
2K
Equations of Motion w/ spring scale
Replies
2
Views
2K
Is the language 0^i10^j decidable?
Replies
1
Views
1K
Engineering Calculating values of impedance in a series/parallel circuit
Replies
4
Views
4K
MHB Can Turing Machine Decidability Extend to Complex Algorithm Outputs?
Replies
1
Views
2K
Turing-recognizable infinite language, decidable subset
Replies
3
Views
2K

Hot Threads

Recent Insights

Back
Top