Register to reply

Turing Machines & Undecidability

by crazyautomata
Tags: machines, turing, undecidability
Share this thread:
Mar12-12, 08:07 AM
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!
Phys.Org News Partner Science news on
Wildfires and other burns play bigger role in climate change, professor finds
SR Labs research to expose BadUSB next week in Vegas
New study advances 'DNA revolution,' tells butterflies' evolutionary history
Mar13-12, 05:00 PM
P: 127
What do you mean by undecible language, the chomsky hiearchy for languages is given as follows:
Mar13-12, 08:15 PM
P: 3
I mean partially decidable or recursively enumerable.

Mar14-12, 04:45 AM
P: 127
Turing Machines & Undecidability

Aren't they both regular?

Register to reply

Related Discussions
Turing Machines Calculus & Beyond Homework 4
Conciousness and Turing undecidability General Discussion 1
Uncountably Many Turing Machines Set Theory, Logic, Probability, Statistics 4
Turing machines Calculus 5