Properties of algorithms

Question

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!

Answer 1

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.

Answer 2

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.