HashWalk

HashWalk

Paradigm(s)	String-rewriting
Designed by	User:Hakerh400
Appeared in	2022
Computational class	Unknown
Major implementations	Implemented
File extension(s)	.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 $\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).