Turing Machines & Undecidability


by crazyautomata
Tags: machines, turing, undecidability
crazyautomata
crazyautomata is offline
#1
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 Phys.org
Cougars' diverse diet helped them survive the Pleistocene mass extinction
Cyber risks can cause disruption on scale of 2008 crisis, study says
Mantis shrimp stronger than airplanes
Max.Planck
Max.Planck is offline
#2
Mar13-12, 05:00 PM
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.
crazyautomata
crazyautomata is offline
#3
Mar13-12, 08:15 PM
P: 3
I mean partially decidable or recursively enumerable.

Max.Planck
Max.Planck is offline
#4
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