# HashWalk

Paradigm(s) String-rewriting User:Hakerh400 2022 Unknown Implemented .txt

HashWalk is an esolang invented by User:Hakerh400 in 2022.

## Overview

Let s be the source code and let i be the input (both are arrays of bytes). Let a = 0 be an integer variable and let h = [] be an array of bytes (initially empty).

Perform the following algorithm until the program halts. Calculate the SHA-256 hash of the concatenation of s, h and i, respectively, and assign the result to h. Calculate the first byte of h modulo 3. Depending on the result, do the following:

• If the result is 0, continue
• If the result is 1, if a is 0, terminate the program, otherwise decrement a
• If the result is 2, increment a

Output the number of steps decremented by 1.

## Implementation

Implementation in Node.js:

'use strict';

const crypto = require('crypto');

const run = (src, inp) => {
src = Buffer.from(src);
inp = Buffer.from(inp);

let h = Buffer.alloc(0);
let a = 1n;
let n = -2n;

while(n++, a){
const hash = crypto.createHash('sha256');
hash.update(Buffer.concat([src, h, inp]));
h = hash.digest();
a += [0n, -1n, 1n][h[0] % 3];
}

return n;
};


Note: in this implementation, we initialize local variable a to 1 to simplify the loop condition, but the result is identical to the original algorithm description.

## Example

Program:

aju


For the empty input, it prints 13560111. There is not much of a point to show other examples, because none of them can do anything useful. This is some random example we have chosen.

## Computational class

This language is strictly less powerful than Turing machine. Since SHA-256 gives a byte array of length 32, each program for a given input will either output an integer in the interval ${\displaystyle \left[0,256^{32}-1\right]}$, or loop forever. Moreover, since SHA-256 has a maximum input length, there are only finitely many programs we can write (and each program can take finitely many inputs).