Wednesday, May 15, 2013
Recursively enumerable vs. regular expressions
These two terms, recursively enumerable and regular expressions are both mentioned when speaking of computational theory in computer science. I think thy need new terms like renum for recursively renumerable and regex for regular expressions. These two terms are much more understandable than r.e. for both of them. But now I have also learned a tidbit about intractable languages. I wonder if they are contain exponential solutions. As in are problems which can be solved in exponential time, are they considered intractable languages?