Mathematicians. If you let them use the concept of infinity, there’s almost nothing they won’t be able to prove. Case in point: the Turing machine. The idea is that with an infinite length of tape, one could build a thought-experiment machine with only a few instructions that should be able to compute anything that’s computable.
[Igor]’s Turing machine is one of the nicest we’ve ever seen built. The “tape” is significantly shorter than infinity, which limits the computations he can achieve, the use of 3D printing, electric contacts, and WS2812 RGB LEDs for the tape are profoundly satisfying.
A bit on the tape is portrayed as unused if the LED is off, zero if it is red, and one if it is green. Each station on the tape is indexed by a set of blue LEDs observed by the gantry of the writing head which uses a 3D printed finger and motor to change the state of each bit. Programs are stored on a home-built punch card, which gets extra geek points from us.
Watch it run through “busy beaver” (embedded below) and tell us that it’s not awesome, even if it is a couple of LEDs short of infinity.
For more Turing machine builds, check out this exquisite version, this one made from Lego, and this Turing machine played out on an infinite deck of Magic the Gathering cards (what?!?!).
I also did my build of the turing machine out of “meccano” and “Lego” pieces when I was in High School.
If you are interested this is the video i did http://www.youtube.com/watch?v=ZKoyp458wOU
I just came to say that the paw-print writing head is ADORABLE!
Can it play Tetris? Or mine Bitcoins? :-) Quite strange to see a Turing Machine that has an Arduino inside that is much more powerfull than the entire thing.
Haha. I want to see it as a calculator.
50!=
Great looking machine!
Punch-cards 3D printing and two light filters made from store bags.
Since we’re using LEDs for the bits, we could implement bit shifting in order to extend the “tape” infinitely in either direction (so long as we can store the “offscreen” bits somewhere).
This is a great idea. SD-cards cost almost nothing these days and have a lot of space. It’s still not infinity long but approching… Because of the mechanical stuff speed shouldn’t be an issue neither.
Just a little bit of nitpicking. Actually, there is no proof that the Turing machine can compute anything that’s computable – it’s rather that computer scientists (a certain breed of mathematicians;)) defined being computable as computable using a Turing machine. It is only a hypothesis – the Church-Turing hypothesis – that every possible physically realizable computation model computes the same functions as the Turing machine. Numerous computation models have been proposed (recursive functions, lambda calculus, stack machines, register machines…) that have all been proven equivalent to Turing machines in terms of computability.
And, well, there is nothing magical about the infinite tape – it’s just an equivalent of computer memory: the more tape you have, the more can you compute. The machine will always use only a finite part of the tape.
I didn’t understand the second sentence.
Computer scientists define the term “computable function” as “a function that can be computed by a Turing machine”. There is no good definition of what an algorithm is which does not refer to some particular computation model.
The second sentence addresses the problem with the statement: “Mathematicians. If you let them use the concept of infinity, there’s almost nothing they won’t be able to prove. Case in point: the Turing machine. The idea is that with an infinite length of tape, one could build a thought-experiment machine with only a few instructions that should be able to compute anything that’s computable.”
In that, “computable” is not defined. Computer Science as a field defines “computable” as “a set of instructions that can be carried out on a Turing machine with an infinite tape.”
So tilk is saying that the interesting part is not that a Turing machine can solve any computable problem; that statement is a tautology. What is interesting is that, so far, every other computation model has been able to be reduced back to a Turing machine with an infinite tape (the Church-Turing hypothesis).
So are you saying that if I did have a Turing Machine that I could demonstrate was capable of emulating a cyclic tag system it still would not prove that it was universal, capable of computing anything that was computable and therefore able to emulate a general purpose computer such as the Von Neumann or Harvard architectures? Given enough time and tape.
To prove that some computational model (like the cyclic tag system, semi-Thue system, etc.) is computationally complete, you need to demonstrate that some another model which was already proven to be computationally complete can be emulated on your model. For instance, if you could translate any Turing machine to a cyclic tag system, you would prove the cyclic tag systems computationally complete. (Computer scientists call such a translation a reduction).
This does not work the other way around – by showing a translation of cyclic tag systems to Turing machines, you only prove the computability of cyclic tag systems, but not their completeness. Or, in simple words, if you write an interpreter for some programming language for a general purpose computer, this does not mean that the language is computationally complete. (By the way, there is a number of useful programming languages which are not computationally complete.)
Not answering the actual question is generally rewarded with a fail.
Here is the information you would need to answer the actual question.
http://www.wolframscience.com/nksonline/page-678-text
Perhaps you could have presented the information from the start, rather than acting like a child.
Hey troll, perhaps you should stop trying to psychologically abuse people who are clearly invulnerable? Your ploys are clearly ineffective and your failure to realize this and adapt to that reality does clearly demonstrate a lack of fluid intelligence on your part.
Quin says:
July 12, 2016 at 5:02 pm
The second sentence addresses the problem with the statement: “Mathematicians. If you let them use the concept of infinity, there’s almost nothing they won’t be able to prove. Case in point: the Turing machine. The idea is that with an infinite length of tape, one could build a thought-experiment machine with only a few instructions that should be able to compute anything that’s computable.”
In that, “computable” is not defined. Computer Science as a field defines “computable” as “a set of instructions that can be carried out on a Turing machine with an infinite tape.”
So tilk is saying that the interesting part is not that a Turing machine can solve any computable problem; that statement is a tautology. What is interesting is that, so far, every other computation model has been able to be reduced back to a Turing machine with an infinite tape (the Church-Turing hypothesis).
Report comment
Reply
Hello, I would like to buy a machine of this for education, is this possible?