3
$\begingroup$

Is there any way to find out how to replace for/if for elementary recursive algorithms? I know that primitive recursive functions cannot basically eliminate "for", but for elementary recursive functions, there must be a way to convert the program into ones that do not have for/if/while and so on (which is elementary recursive).

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ If you assume that you are given a program (a TM) and you are asking whether there is an equivalent program without for/if, then it is clearly undecidable (e.g. since it's a nontrivial semantic property). If you are referring to a promise problem, where you are given an elementary recursive function, my guess is that it would remain uncomputable. $\endgroup$
    – Shaull
    Commented Apr 28, 2013 at 7:31
  • $\begingroup$ @Shaull I know that Entscheidungsproblem is unsolvable, but this only means there does not exist a single program that shows whether two function results in the same result... This case is only restricted those that are known to have elementary recursive algorithm/function. (Complexity class: elementary) $\endgroup$
    – Pros
    Commented Apr 28, 2013 at 9:46
  • $\begingroup$ actually I was thinking about this undecidable promise problem, which motivates me to believe that your problem may also be undecidable. But as I said - it's only a guess. $\endgroup$
    – Shaull
    Commented Apr 28, 2013 at 14:23
  • $\begingroup$ Could you be more precise as to what is left, rather than what you remove. It is a rather unusual way to define a problem. Else give precise reference to what you had to start with. I mean that for me, for and while are very similar. So is repeat. Do you keep repeat? $\endgroup$
    – babou
    Commented Aug 10, 2015 at 15:44
  • $\begingroup$ What is meant by "elementary recursive"? Primitive recursive? Deciding weather a program is writable in a primitive recursive fashion is undecidable (proof there are functions from natural numbers to natural numbers which are not primitive recursive and there are those that are, apply rice's theorem). This applies to any complexity class btw. However if you are asking weather you can replace for/if statements with recursion in general then the answer is yes, always, because both are turing complete. $\endgroup$
    – Jake
    Commented Aug 10, 2015 at 17:17

1 Answer 1

Reset to default
2
$\begingroup$

For/if/while are the main blocks that will check for a condition. Since a recursive function will keep recurring until a condition is met, you will at least need an if statement to tell the function when to return. Otherwise, you will essentially be stuck in an infinite loop.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Welcome to Computer Science Stack Exchange. Please read cs.stackexchange.com/tour, if you have not yet done so. $\endgroup$
    – babou
    Commented Aug 10, 2015 at 16:05
  • 1
    $\begingroup$ This is pretty much true. At least if you extend 'if statement' to any kind of branching this is true. $\endgroup$
    – Jake
    Commented Aug 10, 2015 at 16:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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