# Turing Machines & Undecidability

by crazyautomata
Tags: machines, turing, undecidability
 P: 3 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!
 P: 127 What do you mean by undecible language, the chomsky hiearchy for languages is given as follows: http://en.wikipedia.org/wiki/Chomsky_hierarchy.
 P: 3 I mean partially decidable or recursively enumerable.
P: 127

## Turing Machines & Undecidability

Aren't they both regular?

 Related Discussions Calculus & Beyond Homework 4 General Discussion 1 Set Theory, Logic, Probability, Statistics 4 Calculus 5