4
\$\begingroup\$

Synopsis

Your goal is to implement the (asymptotically) fastest growing function within bounded code on a fictional CPU utilizing a quite limited, yet (probably) turing-complete instruction set.

Environment

The CPU utilizes unbounded RAM as well as two registers, the accumulator A and the program counter C, with words consisting of arbitrary integers, such that neither overflows nor underflows are possible. RAM is used to store data as well as code, allowing for self-modifying programs. Each instruction takes one parameter and therefore consists of two words; all instructions of your program are stored sequentially in RAM, starting at address 0. The following instructions can be used, P representing the parameter of the instruction:

Mnemonic Corresponding word Behavior
LOAD P 0 A := RAM[P]; C += 2
SAVE P 1 RAM[P] := A; C += 2
CNST P 2 A := P; C += 2
ADDT P 3 A += RAM[P]; C += 2
NEGA P 4 A := -RAM[P]; C += 2
JUMP P 5 C := P
JMPN P 6 If A <= 0 then C := P else C += 2.
HALT P every other number The program halts.

At each step, the instruction at address C will be executed using the parameter stored at C + 1. Both A and C will be initialized to 0 at the start of a program's execution. The word at -1 is supposed to be your input which can be guaranteed to be non-negative, other words not storing any instructions initially contain 0. The number stored at -2 will be considered your program's output, which must also be positive in all but finitely many cases.

Rules

At the initial state, your program may not occupy more than the first 2048 words each storing integers between -2^64 and 2^64, however, during execution, there are no bounds. Of course, you don't have to write your program in bytecode, using some assembly equivalent or ultimately any other language is fine as well, as long as you provide some rules/translator and show the result does not exceed the given bounds.

Every answer should come with some rough argument showing the program always halts, as well as some approximate lower bound on its growth rate. As the given space might very well suffice for some extremely fast-growing functions, it might be helpful to utilize the slow-/fast-growing hierarchy, as it provides a relatively simple way to compare two answers. Answers will be ranked by lower bounds that can be shown to hold.

\$\endgroup\$
4
  • 6
    \$\begingroup\$ Clearly the 2048 word restriction is intended to prevent unboundedly large programs; however, it fails to do so because the program can still contain unboundedly large integers. One can write some universal interpreter that interprets an unboundedly large integer in the initial state as another program. (This may be what @l4m2 was trying to point out in the sandbox.) \$\endgroup\$ Apr 25, 2021 at 17:57
  • \$\begingroup\$ @AndersKaseorg Oh, true. I initially thought of this but then forgot to include it in the question, thanks. \$\endgroup\$
    – univalence
    Apr 25, 2021 at 18:30
  • 3
    \$\begingroup\$ 2048 words is absurdly large (it's probably enough for a Turing machine with 1900 states, or for over 100 kilobits of binary lambda calculus). \$\endgroup\$ Apr 26, 2021 at 4:32
  • \$\begingroup\$ This is huge. Once understanding how to code in this strange instruction set this should blow up big. I've worked out how to do call/return already; working on recursion. \$\endgroup\$
    – Joshua
    Jul 1, 2021 at 17:57

1 Answer 1

2
\$\begingroup\$

x=>x*2^x, 29 words

I use only some constants in addition to constant valued pointers, which you can replace into their values for a true program, along with C-style comments. I believe with enough patience and macros, any function ala "Largest Number Printable" should be implementable.

// constant definitions
// do not take any space of their own
IN = -1
OUT = -2
NULL = 0

/*
PROGRAM x => x*2^x
*/

LOAD IN         // VALUE = in; COUNTER = in;
SAVE VALUE      //
SAVE COUNTER    //

loop:           // do {

LOAD VALUE      // VALUE *= 2;
SAVE (INC_BY+1) //
INC_BY: ADDT NULL //
SAVE VALUE      //

LOAD COUNTER    // COUNTER--;
ADDT NEGONE     //
SAVE COUNTER    //

JMPN end        // if (COUNTER<=0) break;
JUMP loop       // } while (true)
end:            //

LOAD VALUE      // return VALUE;
SAVE OUT        //
NEGONE: HALT 0  // HALT is -1

COUNTER: NULL   // var COUNTER, VALUE;
VALUE: NULL     // these variables are both trailing 0s, so can be ignored as the tape defaults to 0.

Also push and pop, which I think much helps a turning completeness proof.

/*
MACRO stack_manipulation_push_a
14 words
*/
STACKPTR: -2    // put outside of codespace.
CNST 01337      // assume A has the value you want, in this cse, 1337 in base 8

SAVE 0          // probably not being used.
LOAD STACKPTR   // move the stack pointer down to the next open free space.
ADDT NEGONE     //
SAVE STACKPTR   //
SAVE (EAT_ME+1) // put the fresh stack position into the save command, basically dereference.
LOAD 0          // load back in value to be saved
EAT_ME: SAVE NULL // save the orignal A value to where stackptr points

/*
MACRO stack_manipulation_pop_a
16 words
*/
LOAD STACKPTR       // *0 = *STACKPTR;
SAVE (EAT_ME+1)     //
DRINK_ME: LOAD NULL //
SAVE 0              //
LOAD STACKPTR       // move the stack pointer up to the last space.
ADDT 1              //
SAVE STACKPTR       //
LOAD 0              // put the value back in A
\$\endgroup\$
2
  • \$\begingroup\$ This is exactly the sort of answer I was interested in! Just a very tiny issue: technically, ADDT -1 needs to be changed since ADDT reads from RAM and doesn't directly take constant values. The stack functionality seems intriguing as well \$\endgroup\$
    – univalence
    Jul 3, 2022 at 9:35
  • \$\begingroup\$ @univalence Thanks for pointing that out. Since halt can be any value that isn't an opcode, I just called it -1 so that it doesn't take any extra bytes. \$\endgroup\$ Jul 4, 2022 at 16:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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