Is there a Turing-complete programming language for pen and paper?

3 days ago by ki4jgt to c/asklemmy

Let's say you wanted to use the mind as a calculator, and pen and paper as memory/registers/storage. Is there a programming language that works with pen and paper?

wiccan2 22 points 3 days ago

Yes, the WDR Paper Computer: https://en.wikipedia.org/wiki/WDR_paper_computer

It's an awesome way to show the fundamentals of an assembly language without getting too complicated.

Originally designed for use in schools to teach computer science without needing an expensive electronic computer.

save

path: 0 26241951, hotness: undefined, score: 22, children: 0

AbouBenAdhem 10 points 3 days ago

Check out lambda calculus—it was created by Turing’s doctoral advisor in 1936, and thus predates real-world programming languages.

save

path: 0 26241645, hotness: undefined, score: 10, children: 0

AntiOutsideAktion 8 points 3 days ago

A pen and paper is the original memory/storage/register and your brain is the original calculator so yes and no.

You literally carried out the outcome of your question by asking it

save

path: 0 26241904, hotness: undefined, score: 8, children: 1

wiccan2 3 points 3 days ago

This comment deserves more love.

The word "computer" predates what most people think of as a computer by centuries. It was originally a job title, people were called computers because that's what they did compute. They would follow the instructions given to them by hand and then give the results to their supervisor.

It also wasn't seen as an intellectual role and they were sometimes not appreciated as much as they should have been. A good example is how the women in the computing departments at NASA were treated, especially those that were also segregated because of their colour.

save

path: 0 26241904 26244230, hotness: undefined, score: 3, children: 0

zener_diode 3 points 3 days ago

This is actually something that a turing machine is suitable for.

Get youself something to remember what state you're in, write the rules on a sheet of paper and use a stack of paper as the tape, with each piece of paper being one cell.

Turing's idea was to build a mathematical model that mirrored how humans go about large, complex tasks.

Honestly, all of these super basic mathematical models for calculation are fairly well suited to being "run" by hand.

Random-access-machines can be done similarly to turing machines. Write the program down, keep the program counter on one piece of paper, and have a (numbered) stack of paper as memory.

And lambda-calculus is probably the easiest. Just write out the expression, and then write out each reduction step. This is what functional programming languages build on, and with the additional effort of checking types, you could probabl evaluate something like Haskell by hand pretty well.

All of those are turing complete (if you ignore infinite memory).

EDIT: spelling

save

path: 0 26241803, hotness: undefined, score: 3, children: 0

red_tomato 3 points 3 days ago

In theory, any programming language can be carried out on pen and paper. The problem is that it doesn’t take much for it to become far beyond impractical.

save

path: 0 26241907, hotness: undefined, score: 3, children: 0

gezero 3 points 3 days ago

Turing machine itself is a theoretical tool that was thought to me using pen and paper, or chalk and blackboard. I guess you are looking for higher level language.

In such case i would allow multiple heads and more complex operations on the heads.

save

path: 0 26241635, hotness: undefined, score: 3, children: 0