Turing Machine Alternative (Counter Machines) - Computerphile

Computing with counters. How "counter machines" are as powerful as turing machines, albeit slightly more convoluted! Dr Christopher Hampson, Senior Lecturer in Computer Science Education at KCL explains.
EXTRA BITS: • EXTRA BITS - More on C...
/ computerphile
/ computer_phile
This video was filmed and edited by Sean Riley.
Computer Science at the University of Nottingham: bit.ly/nottscomputer
Computerphile is a sister project to Brady Haran's Numberphile. More at www.bradyharan.com

[@remingtonantonamalanthan1685]

Chris was the single best lecturer that I've ever had (and probably will ever have). Broke down problems in a way that everyone could understand. Glad to see that his streak of amazing teaching continues!

[@cadekachelmeier7251]

The other half of this would be to show that every counter machine can turn into a turing machine. That's left as an exercise for the reader.

[@enas_trelos]

Best lecturer I had at KCL. Always a pleasure listening to him!

[@dembro27]

Using the right candy as counters, this seems like a delicious alternative, though more prone to data loss.

[@stardustsong1680]

It's so weird to call it "Counter Machine" but we can't actually "count" the number of elements inside every container. I'd rather call it "Stack machine" because its behaviour is similar to a stack ("push" and "pop").

[@wholenutsanddonuts5741]

Turing was amazing. Thanks for this counter example!

[@ekandrot]

For double, why not double on the write rather than the read? It would be almost half the number of overall operations.

[@mellertid]

So both the containers and the value units are "counters"?

[@r-prime]

I just realised this is literally easier Brainfuck with no i/o:

[@tediustimmy]

I'm another person who immediately thought brainf*ck. The counter machine has some capabilities that bf doesn't have, like 'break'. An interesting tidbit is the isomorphism between bf and a language Corrado Bohm invented in the 1960s while simplifying Turing machines. This language shows up in Bohm and Jacopini's proof of the Structured Programming Theorem.

[@stickfigure31]

How he describesld a counter machine works kind of reminds me of when I built an 8bit binary adder with a 1bit carry out with Redstone NOR gates in my survival world. It was so tiring and resource intensive I didn't want to added hardware bitshit or bitwise operators, so I looked up the Arithmetic algorithms and converted the multiplies/divides to repeated add instructions before working on a clock, program counter, and memory.

[@s.patrickmarino7289]

This looks functionally a bit like the destructive read of core memory in very early computers.

[@issaryazbin1695]

In the video, it was stated that the tape of a Turing machine is infinite. If so, how would a counter machine be able to hold decimal representations of the binary numbers to the left and right of the current location?

[@George4943]

If we're looking for simplicity in hardware and want to implement logic gates the single gate, NAND, is enough. All the 2-input 1-output logic gates can be built by composing NAND gates. So all the Turing machine (or counter machine) logic can be done with NAND.

[@U014B]

23:30

[@codahighland]

It should be noted that by "outperform" he means "compute a result that a TM can't" -- not "run faster" because TMs are notoriously inefficient.

[@SteveGouldinSpain]

It's like using the Tower of Hanoi to compute!

[@themcchuck8400]

This has been implemented for 30 years as the esoteric language "Brainf*ck".

[@Jaylooker]

This counter machine has the same analogy for the axiom of choice with bags and marbles like the the axiom of choice. In a way this counter machine assumes the axiom the choice by being able to collect any element from each set to form a new set even if temporarily.