I feel content creators need to have more confidence in their own ability to inform / educate / entertain than to use loud music as a crutch. Not every video needs to have music drowning it.
Since the model tape isn't actually infinite, this machine has a finite state space, and termination is therefore decidable. No Turing Award to obtain here …
Can you? It's been a long time since I studied Turing machines, but if a machine returns to an exact previous full state (of both the machine and the tape), then we know it will not terminate but loop forever; and a machine with a finite tape must return to a previous state in finite time if it doesn't terminate first. So a finite state machine will either terminate or begin to loop in finite time.
There still is no shortcut -you will still need to actually compute out those states to see how long they run. The fact that for very simple machines this is possible on modern computers does not avoid or solve the halting problem.
I’m not even sure if that is actually possible on this machine even- I suppose it depends on how many bits on the tape, and rapidly becomes impossible to compute after a pretty small number of bits.
But yes- a particular program must eventually either halt or loop back to a state it already was in, which confirms non halting.
I think this is related to the https://en.wikipedia.org/wiki/Busy_beaver game. I count 5 bits on the tape, and BB(5) = 47,176,870 which seams like a tractable number of steps for a modern computer to check.
If I've understood it correctly, this means that any program for this machine which does not halt after 47,176,871 states will run indefinitely.
BB(6) is thought to be incredibly huge, so it's nice that they stopped at 5.
This machine has 8 states, so (for actual Turing Machines with an unbounded tape) you'd be looking at BB(8). However, since the tape can only store 24 symbols, the machine only has 8 (states) * 4 (tape symbols) * 24 (tape length) = 768 different configurations. Thus, any program will either terminate in at most 768 steps, or loop indefinitely.
Maybe Lego can help answer another question kids may find frustrating: if the solution to a Lego design is easy to check for correctness, must the Lego design be easy to construct?
One the greatest "real" things I've ever read in sci-fi is the /physical/ turing machine in a museum at the start of Fall; or, Dodge in Hell that actually speaks ICMP, and (with a long enough timeout) is pingable from the external 'net.
Lego Ideas has a limit on how many pieces a design can have, so fitting the Turing machine into those limitations was not easy. I agree, though, having the mechanisms be visible would make this a lot cooler.
> The model has 4 (2²) possible symbols and 8 (2³) possible states, so in total 32 possible symbol-state combinations. Each instruction has 7 bits (3 for the state, 2 for the symbol, 1 for moving left/right and 1 for stopping)
28 comments
[ 3.0 ms ] story [ 67.4 ms ] threadI feel content creators need to have more confidence in their own ability to inform / educate / entertain than to use loud music as a crutch. Not every video needs to have music drowning it.
Just start at 1, and iterate until sqrt(x).
Whats the big deal?
I’m not even sure if that is actually possible on this machine even- I suppose it depends on how many bits on the tape, and rapidly becomes impossible to compute after a pretty small number of bits.
But yes- a particular program must eventually either halt or loop back to a state it already was in, which confirms non halting.
If I've understood it correctly, this means that any program for this machine which does not halt after 47,176,871 states will run indefinitely.
BB(6) is thought to be incredibly huge, so it's nice that they stopped at 5.
> The model has 4 (2²) possible symbols and 8 (2³) possible states, so in total 32 possible symbol-state combinations. Each instruction has 7 bits (3 for the state, 2 for the symbol, 1 for moving left/right and 1 for stopping)
And the tape is unlimited of course ;)