(adsbygoogle = window.adsbygoogle || []).push({}); 1. The problem statement, all variables and given/known data

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?

2. Relevant equations

3. 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 Forums - The Fusion of Science and Community**

# Turing Machines & Undecidability

Have something to add?

- Similar discussions for: Turing Machines & Undecidability

Loading...

**Physics Forums - The Fusion of Science and Community**