⚠️ This blog post is not finished and is a work in progress. Along with being really poorly written, it also stops making any sense towards the end. ⚠️
*non-programmable scientific calculator
Introduction
As an A-level student, I am at the mercy of JCQ – the Joint Council for Qualifications – for what I am and am not allowed to do during my exams. They are the ones that say you should only have a clear pencil case, wearing any watch is a crime and that you get a generous 4% extra in your exams if you had 6 nights in an ICU just before (though they do raise it to 5% if you are terminally ill).
One interesting section of their specification is where they discuss what sort of calculator you’re allowed in the exam:
This is my school calculator:
(or at least an emulation of it). It’s a Casio FX-991EX and the one that most of the Edexcel mathematics A-level syllabus is written to use. It’s a decent calculator and can do things you’d expect a scientific calculator to do, like adding numbers together:
Hmmmm. Division:
Keeping things in terms of $\pi$:
Hmmmm. And it also has some nice features, like it lets you store intermediate calculations as variables (here $x$ gets set to $5$):
It also supposedly meets all the criteria of the JCQ specification. Although it can integrate and differentiate, it does so approximately and numerically rather than symbolically. It also definitely can’t translate anything, or do symbolic algebra manipulation. There’s also no functionality for writing your own programs – you’re stuck with the functions it gives you.
But what if I told you that you actually could do all those things? It turns out that using a messy combination of its existing functionality, you can actually use it to emulate a Turing machine! This means that, in theory, it can actually do anything a normal computer can do, albeit very, very, very slowly.
In fact, it’s so slow and cumbersome that it would make any practical application in an exam completely worthless, such as writing a program to compute integrals or rearrange equations. By the time you’d finished writing the program, the exam would’ve ended hours and hours ago. But I still find it interesting in theory because it’s surprising. It means that you can say “Sure, this is supposed to just add numbers together. But if I had an infinite amount of time, and a calculator with an infinite amount of memory, I can add numbers together in just the right way that it could use it to simulate an entire universe”.
This isn’t a property of arithmetic, but a property of the calculator thanks to a few quirks and features it provides (which will be explained shortly). Addition and subtraction aren’t enough for Turing completeness by themselves1.
What is Turing completeness?
Turing completeness, at least informally, is a property of a system that means it is computationally universal and can be used to carry out any procedure or program that any other computer can. For example, programming languages like Python and Java are said to be Turing complete because they can be used to write any program that a computer could carry out. HTML, a markup language, is not Turing complete because you couldn’t use HTML to write a program that calculated the digits of Pi (although you could create a website that did using JavaScript).
Non-programmable calculators aren’t supposed to be Turing complete because they don’t provide conventional facilities for programming, like an editor or a way of storing and loading code you’ve already written. You can buy programmable calculators, and so they are Turing complete almost by definition. But scientific calculators like mine aren’t created by the manufacturer with the intention of being able to run any program you want.
An Example
As an example, the calculator lacks any functionality to return the maximum of two numbers. That’s fair enough – most of the time, you can use your eyes to see which of two numbers is bigger, and if you really weren’t sure you could subtract one from the other and see if you get a positive answer.
But suppose that all of that we were having a bad day and needed to relax. We want to just be able to type in two numbers, press equals a few times and be told, plain and simple, which of the two numbers is bigger. We don’t want to have to do any mental work whatsoever – making any comparisons ourselves is out of the question. Let’s say that we want to work out which is the bigger number out of $1$ or $3$ (spoiler: it’s $3$).
The first step is feeding our inputs to the machine. We have two numbers, but we can actually turn it into just one number thanks to the fact that every number can be written as a unique product of primes. In other words, we can represent $1$ and $3$ as just one number, $2^1 \times 3^3 = 54$ because $2$ and $3$ are the first two primes.
Or say we wanted to find the bigger number out of $23297436860606013585$ and $9656989334340131089$, we would use:
$$ 2^{23297436860606013585} \times 3^{9656989334340131089}$$
This is a number with around $100,000,000,000,000,000,000$ digits2.
Let’s store our original example of $2$ and $3$ in $x$:
So far, so good. Now we have to do just a little bit of initialisation of a couple other variables. This looks like hard work but it isn’t – these get set to exactly the same thing regardless of what numbers want to find the max of so we are yet to make any decisions for ourselves.
In a bit of a more familiar notation, we’ve just done:
# Specifically for our problem
x = 2**1 * 3**3
# Things we set every time
C = 0
y = 3
A = x
F = 1
(confusingly, assignment is denoted backwards on the calculator). Now we are ready to type in the “program”.
√(F-1)
C -> x
y -> B
-(y-2)(y-1)(y)÷(3!)+y -> y
x -> C
(Ax5⌟3-x)(B-2)(B-1)(B)÷(3!) -> x
Σ(1, 1, x)
y -> b
-(y-1)(y)÷(2!)+y -> y
x -> C
(Ax5⌟2-x)(B-2)(B-1)(B)÷(2!) -> x
Σ(1, 1, x)
y -> b
0 -> y
x -> c
(Ax5⌟6-x)(B)÷(1!) -> x
Σ(1, 1, x)
Abs(a - x) -> f
x -> a
3 -> y
…and hit equals and back quite a few times, you’ll eventually be left with the bigger number only.
Backlinks
Metadata
date: 2021-09-29 15:19
tags:
- '@?public'
- '@?blog'
- '@?safe-to-post-online'
- '@?todo'
title: Using a scientific calculator as a Turing machine
Attachments
- addition.png
- calculator-blank.png
- division.png
- init-1.png
- init-2.png
- initial-input.png
- pi.png
- recall.png
- spec.png
- storage.png
-
Though I’m limited by my current understanding here, technically the Peano axioms (a set of simple rules that capture in simple rules what we mean by “arithmetic” in a logical context) are enough to provide Turing completeness. However, this description includes things like boolean connectives (
AND,OR,NOT) and statements involving “for all $x$” which isn’t the sort of arithmetic you mean when talking about calculators. ↩︎ -
This is an example of where you’d run into memory limitations on the calculator. The biggest number it can store is $10^{100}$, which is about $3^{210}$. ↩︎