Re: In case you studied the GOTO theoretical language...

From: H. J. Sander Bruggink (sanderbruggink_at_hotmail.com)
Date: 01/11/05 

Date: Tue, 11 Jan 2005 12:05:03 +0100

THE SWARM MASTER wrote:
> Greetings. I have the following conjecture about the GOTO-programs:
>
> Let n be the greatest integer such that X_n appears at least in one
> instruction of a given GOTO-program P, and let e be the code of such a
> program P. Therefore, if the program P eventually halts on the input
> (x_1, ..., x_n), then M instructions have been executed, with M <=
> e^(1 + SUM_(i=1)^{n} {x_i}), that is, there is a computation of length
> l <= e^(1 + SUM_(i=1)^{n} {x_i}).
>
> Could you prove or disprove this conjecture? I have tried
> unsuccessful...
>
> As usual, thanks to all posts in advance.

I haven't studied this GOTO language thoroughly, but I think
your conjecture is not true. This goto language looks like
it's Turing complete, and thus functions can be written in it
which increase much faster than only exponentionentially.
Since the language has only increments and decrements,
it requires that much more instructions are executed than the
upper bound you gave.

groente
--Sander

Loading