Re: In case you studied the GOTO theoretical language...
From: |-|erc (h_at_r.c)
Date: 01/11/05
- Next message: Mitch Harris: "Winning Ways: NP-hardness question"
- Previous message: H. J. Sander Bruggink: "Re: In case you studied the GOTO theoretical language..."
- In reply to: H. J. Sander Bruggink: "Re: In case you studied the GOTO theoretical language..."
- Next in thread: Rick Decker: "Re: In case you studied the GOTO theoretical language..."
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Date: Tue, 11 Jan 2005 22:13:27 +1000
I am The Truman of Jim Carrey fame. Please help stop me being tortured since April 2002
with constant microwave laser from the Truman satelite splitting my head and tormenting me
and people around me. Not a prank, I am not crazy, The Truman Show made you think that
---------------------------------------------s-o-s-----------------------------------------
"H. J. Sander Bruggink" <sanderbruggink@hotmail.com> wrote in
> 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
Anyone post the language details? Sounds like a busy beaver type problem
so, as has been said, the language would have to be simplistic to set a limit at all,
but we can probably work it out if its very primitive.
Herc
- Next message: Mitch Harris: "Winning Ways: NP-hardness question"
- Previous message: H. J. Sander Bruggink: "Re: In case you studied the GOTO theoretical language..."
- In reply to: H. J. Sander Bruggink: "Re: In case you studied the GOTO theoretical language..."
- Next in thread: Rick Decker: "Re: In case you studied the GOTO theoretical language..."
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Relevant Pages
|
