[Solved]: What does it mean to say that there doesn't exist an algorithm from a TM point of view?

Problem Detail: 

A TM for a recursive language corresponds to our informal notion of an algorithm.

as per Automata Theory, Languages and Computation by Ullman et al. Then there are languages called RE and $L_d$, where there exist TM that halts for accepting strings in the case of RE languages.

This means that we cannot construct a algorithm for RE languages that are not recursive? Then what is the significance of these RE languages from an algorithm point of view.

What confuses me is that for RE language you can construct a TM. So you can construct an algorithm?

Asked By : user5507

Answered By : Raphael

First, note that it is easy to write algorithms that not always halt:

algo(n) {   while ( n % 2 != 0 ) {     n += 2   }   return n } 

It seems that you are asking for a semi-decidable problem of practical relevance. Consider verification of hard- and software. Many interesting properties require logics of higher order for their formulation, and usually satisfiability and/or validity of such formulae is undecidable.

But these logics have proof system, sets of axioms and rules that make up every proof for valid formulae¹. Along these systems, all proofs can be (recursively) enumerated: thus, we can semi-decide many important properties. Using clever heuristics, lots of computational power and human intervention, e.g. by providing key lemmata, many problems can be solved in practice (i.e. for some useful instances) that are theoretically undecidable.

---

1. Beware incomplete proof systems.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/11285

 Ask a Question

 Download Related Notes/Documents