First steps¶

To start, either download this notebook and run it locally, or else click on ‘Open in Colab’ above. Then click on the triangle below.

!python -m pip install -U setuptools
!python -m pip install -U git+https://github.com/lmoss/onesharp.git@main
from onesharp.interpreter.interpreter import *

Welcome to our first tutorial lesson on \(\one\hash\). You will learn the basics of the language here and also see some small programs.

This lesson is written on a lower level than the lessons which come after it. The only abstract concept comes at the end, as does the only and mathematical notation. The rest of the lesson is a concrete introduction to \(\one\hash\).

If you are familiar with any machine model in the theory of computations, such as Turing Machines, or classical register machines, you probably will want to skim through this lesson quickly.

But this introductory lesson is really intended for people with no background on these matters. If this is you, please work slowly, doing the exercises as you go.

To begin, here is an interpreter for \(\mathtt{1\#}\). Even before learning how the language works, we want to see how to run programs by entering them into the interpreter along with inputs.

def end_strip(list): ## removes the tail of empty registers
  if list == []:
    return(list)
  elif list[-1] == '':
    return(end_strip(list[:-1]))
  else:
    return(list)
def remove_multiple_blanks(my_str):
   return(my_str.replace(" ", ""))


program = '11#####111111###111###1##1111####1#111111####' #@param {type:"string"}
R1 = '#11###1' #@param {type:"string"}
R2 = '11111#' #@param {type:"string"}
#R3 = '' #@param {type:"string"}

## For more registers, add lines here like
## R4 = '' #@param {type:"string"}
## You also must modify the definition of 'a' below accordingly.

# First, we delete the last batch of empty registers
# to simplify the output 
a = [R1,R2]
a = [remove_multiple_blanks(x) for x in a]

onesharp(program,a)

'#11###111111#'

The top line of the interpreter contains the following program of \(\one\hash\):

11#####111111###111###1##1111####1#111111####

The other two lines are the inputs to two registers. Those inputs are the same kind of mathematical object as the program: they are words on the alphabet \(\set{\one,\hash}\). In this book, words are just sequences composed of the symbols 1 and #, such as 11###11#1 and #1###1###111#11. We’ll have more to say about and programs soon. But for now, modify the inputs to R1 and R2, but keep the program the same. Click on the arrow to run the program on the inputs, and look at the output below the interpreter.

Another way to run the program is to type shift-return on a keyboard. The output is shown below the interpreter, above the current cell.

The empty word is a perfectly good word, so you could also enter it into R1 or R2 just by leaving the register blank or by entering one or more spaces.

You can modify \(\Rone\) and \(\Rtwo\) as many times as you like.

What you should find after doing this is that the output is the input in \(\Rone\) followed by the input in \(\Rtwo\). We usually will say concatenated instead of followed by.

The overall point is that the program 11#####111111###111###1##1111####1#111111#### may be run on words which are input in the registers. This program does not change when we run it. Our little interpreter didn’t show the step-by-step behavior of the register machine, it only showed the final output. We’ll return to the soon, after we understand what the program is doing. It turns out that this program is composed of seven instructions. We’ll get to the instructions soon, but first we have an exercise for you to try.

Exercise 1

Here is another 1# program. It takes its input from the first two registers. Enter some words in R1 and R2 input boxes, and then run the program. Your job is to try to figure out what the program does.

1##### 11111111### 1111### 111## 1111## 11111#### 111# 1111# 11111111#### 111##### 111111### 111### 1## 1111#### 1# 111111#### 1111##### 111111### 111### 1## 1111#### 1# 111111#### 11##### 111111### 111### 1## 1111#### 1# 111111####

Instruction	Meaning
1#	Add 1 to R1
11#	Add 1 to R2
111#	Add 1 to R3

Instruction	Meaning
1##	Add # to R1
11##	Add # to R2
111##	Add # to R3

Instruction	Meaning
1^n #	Add 1 to Rn
1^n ##	Add # to Rn

Instruction	Meaning
1^n ###	Go forward n instructions
1^n ####	Go backward n instructions

Instruction	Meaning
1^n #	Add 1 to Rn
1^n ##	Add # to Rn
1^n ###	Go forward n instructions
1^n ####	Go backward n instructions
1^n #####	Cases on Rn

Invitation to Computability

First steps

Contents

First steps¶

The \(\mathtt{1\#}\) instruction set¶

What are programs?¶

Running programs in notebook cells¶

The full set of instructions of 1#¶

Useful command-line tools¶

Useful operations inside a Jupyter notebook¶

	instruction	explanation
1	1#	add 1 to R1
2	11#####	cases on R2
3	1###	go forward 1 to instruction 4
4	1###	go forward 1 to instruction 5

Instruction	Meaning
`onesharp(p,[r1, . . .,rn])`	runs the program `p` on the list of words `[r1, . . .,rn]`
`step_by_step(p,[r1, . . .,rn])`	parses p and shows all steps in the run
`parse(p)`	expresses `p` as a list of instructions
`parse_explain(p)`	gives a table of the parse with glosses
`unparse(p)`	inverse of `parse(p)`

	contents
1	1#1
2	#

	contents
1	1#11
2	#

	contents
1	1#11
2

	contents
1	#1
2	#1
3	1#