Contact Us!
CoCalc Logo Icon
StoreFeaturesDocsShareSupportNewsAboutSign UpSign In

Real-time collaboration for Jupyter Notebooks, Linux Terminals, LaTeX, VS Code, R IDE, and more,
all in one place. Commercial Alternative to JupyterHub.

| Download

This file is an interpreter for the tiny programming language 1# used in my classes on theory of computation at Indiana University. For more on 1# and the class, see https://iulg.sitehost.iu.edu/trm. Right now, this is just for my students. But if the move to Cocalc turns out well, I might expand this to cover the basics of computability theory.

Views: 69
Image: ubuntu2004
Tweet
Share
Share
Kernel: Python 3 (system-wide)

Getting stared with 1#

This notebook is a new interpreter for 1# written for the Jupyter notebook. It is under development for use in my IU class M584 in this (current) fall 2022 semester. The main source on 1# is the web text available at https://iulg.sitehost.iu.edu/trm. If this notebook works out, then the plan is to convert all of the material on that web site to this format, and to make it available on Cocalc. To start, click on the box below and then press shift-enter.

import pandas as pd
from IPython.display import display
import numpy as np


def program_checker(str):
    m = len(str)
    x1 = str[m - 1] == '#'
    x2 = all((str[i] == '1' or str[i] == '#') for i in range(m))
    x3 = (str.find('######') == -1)
    if (x1 and x2 and x3):
        flag = True
    else:
        flag = False
    return (flag)


def preparse(xstr):
    b = xstr.string.find('#1')
    xstr.remainders = xstr.remainders + [xstr.string[:(b + 1)]]
    xstr.string = xstr.string[(b + 1):]
    return (xstr)


class Augmented:
    def __init__(self, string, remainders):
        self.string = string
        self.remainders = remainders

class Snapshot:
    def __init__(self, instr_number, regs):
        self.instr_number = instr_number
        self.regs = regs


def parse(y):
    tempx = Augmented(y, [])
    while tempx.string.find('#1') >= 0:
        tempx = preparse(tempx)
    return (tempx.remainders + [tempx.string])


def prog_to_string(p):
    return (''.join(p))


def instruction_type(instruction):
    if instruction[-2:] == '1#':
        return ('add1')
    if instruction[-3:] == '1##':
        return ('add#')
    if instruction[-4:] == '1###':
        return ('forward')
    if instruction[-5:] == '1####':
        return ('backward')
    if instruction[-6:] == '1#####':
        return ('cases')


def tail(list):
    return (list[1:])


def one_step(p, snapshot): # p is parsed
    i = snapshot.instr_number
    r = snapshot.regs
    instruction = p[-1 + i]
    if verbose == True:
        print('Step ' + str(step_number) + ':')
        print('Execute instruction ' + str(i) + ':' + " " +
              instruction_gloss(instruction,i-1)
              + '.')
        if instruction_type(instruction)=='cases':
            billy= len(instruction) - 5
            if snapshot.regs[billy-1] == "":
                print('The register is empty, so we go ahead one instruction.')
            elif snapshot.regs[billy-1][0] == "1":
                print('The first symbol in that register is 1,' +
                      ' so we delete that symbol and go forward two instructions.')
            elif snapshot.regs[billy-1][0] == "#":
                print('The first symbol in that register is #,' +
                      ' so we delete that symbol and go forward three instructions.')
    t = instruction_type(instruction)
    if t == 'add1':
        snapshot.instr_number = 1 + snapshot.instr_number
        l = len(instruction)
        reg = len(instruction[:(l - 1)])
        snapshot.regs[reg - 1] = snapshot.regs[reg - 1] + '1'
    if t == 'add#':
        snapshot.instr_number = 1 + snapshot.instr_number
        l = len(instruction)
        reg = len(instruction[:(l - 2)])
        snapshot.regs[reg - 1] = snapshot.regs[reg - 1] + '#'
    if t == 'forward':
        l = len(instruction)
        offset = len(instruction[:(l - 3)])
        snapshot.instr_number = offset + snapshot.instr_number
    if t == 'backward':
        l = len(instruction)
        offset = len(instruction[:(l - 4)])
        snapshot.instr_number = (-offset) + snapshot.instr_number
    if t == 'cases':
        l = len(instruction)
        reg = len(instruction[:(l - 5)])
        if snapshot.regs[reg - 1] == '':
            snapshot.instr_number = 1 + snapshot.instr_number
        elif snapshot.regs[reg - 1][0] == '1':
            snapshot.instr_number = 2 + snapshot.instr_number
            snapshot.regs[reg - 1] = tail(snapshot.regs[reg - 1])
        elif snapshot.regs[reg - 1][0] == '#':
            snapshot.instr_number = 3 + snapshot.instr_number
            snapshot.regs[reg - 1] = tail(snapshot.regs[reg - 1])
    if verbose == True and snapshot.instr_number <= len(p) and 0 < snapshot.instr_number:
        regdf = pd.DataFrame([[str(n+1),snapshot.regs[n]] for n in range(len(snapshot.regs))],columns=["R","contents"])
        def make_pretty(styler):
             styler.set_properties(**{'background-color': '#FFFFCC'})
             styler.set_properties(**{'text-align': 'left'})
             styler.set_caption("after step " + str(step_number))
             styler.hide(axis='index')
             return styler
        display(regdf.style.pipe(make_pretty))
    return (snapshot)


def number_help(instr):
    if instruction_type(instr) == 'add1':
        return (len(instr) - 1)
    if instruction_type(instr) == 'add#':
        return (len(instr) - 2)
    if instruction_type(instr) == 'cases':
        return (len(instr)-5)
    else:
        return (0)


def max_register(p):
    return (max([number_help(instr) for instr in parse(p)]))


def pad(p, register_inputs):
    n = len(register_inputs)
    m = max_register(p)
    extras = ['' for x in range(m - n)]
    bigger = register_inputs + extras
    return (bigger)


def step_by_step(word_prog, register_inputs):
    word_prog = word_prog.replace(" ", "")
    register_inputs = [word.replace(" ", "") for word in register_inputs]
    if program_checker(word_prog) == False:
        print('The input ' + word_prog + ' is not a valid 1# program.')
        print('It is not the concatenation of a sequence of instructions in the language.')
        print('So what you are asking for is undefined.')
    else:
        print('First, here is the program:')
        parse_explain(word_prog)
        print()
        global step_number
        step_number = 1
        global verbose
        verbose = True
        regs = pad(word_prog, register_inputs)
        prog = parse(word_prog)
        snap = Snapshot(1, regs)
        print('The computation starts with the register contents shown below.')
        print('The registers include those those which you entered as part of the input')
        print('and also others mentioned in the input program.')
        regdf = pd.DataFrame([[str(n+1),snap.regs[n]] for n in range(len(snap.regs))],columns=["R","contents"])
        def make_pretty(styler):
             styler.set_properties(**{'background-color': '#FFFFCC'})
             styler.set_properties(**{'text-align': 'left'})
             styler.set_caption("at the start")
             styler.hide(axis='index')
             return styler
        display(regdf.style.pipe(make_pretty))
        print()
        N = len(prog)
        while (snap.instr_number < N + 1) and (snap.instr_number >=0):
            snap = one_step(prog, snap)
            step_number = step_number + 1
        if snap.instr_number <= 0:
            print(
                'The computation has not halted properly ' +
                'because the control went above instruction 1 of the program.'
            )
        elif (snap.instr_number == (N + 1)) and all(
                snap.regs[i] == ""
                for i in range(1, len(snap.regs))):
            print(
                'The computation then halts properly because' +
                ' the control is just below the last line of the program,'
            )
            print('and because all registers other than R1 are empty.')
            if snap.regs[0] == "":
                print('The output is the empty word.')
            else:
                print('The output is ' + snap.regs[0] + '.')
        else:
            print('This computation does not halt.')
            if snap.instr_number != N + 1:
                print('This is because the program has ' + str(len(prog)) +
                  ' instructions, and control at the end is not one line ' +
                   ' below the bottom of the program.')
                print()
            else:
                not_blank = [
                    i + 1 for i in range(1, len(snap.regs))
                    if snap.regs[i] != ""
                ]
                print('Here is the list of registers whose contents ' +
                      'are not empty at this point, other than R1:' +
                      str(not_blank) + '.')
                print('The register contents at the end are shown above.')


def onesharp(word_prog, register_inputs):
    global verbose
    verbose = False
    word_prog = word_prog.replace(" ", "")
    if program_checker(word_prog) == False:
        print('The input ' + word_prog + ' is not a valid 1# program.')
        print('It is not the concatenation of a sequence of instructions in the language.')
        print('So what you are asking for is undefined.')
    else:
        register_inputs = [word.replace(" ", "") for word in register_inputs]
        regs = pad(word_prog, register_inputs)
        prog = parse(word_prog.replace(" ", ""))
        snap = Snapshot(1, regs)
        N = len(prog)
        global step_number
        step_number = 1
        while snap.instr_number < N + 1:
            snap = one_step(prog, snap)
            step_number = step_number+1
        if (snap.instr_number == (N + 1)) and all(
                snap.regs[i] == "" for i in range(1, len(snap.regs))):
            return ((snap.regs)[0])
        else:
            print("This is undefined.")
            print("The register contents at the end are shown below.")
            regdf = pd.DataFrame([[str(n+1),snap.regs[n]] for n in range(len(snap.regs))],columns=["R","contents"])
            def make_pretty(styler):
                #styler.set_properties(**{'background-color': 'black',
                           #'color': 'lawngreen',
                           #'border-color': 'white'})
                styler.set_properties(**{'background-color': '#FFFFCC'})
                styler.set_properties(**{'text-align': 'left'})
                styler.set_caption("after step " + str(step_number))
                styler.hide(axis='index')
                return styler
            display(regdf.style.pipe(make_pretty))


def instruction_gloss(instr,line):
    if instruction_type(instr) == 'add1':
        return ('add 1 to R' + str(len(instr) - 1))
    if instruction_type(instr) == 'add#':
        return ('add # to R' + str(len(instr) - 2))
    if instruction_type(instr) == 'forward':
        w = len(instr) - 3
        return ('go forward ' + str(w) + ' to instruction ' + str(w+line+1))
    if instruction_type(instr) == 'backward':
        w = len(instr) - 4
        return ('go backward ' + str(w) + ' to instruction ' + str(line - w+1))
    if instruction_type(instr) == 'cases':
        return ('cases on R' + str(len(instr) - 5))

def expanded(gorp):
    pgorp = parse(gorp)
    wwgorp = [[pgorp[x],instruction_gloss(pgorp[x],x)] for x in range(len(pgorp))]
    return(wwgorp)

def parse_explain(prog):
    df = pd.DataFrame(expanded(prog),
                      columns=["instruction", 'explanation'])
    df.index = np.arange(1, len(df) + 1)
    def make_pretty(styler):
                styler.set_properties(**{'background-color': '#C9DFEC'})
                styler.set_properties(**{'text-align': 'left'})
                return styler
    display(df.style.pipe(make_pretty))
    #display(df)

clear_1 = '1#####111###11####111####'

move_2_1 = '11#####111111###111###1##1111####1#111111####'

copy_1_2_3 = '1#####11111111###1111###11##111##11111####11#111#11111111####111#####111111###111###1##1111####1#111111####'

length = '1#####1111111###11####11#1#####111###111111####111####11#####111111###111###1##1111####1#111111####'

write = '1#####111111111###11111###11#11##11##111111####11#11##111111111####11#####111111###111###1##1111####1#111111####'

diag = '1#####11111111111###111111###11##111#111##111##1111111####11#111#111##1111####111#####111111###111###1##1111####1#11####11#####111111###111###1##1111####1#11####'

self = '1#1##1##1##1##1##1#1#1#1#1#1#1#1#1#1#1#1##1##1##1#1#1#1#1#1#1##1##1##1#1#1##1##1#1#1#1##1#1#1#1##1##1#1#1#1##1##1#1#1#1#1#1#1#1##1##1##1##1#1#1##1#1#1#1##1#1#1#1##1##1#1#1#1#1##1##1##1##1#1#1#1##1##1##1##1##1#1#1#1#1#1#1##1##1##1#1#1#1##1##1##1#1##1##1#1#1#1#1##1##1##1##1#1##1#1#1##1##1##1##1#1#1##1##1##1##1##1#1#1#1#1#1#1##1##1##1#1#1#1##1##1##1#1##1##1#1#1#1#1##1##1##1##1#1##1#1#1##1##1##1##1#####11111111111###111111###11##111#111##111##1111111####11#111#111##1111####111#####111111###111###1##1111####1#11####11#####111111###111###1##1111####1#11####'

multiply = '111##1111##11#####11111111###1111###11111##111111##11111####11111#111111#11111111####111111#####111111###111###11##1111####11#111111####111#####11111111###1111###111111##1111111##11111####111111#1111111#11111111####1111111#####111111###111###111##1111####111#111111####11111#####111111###111111111###111111#####11111111111###1111111111###111111####111111#####111111111111111###111111###11111###111111#####111###1111111111111####1###11111#####111###11####111####111111#####1111###11####111####11111#11111#####111###1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111###1#1#####11111111###1111###11111##111111##11111####11111#111111#11111111####111111#####111111###111###1##1111####1#111111####1111#####111111###111###111111##1111####111111#111111####11111#####111###111111###111111111###111111#####11111111111111111111111111111111111###11111111111111111111111111###111111111111111111111111111###111111#####11111111111111111111111###1111111111111111111111111111###111111111111111111111###111111#####111111111111111111111###111111111111111111###1111111111111111111###11111#####111###111111###111111111###111111#####11111111111###1111111111111111###111111111###111111#####1111111111111###1111111111###11111111111###111111#####111###11111111###1###1111111#111111111111111111111111111111111####1111111##11111111111111111111111111111111111####1111111#111111111111111111111####1111111##11111111111111111111111####1###1111111#####111111###111###11111##1111####11111#111111####11111#####111111###111###1111##1111####1111#111111####111#####1111111111111###1111111111###11111#111#####111111###111###11111##1111####11111#111111####1111###11111##1111111111111####11111#11111#####111111###111###111##1111####111#111111####1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111####1#####111###11####111####11#####111###11####111####111#####111###11####111####1111#####111111###111###1##1111####1#111111####'

universal = '1#####1###11###11####111111#1#####111###111111###1111111###11111#####1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111###1###1####111#111111111####111##1#####1111###11###11111###111#11111#####1111111111111111111111111111111111111111111111###111111111###111##1#####1111###11###11111###111#11111#####1111111111111111111111111111111111111###111111111###111##1#####1111###11###11111###111#11111#####1111111111111111111111111111111111111111111111###111111111###111##1#####1111###11###11111###111#11111#####111111111111111111111111111111111111111111111111111111###111111111###111##1#####1111###11###11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111###111#11111#####1111111111###1###111#####111111###111###1111##1111####1111#111111####11111111111111111111111111111111111111111111111111111111111111####111#####1###11###1111###11111#1111#111111####11111##1111##111#####1111111###1111###1111##11111##11111####1111#1111111####111111111111111111111111111111111111111111111111111111111111111111111111111###111#####1###11###11111###11111#1111#111111#1111111####1111##111#####111111###111###1111##1111####1111#111111####11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111####111#####1###11###1111###1111#11111#111111####11111#11111#1111##111#####111111###111###1111##1111####1111#111111####11111#####11111111###11###1###111111#####111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111###1###1###11111111####111111#####1111###111#11111#1111####111#####111###111111#111####1#####111111###111###111##1111####111#111111####1111#####111111###111###1##1111####1#111111####111#####111111###111###1##1111####1#111111####111111111111111111111111111111111111111111111111111111111####11#####111###11111###111111111111###11##11##111111####111#11#####1###111###111##11###111#11111111111111####111##11#####11111111111111111111111111111111111111111111111111111111111111111111###1###111##11111#####1###1111111111111111111111####11111#####1111111111111111111111111111###111111111111111111111111111###11111#####111###11###111111111111111111111111111111111111111111111###11#####111111111111111111###111111111###111#11#####1###1###111#111##111##111111111111111111111111111111111111111111111111111111111###111#11#####1###111###111##11###111#111111111111111111####111#111#1111111111111111111111111111111111111111111111###11#####111111111111111111###111111111###111#11#####1###1###111##111##111##11111111111111111111111111111111111###111#11#####1###111###111##11###111#111111111111111111####111#111##111111111111111111111111###11111#####1###1###11111#####1###1###11#####11111111111111111111111###111###111##1111111111111###11#####1###11111###1###11111#111111#111111###11111#11111#111111#111111#1###11#####111111###111###111##1111####111#111111####111#####111111###111###11##1111####11#111111####1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111####11#####1###1###11#####1###1###11#####11111111111111###11###11111111###11#####1###111###1#11111111####1##1111111111####11#####111###11####111####111111#####11###11####1111#####111###11####111####'

To load the program, click above and press shift-enter.

Hopefully you have loaded in the Python programs that are going to run 1#.

Next, enter the cell below by clicking on it and then pressing shift-enter together. The output is a step-by-step explanation of a computation of the program 1#11#####1###1### when started with the word 1#1 in R1,and # in R2.

parse_explain(clear_1)

step_by_step(clear_1,['1#1','#'])
First, here is the program:
The computation starts with the register contents shown below. The registers include those those which you entered as part of the input and also others mentioned in the input program.
Step 1: Execute instruction 1: cases on R1. The first symbol in that register is 1, so we delete that symbol and go forward two instructions.
Step 2: Execute instruction 3: go backward 2 to instruction 1.
Step 3: Execute instruction 1: cases on R1. The first symbol in that register is #, so we delete that symbol and go forward three instructions.
Step 4: Execute instruction 4: go backward 3 to instruction 1.
Step 5: Execute instruction 1: cases on R1. The first symbol in that register is 1, so we delete that symbol and go forward two instructions.
Step 6: Execute instruction 3: go backward 2 to instruction 1.
Step 7: Execute instruction 1: cases on R1. The register is empty, so we go ahead one instruction.
Step 8: Execute instruction 2: go forward 3 to instruction 5. This computation does not halt. Here is the list of registers whose contents are not empty at this point, other than R1:[2]. The register contents at the end are shown above.

The last computation started with two inputs. Try changing those inputs to see what happens. As practice with the definition of halt, you might try yourself to predict what will happen before running it. You can add the symbols 1 or #, and you also can delete symbols. But you should not delete the quote marks. Also, you can change the program the same way. The idea is that you should explore this function step_by_step by trying it out on simple inputs. Here is another computation, with more explanation of the notation.

move_2_1
'11#####111111###111###1##1111####1#111111####'
step_by_step('1#11#####1###1###',['1#1','1111111#',])
First, here is the program:
The computation starts with the register contents shown below. The registers include those those which you entered as part of the input and also others mentioned in the input program.
Step 1: Execute instruction 1: add 1 to R1.
Step 2: Execute instruction 2: cases on R2. The first symbol in that register is 1, so we delete that symbol and go forward two instructions.
Step 3: Execute instruction 4: go forward 1 to instruction 5. This computation does not halt. Here is the list of registers whose contents are not empty at this point, other than R1:[2]. The register contents at the end are shown above.

Here is an explanation of the form of the command called "step_by_step" that we have been using.

The first argument could be a 1# program surrounded by single quotes or double-quotes. If you use single quotes, you need to be sure to use the correct ones; on my screen they look straight, not slanted. You could also use a concatenation of quoted expressions (see below). But if you forget the quotes, you will get an error because the Python program that is running all of this will balk at 1# expressions without quotes around them.

In addition, you can name expressions ahead of time using assignment statements like

p = '1#'

and then write step_by_step(p,['11']), for example.

The program step_by_step begins with a parse of your program, and so if you input a word that is not a sequence of 1# expressions, it will stop without further ado.

The second argument to "step_by_step" is a list of words. A list in Python is enclosed by square brackets [ and ], not by parentheses. The words that go in the list are used in R1, R2, . . . in that order. It is understood that any register not represented by any input starts with the empty string. You can also represent the empty string by ' '. And the empty list of registers is denoted by two square brackets with nothing inside, [ ].

All in all, the examples below show different formats for the input to our function step_by_step.

p= '1#'
q = '#1'
step_by_step(p,[q,q,p])

step_by_step(p+q+p,[])
# This is a comment.
# the symbol + is used for concatenation of strings
# and since p and q are strings, 
# we can concatenate them

So far in this notebook, we have only seen the function step_by_step. If we want to run things "in one fell swoop", we could use the function onesharp(p,[r1,r2, . . ., rn]). It also takes two arguments, the first a program and the second a (possibly-empty) sequence of input words.

clear_1 = '1##### 111### 11#### 111####'
onesharp(clear_1,['1111###1111##########'])
# You can also run the line above slowly by running
# step_by_step(clear_1,['1111###1111##########'])
''
diag
'1#####11111111111###111111###11##111#111##111##1111111####11#111#111##1111####111#####111111###111###1##1111####1#11####11#####111111###111###1##1111####1#11####'


onesharp(multiply,['1#1','1#1'])
'1##11'
diag
'1#####11111111111###111111###11##111#111##111##1111111####11#111#111##1111####111#####111111###111###1##1111####1#11####11#####111111###111###1##1111####1#11####'
onesharp(write, ['1111###1'])
'1#1#1#1#1##1##1##1#'
onesharp(onesharp(write, ['1111###1']),[])
'1111###1'
parse_explain(write)

step_by_step(write,['11#'])
First, here is the program:
The computation starts with the register contents shown below. The registers include those those which you entered as part of the input and also others mentioned in the input program.
Step 1: Execute instruction 1: cases on R1. The first symbol in that register is 1, so we delete that symbol and go forward two instructions.
Step 2: Execute instruction 3: go forward 5 to instruction 8.
Step 3: Execute instruction 8: add 1 to R2.
Step 4: Execute instruction 9: add # to R2.
Step 5: Execute instruction 10: go backward 9 to instruction 1.
Step 6: Execute instruction 1: cases on R1. The first symbol in that register is 1, so we delete that symbol and go forward two instructions.
Step 7: Execute instruction 3: go forward 5 to instruction 8.
Step 8: Execute instruction 8: add 1 to R2.
Step 9: Execute instruction 9: add # to R2.
Step 10: Execute instruction 10: go backward 9 to instruction 1.
Step 11: Execute instruction 1: cases on R1. The first symbol in that register is #, so we delete that symbol and go forward three instructions.
Step 12: Execute instruction 4: add 1 to R2.
Step 13: Execute instruction 5: add # to R2.
Step 14: Execute instruction 6: add # to R2.
Step 15: Execute instruction 7: go backward 6 to instruction 1.
Step 16: Execute instruction 1: cases on R1. The register is empty, so we go ahead one instruction.
Step 17: Execute instruction 2: go forward 9 to instruction 11.
Step 18: Execute instruction 11: cases on R2. The first symbol in that register is 1, so we delete that symbol and go forward two instructions.
Step 19: Execute instruction 13: go forward 3 to instruction 16.
Step 20: Execute instruction 16: add 1 to R1.
Step 21: Execute instruction 17: go backward 6 to instruction 11.
Step 22: Execute instruction 11: cases on R2. The first symbol in that register is #, so we delete that symbol and go forward three instructions.
Step 23: Execute instruction 14: add # to R1.
Step 24: Execute instruction 15: go backward 4 to instruction 11.
Step 25: Execute instruction 11: cases on R2. The first symbol in that register is 1, so we delete that symbol and go forward two instructions.
Step 26: Execute instruction 13: go forward 3 to instruction 16.
Step 27: Execute instruction 16: add 1 to R1.
Step 28: Execute instruction 17: go backward 6 to instruction 11.
Step 29: Execute instruction 11: cases on R2. The first symbol in that register is #, so we delete that symbol and go forward three instructions.
Step 30: Execute instruction 14: add # to R1.
Step 31: Execute instruction 15: go backward 4 to instruction 11.
Step 32: Execute instruction 11: cases on R2. The first symbol in that register is 1, so we delete that symbol and go forward two instructions.
Step 33: Execute instruction 13: go forward 3 to instruction 16.
Step 34: Execute instruction 16: add 1 to R1.
Step 35: Execute instruction 17: go backward 6 to instruction 11.
Step 36: Execute instruction 11: cases on R2. The first symbol in that register is #, so we delete that symbol and go forward three instructions.
Step 37: Execute instruction 14: add # to R1.
Step 38: Execute instruction 15: go backward 4 to instruction 11.
Step 39: Execute instruction 11: cases on R2. The first symbol in that register is #, so we delete that symbol and go forward three instructions.
Step 40: Execute instruction 14: add # to R1.
Step 41: Execute instruction 15: go backward 4 to instruction 11.
Step 42: Execute instruction 11: cases on R2. The register is empty, so we go ahead one instruction.
Step 43: Execute instruction 12: go forward 6 to instruction 18. The computation then halts properly because the control is just below the last line of the program, and because all registers other than R1 are empty. The output is 1#1#1##. 
step_by_step('1##11111####',['111'])
First, here is the program:
The computation starts with the register contents shown below. The registers include those those which you entered as part of the input and also others mentioned in the input program.
Step 1: Execute instruction 1: add # to R1.
Step 2: Execute instruction 2: go backward 5 to instruction -3. The computation has not halted properly because the control went above instruction 1 of the program. 
sage --pip install slabbe
File "/tmp/ipykernel_5912/1371534868.py", line 1 sage --pip install slabbe ^ SyntaxError: invalid syntax