Sr. Developer @easytechgreen

Week of the 07/12/2020 - #50



  • The “busy beaver” problem and its relation to math


  • Escher and an 8-bit demo
  • Twitter likes

The “busy beaver” problem and its relation to math

One idea that has been circling in my mind for years is the posibility of proving mathematical theorems by showing that a particular program halt. Its straightforward to see that you can encode some mathematical theorems into programs that will stop if and only if the theorem is true. So if, by inspecting the program you somehow come to the conclusion it will have to stop under some condition then that would be equivalent of proving the mathematical theorem. Of course its not by any means obvious how to do this but it might turn out that its easier to prove the theorem in this other way.

Related to this idea is the “busy beaver” problem. The problem can be stated in the following way in terms of a Turing machine: given a Turing machine with a finite amount of states and a blank tape what is the halting program that can run the longest. More precisely, the busy beaver game consists of designing a halting, binary-alphabet Turing machine which writes the most 1s on the tape, using only a given set of states. The rules for the 2-state game are as follows:

  1. the machine must have two states in addition to the halting state, and
  2. the tape initially contains 0s only.

A player should conceive a transition table aiming for the longest output of 1s on the tape while making sure the machine will halt eventually.

The busy beaver question is interesting because if you know what is the longest a program of a particular size can run for then you know how long you have to wait to see if any other program of the same size will halt or not. By encoding a mathematical theorem in a program of that size you know how long you need to wait to see if its true or not. This week there was a great article on Quantamagazine on this topic. Here are some interesting links and papers relating to this problem:

Escher and an 8-bit demo

This week I spent some time watching and reading about Escher’s fascination of tilings. I’ve been a fan of Escher for many years and love his art. I have a book which is called “MC Escher: his life and complete graphics work”. In it I learned that he had written a book called “The regular division of the plane”. It was commissioned to hime by the De Roos Foundation and was printed in a limited number of copies. In it he describred his process for the creation of the regular division of the plane and created some beatufiul woodcuts to help the reader.

Regular division of the plane - Woodcut I Regular division of the plane - Woodcut II Regular division of the plane - Woodcut V

These two figures are also very illuminating:

Regular division of the plane - Figure 1 Regular division of the plane - Figure 2

Inspired by his work I’m thinking about doing a demo for the Apple II by subdivision of the plane. I’ve already created some simple patterns and now I want to create more and combine them to make something inspire by woodcut I or by the famous “Metamorphosis II” print where the patterns combine one after the other:

Metamorphosis II

So far I’ve been working in a Jupyter notebook to create the base patterns and then try to combining in a way that looks nice. Here are some of the patterns:

Pattern 1: standard checkerboard Pattern 1

Pattern 2 Pattern 2

Pattern 3: 2 & 3 are from “Pattern in Islamic Art: Geometric Patterns & Borders” Pattern 3

Pattern 4: don’t rememeber where I saw this Pattern 4

And here is one possible way to combine them:

Pattern 4

Here’s the source-code for this experiment:

import matplotlib.pyplot as plt
import matplotlib
import numpy as np
import math

cmap = matplotlib.colors.ListedColormap([[0.2,0.2,0.2], "white"])

# Vacio
def pattern0(row, col):
    offset = 6
    if row < offset:
        return 0
    p = 0.18 * math.sqrt(row - offset)
    if np.random.random_sample() < p:
        return pattern1(row,col)
    return 0

# patron cuadriculado
def pattern1(row, col):
    row = row % 4
    col = col % 4
    if row < 2 and col < 2:
        return 1
    if row > 1 and col > 1:
        return 1
    return 0

# patron arabesco 1
def pattern2(row, col):
    row = (row - 3) % 4
    col = (col - 1)% 4
    if row == 0 and col == 1:
        return 1
    if row == 1 and col > 0:
        return 1
    if row == 2 and col < 3:
        return 1
    if row == 3 and col == 2:
        return 1
    return 0

# patron cruces desfazadas
def pattern3(row, col):
    pattern = "" + \
        "0010111010" + \
        "0111010001" + \
        "1010001011" + \
        "0001011101" + \
        "1011101000" + \
        "1101000101" + \
        "1000101110" + \
        "0101110100" + \
        "1110100010" + \
    row = (row) % 10
    col = (col) % 10
    index = row * 10 + col
    c = pattern[index]
    if c == '0':
        return 0
    return 1

# patron cruces desfazadas
def pattern4(row, col):
    pattern = "" + \
        "0100" + \
        "1110" + \
        "0111" + \
    row = (row) % 4
    col = (col) % 4
    index = row * 4 + col
    c = pattern[index]
    if c == '0':
        return 0
    return 1

width = 16
height = 100
bits = np.zeros((height,width))
for row in range(0, height):
    for col in range (0, width):
        if row < height / 4:
            color = pattern0(row, col)
        elif row < height / 2:
            color = pattern1(row, col)
        elif row < height * 3 / 4 - 3:
            color = pattern2(row, col)
            color = pattern3(row, col)
        bits[row][col] = color

plt.xticks([0,15],['0', '0xf'])
plt.yticks([0,15],['0', '0xf'])
plt.imshow(bits, interpolation='none', cmap=cmap, origin='upper' )
  • For the Apple demo, one idea is to generate a bitmap with all the combined patterns and use a compressor like lzsa to compress it and scroll it from bottom to top. The demo can be stored on disk using qboot for its speed and/or c2d to create a bootable disk.

c2d loader

Twitter likes

Here is some visual stimulation I’ve collected from my Twitter like feed:


Image 1 Image 2 Image 3 Image 4 Image 5












Image Image