Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have 2 questions.

1.Let's have an algorithm

input a;
x ← -7;
y ← a;
while x $<$ y do
x ← x+5;
y ← 2·x+y-6;
done

Question: What is the greatest "stopping" input number ($a$) (number for which will the algorithm stop). $a \in \mathbb Z$

2.Let's have an recursive function

FUNCTION funkceG(x):
if x$<$14 then
r ← funkceG(57−4·x)−7;
else
r ← 44;
fi
RETURN r;

Will the function end for all $x$ ? Or is there $x$ for which will the function never end? Where $x \in \mathbb N$

I would like to ask for a how-to, is there a "simple" way to solve this? I don't need answer exactly to these questions, how-to would be awesome. Thanks!

share|improve this question
2  
Ther is no systematic procedure that will always tell you something correct about which inputs will make a given algorithm terminate. So your only hope is either (a) to restrict yourself to a precisely specified subset of all algorithms you want to deal with, and for which you can concoct a solution procedure, or (b) to apply human intelligence, understand what the algorithm does, and reason case-by-case from there. –  Henning Makholm Dec 15 '12 at 18:18
add comment

2 Answers 2

up vote 3 down vote accepted

For the first, $x$ runs through $-2, 3,8,13,\ldots$. $y$ then runs through $a-10, a-10, a, a+20, \ldots$ You stop if any of these $x$'s are greater than or equal to the corresponding $y$. So you stop the first time if $a \le 8$. Eventually $y$ grows faster than $x$, so if you go to far you will never stop.

For the second, you terminate if $x \ge 14$. I would start by making a spreadsheet and trying a number of inputs to see what happens. My experiments convince me that it always terminates quickly, so you should be able to trace a couple generations of calls and see that it does.

share|improve this answer
    
On the second one, I was thinking about a graph,e.g. $f(y)=(57-4x)$. Do you think is it possible to solve that somehow that way? –  Noturab Dec 15 '12 at 18:59
add comment

Henning Makholm's comment deserves an answer of its own.

This question -- find a set of instructions to determine whether a given procedure will halt or not -- have been proven to be unsolvable[a].

It's called the "halting problem" and was proven unsolvable by Gödel in 1931 (under a different guise) and by Turing in 1936.

The intuition is easy. Suppose I gave you an algorithm $A$ that reads in a procedure and an input and returns "yes" if the procedure halts on that input, "no" otherwise.

Then I'll construct the following algorithm $B$:

  1. Run algorithm $A$ on myself.
  2. If it says "yes", enter an infinite loop.
  3. If it says "no", halt.

We have a logical contradiction -- if $B$ halts, then it enters an infinite loop; and if it enters an infinite loop, it halts. So we must not be able to construct this algorithm $A$ in the first place.

--

[a] Assuming the Church-Turing Thesis: That there is not some more "powerful" model of computation out there undiscovered.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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