SE Peeze Binkhorst sez, "100 years ago today, Alan Turing was born. To celebrate, I wrote a Universal Turing Machine in 100 Punchcards. I've uploaded a video to explain a small part of the read head (the Jacquard). One needle is shown out of a total of 28. The needle and anything else in the animation is not part of the Turing Machine, but is part of a machine that reads and executes the program, i.e. a computer I am working on, which is in part explained in this schematic. As the turingloom website is about a program for a Turing Machine and not about a physical Turing Machine, I hope to be excused from the requirement of infinite tape."

report this ad

You could not ask for a clearer, easier-to-read, more informative guide to facial recognition and machine learning thank Adam Geitgey’s article, which is the latest in a series of equally clear explainers on machine learning, aimed at non-technical people — and if you are a programmer, he’s got links to Python sample source and projects […]

Game theory is the place where politics, economics, psychology and math meet, and it offers the seductive promise of being able to quantify empirically optimal outcomes from thorny problems ranging from whether to go to war to how to split the tab at a restaurant.

In the year since Berke Breathed came out of retirement to cover the 2016 election cycles with Opus, Bill, Milo and the gang, he’s amassed enough material to fill a new 144-page collection: Bloom County Episode XI: A New Hope, which comes out in September.

Home audio has taken some big leaps forward in recent years–not just in terms of sound quality, but also in the style department. The FRESHeBAR Leather Soundbar, now 56% off in the Boing Boing Store, is proof.The FRESHeBAR comes packing almost all the options you’d ever need for a home sound system, including Bluetooth streaming capabilities.The unit’s 90 […]

Much of what goes into creating an amazing photo happens in the digital darkroom. Here’s your chance to master all things photo editing: the Ultimate Adobe Photo Editing Bundle, now available in the Boing Boing Store for just $29.99.Across 8 courses and over 41 hours of intensive instruction, you’ll learn the fundamentals of Adobe’s suite of photo […]

3D printers are hot, but they’re also pricey. While the prospect of cranking out everything we can dream up is enticing, cost is often one factor that keeps us from jumping onto the 3D printing train.Now, thanks to M3D, that doesn’t have to be the case. You can now get its flagship 3D printer–plus four reels of filaments–for just […]

report this ad

Surprised you guys haven’t posted on the current Google Doodle. Its some sort of Turing machine based puzzle game. And I am entirely incapable of figuring it out.

Interesting. I am sorta able to get the binary numbers to match (at least at first), but I really am not quite sure what I am doing…. Thanks for pointing this doodle out

It appears to be a simple puzzle — program his machine to give a desired output, which is his encoded name (there is another layer of complexity I don’t grok, the relationship between input and output). 10 minutes of debugging gets you to “Alan Turing” search results. Thanks, Alan, for showing us how to search any term, automagically. Thank FSM for high level formal languages.

The hardest part for me was realising that there

wasa puzzle.I actually looked it up.

Now, imagine the fate of the free world resting on your ability to solve that puzzle. Welcome to Bletchley Park.

What’s funny is that I know significantly more about Bletchley Park and Turing as an adult. I grew up and went to school in Bletchley.

Yes, yes, welcome to Bletchley Park! Now strip down to your knickers. Oh yes, it’s for the war effort, you see. Quite essential, really.

It’s like a heterosexual version of Moby Dick.

Reminds me of a great episode of James Burke’s ‘Connections’

Episode 4:Faith in Numbers.

Ok, guys, PLEASE. A Turing machine requires an INFINITE sized tape. A Turing machine is theoretical and CANNOT EXIST.

A finite machine – a machine with a finite tape or finite memory – is a non-deterministic finite automata. NOT a Turing machine.

Thank you and good day,

Yehuda

Now you’re just nitpicking. In non-formal conversation, finite state-based automata are frequently referred to as ‘Turing machines’, and for very good reasons. (For all programs not exceeding the available tape capacity, there’s no difference. While infinite tape is impossible, ‘large enough’ is a reasonable approximation for many purposes.)

…

Maybe it’s nitpicking. But the difference between a Turing Machine and a finite state automaton is like the difference between infinite and finite, or between the alphabet and the entire works of Shakespeare (times infinity) i.e. Really Big.

The whole point of a Turing Machine being infinite was that it could theoretically simulate the responses of a human being (i.e. ANY response to ANY input) and therefore pass the Turing Test. A finite automaton is little more than a version of Eliza; a finite series of responses to a finite series of inputs. It’s a nifty calculator.

Finite automata are cool in their own right. Ones with really big tapes are cooler. But seeing them presented as Turing Machines is just painful.

Yehuda

All that is true, but I stand by my claim. The English language has evolved to contain (outside of mathematical contexts, where I agree with you totally) the idea of ‘Turing machine’ as a synonym for any such state-based automaton. And this isn’t a harmful development – it’s a useful, compact phrase. Even if it does make the logician part of me wince for a second.

Nor is this a problem for Turing’s original discussion point. At least one machine which we *know* would pass the Turing test – an exact simulation of a human brain – is a finite machine. We know that an infinite-capacity-tape Turing Machine is not actually necessary for the test. I concede that a finite automaton is ultimately nothing more than a nifty version of Eliza, but then… so are we. (Unless you’re claiming to possess an infinite number of neurons, in which case I will have little choice but to bow to your superior intellect.)

After all, an awful lot of maths is based on us pretending that there’s no meaningful difference between finite-but-arbitrarily-large and countably-infinite.

I think a couple of things should be kept in mind:

1) The definition of a Turing Machine (TM) works perfectly well with an unbounded tape, not an infinite tape.

2) The only TMs which need an infinite tape are non-halting TM. Every halting TM only uses a finite tape.

3) Nearly every (if not every) computational class (e.g., P, NP, PSPACE, EXP, etc) only uses a finite tape who’s length can be bounded before running; Even NP-Complete problems only take a tape proportional to a polynomial of the input size.

So if you give me a computable problem, plus it’s input, I can give you a TM with a finite tape than can solve it.

And the point of a TM was not to pass the Turing Test, it was to prove that the set of computable numbers is countable.

The 100 punchcards merely define the rule table of a Turing Machine, it is software. The machine itself is a computer, not a Turing Machine. The program thinks the memory is the tape and uses that.

If the tape is longer than the machine is physically capable of indexing through in a lifetime, it’s for all practical purposes infinitely long.

Er, it is a finite automata but a deterministic one, not a non-deterministic one.