Turing Machines & Undecidability

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

Discussion Overview

The discussion revolves around the decidability of the intersection of two languages related to Turing machines: L1, which consists of Turing machines that accept any input, and L2, which includes Turing machines with at most 100 states. The inquiry seeks to understand the nature of L1 and L2 in terms of decidability and their intersection.

Discussion Character

  • Homework-related
  • Debate/contested

Main Points Raised

  • One participant claims that L1 is undecidable and L2 is decidable, suggesting a many-to-one reduction from the halting problem to L1 and stating that L2 can be determined by counting states in an encoding.
  • Another participant questions the definition of undecidable languages, referencing the Chomsky hierarchy.
  • A subsequent reply clarifies that they mean partially decidable or recursively enumerable languages.
  • Another participant raises the question of whether both languages are regular.

Areas of Agreement / Disagreement

Participants express differing views on the nature of the languages in question, particularly regarding their decidability and regularity. No consensus is reached on these points.

Contextual Notes

There are unresolved definitions and assumptions regarding the terms "undecidable," "partially decidable," and "regular," which may affect the discussion.

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