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

From: David Moews (dmoews_at_xraysgi.ims.uconn.edu)
Date: 01/11/05 

Date: 11 Jan 2005 01:46:01 GMT

In article <5d71b560.0501090906.6664744b@posting.google.com>,
THE SWARM MASTER <swarm_master@hotmail.com> 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}).

(In accordance with Swarm Master's later post, I take GOTO to be the
 language G described in
 <http://www.cas.mcmaster.ca/~zucker/Pubs/WOFACS/text.ps> .)

This conjecture is obviously false, since it implies that the output of
program e is bounded by e^(1 + x_1 + ... + x_n). If this were so,
GOTO would not be computation-universal; but GOTO is computation-universal.
For a counterexample to your conjecture, you may therefore take a program which
outputs 2^(2^x1) (or any other fast-growing function.) 

-- 
David Moews                                     dmoews@xraysgi.ims.uconn.edu

Relevant Pages