2
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

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.
$\endgroup$
  • $\begingroup$ But what about Posts Correspondance Problem.We can write an algorithm which tries all the possibilities and halt. It seems something similar to TSP. But PCP is considered to be an undecidable problem? $\endgroup$ – user5507 Apr 14 '13 at 15:37
  • $\begingroup$ @user5507 Because the solution can be arbitrarily long: you can not try all solution candidates in finite time. I suggest you look at the proof for the fact that PCP is undecidable. $\endgroup$ – Raphael Apr 14 '13 at 15:54
2
$\begingroup$

Yes. RE is the set of languages which you can construct an accepting TM for. Recursive languages are those where you can construct a TM that always halts. There are some functions which we can build TMs to accept, but those machines always have infinite time complexity. Also note, that the diagonal language Ld is Not in RE. It is a problem outside RE.

$\endgroup$
  • $\begingroup$ How you could relate this to some real world problems like TSP .. $\endgroup$ – user5507 Apr 13 '13 at 15:21
  • 1
    $\begingroup$ TSP is a recursive problem. Be careful not to confuse what isn't computable, like the diagonal language, with what isn't efficiently computable, like TSP or SAT. In terms of real word problems, one of the best examples is the halting problem: take in a piece of code and its input, and return true if it halts and false if it enters an infinite loop. This is in RE, but is not recursive, since there's no algorithm that solves it which itself never enters an infinite loop. $\endgroup$ – jmite Apr 13 '13 at 19:04
  • 1
    $\begingroup$ It's the same thing with automated debugging. There's no algorithm which takes in an arbitrary specification, and a piece of code, and tells if the code meets that specification. (If there were, it could be used to solve the halting problem). $\endgroup$ – jmite Apr 13 '13 at 19:05
  • $\begingroup$ PCP looks related to TSP but it is undecidable. We can search for all the possibilities to find an answer $\endgroup$ – user5507 Apr 14 '13 at 15:35
  • 1
    $\begingroup$ The difference is that TSP has a large but finite search space, where PCP has an infinite space. $\endgroup$ – jmite Apr 14 '13 at 16:12
0
$\begingroup$

the word "algorithm" is very old, about a millenium old, dating to the beginning of the 2nd millenium ie the year ~1000s & also has a similar etymology to the word "algebra". it was originally based on algebra techniques or problems of integer arithmetic such as multiplication or division.

TMs were invented in 1936 by Turing. the best way to understand it is that computer science has formally defined "algorithm" to refer to recursive languages that always halt on all inputs. RE languages can be modelled by TMs which dont halt on some inputs but are not technically "algorithms" for this reason. so yes if you have an idea that TMs in general somehow model "algorithms", that will be confusing and basically incorrect.

$\endgroup$
  • $\begingroup$ in other words the TM concept is more general than the algorithm concept in particular with RE language. $\endgroup$ – vzn Apr 14 '13 at 14:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.