5 ms·
A Working Turing Machine Hits Lego Ideas
- throwup238 2y agoPrevious discussion: https://news.ycombinator.com/item?id=41633551 https://news.ycombinator.com/item?id=41633551
- nomel 2y agoThe video without annoying music: https://www.youtube.com/watch?v=KGliD4KjxAo https://www.youtube.com/watch?v=KGliD4KjxAo
- echoangle 2y agoHere's the Ideas link: https://ideas.lego.com/projects/10a3239f-4562-4d23-ba8e-f4fc94eef5c7 https://ideas.lego.com/projects/10a3239f-4562-4d23-ba8e-f4fc...
- jkaptur 2y agoLego should provide a way to check whether the machine will stop for a given input, so that kids don't get frustrated turning the crank forever.
- seanw444 2y agoLego subsequently wins the most consequential Turing Award ever awarded...
- mmarx 2y agoSince 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 …
- jagged-chisel 2y agoMy computer has a finite state space, but I can still write programs where termination is not decidable.
- arjvik 2y agoTermination is decidable, it's just that the finite program which decides if it terminates would take unfeasibly long to run.
- PhasmaFelis 2y agoCan 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.
- Jerrrrrrry 2y agoAnyone can write a program to factor numbers into their factors. Just start at 1, and iterate until sqrt(x). Whats the big deal?
- _yb2s 2y agoThere 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.
- hinkley 2y agoIn this house we obey the laws of physics.
- y-curious 2y agoMaybe 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?
- kurisufag 2y agoOne 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.
- Morizero 2y agoIs it a legal build though? It feels like it shouldn't be with how much flexes & rubs. Very cool either way.
- gowld 2y agoWhat part flexes and rubs?
- bluetidepro 2y agoWatch out, the Lego police will you get you if it's illegal.
- Morizero 2y agoNah they just won't produce it, just like how "Quest Builder" was rejected despite having a ton of support
- xutopia 2y agoI think it could be improved to have its inner workings even more visible.
- dmonitor 2y agoLego 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.
- _yb2s 2y agoAnyone know what the specs are, e.g. number of states, symbols, and tape size?
- schnuri 2y agoFrom the Ideas Page: > 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 ;)
- deleted 2y ago[deleted]