Langton's Ant (extra footage) - Numberphile 

+tomatoso27 he's basically a cellular automaton zealot haha

+tomatoso27 (not necessarily a bad thing)

Elan Jacobs very punny

k

Dustin Rodriguez Nice! Thank you. Let's see if I can build a full-adder with this.

Where did the logic gates go?

??

AHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH THEY'RE GONE

nonononononononononoonononononononononononononononononononononononononnnnnnnnnnooooooooonononononon

+Anthony Ferrara I was thinking just the same thing, but in the other direction. If it always halts(it gets to the highway configuration), it cant be Turing complete.

+Anthony Ferrara I think that depending on the input grid, the steps required to get to the configuration that gives the highway pattern is variable. Whether or not a certain pattern will get to the Highway stage is uncertain, perhaps testing a certain pattern will take for ever.

***** But you can't know whether or not a certain pattern will halt or not. If you consider the Highway pattern to be the halt stage, for some patterns, it is trivial to see whether or not it halts the system, but for other patterns, the computation could take for years before the highway pattern is ever reached. With a traditional Turing machine, that is what the halting problem is all about, not being able to find out if the machine will halt in reasonably fast time given some input. In this ant game, the rules are a little different than the traditional linear Turing machine, but the principle is the same: Given some program description (one's and zeros in a basic Turing machine, the grids in this ant game) the halting problem is to find out out if the program will finish at some point or 'Halt' which means that it will run for ever. You have to know for all programs though, in order to solve the halting problem one way or another. There has to be a way of calculating whether or not the pattern will halt without actually simulating it, which relates the the P vs NP problem. Needless to say, solving these types of issues would be a big deal, and would change the face of computation for ever.

If you can prove this is a universal turing machine, then we can trivially find unhaltable starting states. Because we know of many turing machines that are unhaltable, so it's just a matter of re-encoding it into this mechanism. So "we've never found one that didn't wind up in the highway" either implies that 1) it's not a universal turing machine as claimed, or 2) (and far less likely) that it's a solution to the halting problem. Either that, or they just haven't tried to find one that doesn't halt...

JapTut finite turing machines exist which don't halt. The only requirements are that the tape is infinite, not that the machine itself (the rules) are infinite. You need infinite support to be universal, but you can implement finite machines that don't halt (for example, in BrainFuck, the following program will never halt: +[]. This will run forever.

Woah. Overlaying multiple cellauts at once.

+Henrix98 scratch.mit.edu/projects/13801864/

Guest6265+ I tried that, it does not fill my requirements

Henrix98 can you run python code? If so I could send you a working script

while I get what you mean, just thought I'd point out that a wrap-around grid is not remotely similar to a sphere.

@@alansmithee419 Yeah, a wrap around grid is like a torus.

It is there to increase the entropy of the universe.

Because you'd need to try every initial state and there are an infinitely many possible starting states. People have tried a lot and have found that in all of them it always ends up on the highway, but they have not tried all, nor has anyone found a counter example. People need a rigorous mathematical proof.

Primus Productions Yeah, I understand how a proof works. Did you not read my comment? In the first video she says that it's proven, but then in this video she says that it isn't proven.

The true answer should have been that it HAS been proven that the ant will escape and make some sort of pattern, but it HASN'T been proven that that pattern is always the highway.

A loop was shown in the video

I don't quite understand what you mean by "let it go left and right forever". The rule is, the ant moves forward and turns left or right depending on the color of the square it just left, then it changes the color of that square it just left.

Ok well it's a Turing Machine, I don't know much about it.

Watch Up and Atom's video, you will understand everyhing

Well...no, since you don't know what the board looks like outside of the highway in your idea. There are many different games with a highway, so you have to retrace all of them. For example, one could be a few cells leading up to the highway and the rest blank, another could be the same thing, but with a random cell switched. Basically there are too many highway positions to retrace them all.

There are multiple possibilities to start the Highway. The ant can enter the pattern from every direction and the cell before that too and so on. It doesnt make it any easier. You will have to compute exponentially many variations.