Skip to content
Hallway
0:00 / 0:00

#turingmachine#hardwareimplementation

A Turing Machine - Overview

Mike Davey

941 subscribers • 1 video on Hallway

YouTube
  • Recommended by 2 people: 1 in engineering communities and 1 on Stack Overflow and its sister sites.
  • A classic. People kept recommending it from 2010 to 2016.
  • Presented by Mike Davey

Beginner. No background in the topic needed.

821K views16 years ago2 recommendations

Computer scienceHardwareComputation and complexityRetro computing

Mike Davey demonstrates a physical, homebrew Turing machine built to embody the classic look and feel of Alan Turing's 1937 paper.

A Turing machine is a math concept that show that a few simple rules can be used to solve any computable computation. It is the basis for all of today's computers. My goal in building this project was to create a machine that embodied the classic look and feel of the machine presented in Alan Turings 1937 paper on computable numbers. More information can be found at: aturingmachine.com

Why it's here

2 people recommend this

What people say. Recommended as an enlightening visual demonstration of how a Turing machine works compared to a finite state machine.

u/linuxpunk81in r/compsci • Recommends

Homebrew Turing Machine
31View on Reddit

user5193682on Computer Science Stack Exchange • Recommends

On “Difference between a turing machine and a finite state machine?”

I had the same doubt and I saw two very enlightning videos and one explanation on Quora as follows: A finite state machine is just a set of states and transitions. The only memory it has is what state it is in. Thus, the number of memory states is... finite. A Turing machine is a finite state machine plus a tape memory. Each transition may be accompanied by an operation on the tape (move, read, write). I have understood from it that a turing machine uses/has a a finite state machine as part of its operating procedure, plus adding some editable memory to it. Please watch also those two videos, they are enlightning! link to this video link to this video
6View the answer

u/someredditaccount2in r/compsci • Mentions

On “What is the cutest Turing machine simulator out there?”

Not exactly what you're look for, but I think the cutest Turing machine is this one: [video
27View on Reddit

u/more_exercisein r/compsci • Mentions

On “Does turing completeness guarantee anything about speed?”

*for sufficiently large n,* (sigh, begrudgingly) yes, it does. But to equate those to speed, to clock time, to seconds passing, is *wrong*. 1. The 0(1) algorithm is allowed to take as long as it wants, *as long as it does the same amount of work for all inputs*. If that work is astronomically large, but still constant, it would take an astronomically large input to an O(n) algorithm to take the same amount of work. 2. The clock time it takes to perform "the same amount of work" varies significantly. I would rather bubble sort 1000000 elements on my i5, than quicksort 10 items on this 3. There is an inflection point where the constant factors of an O( nlogn ) completely dominate the…
3View on Reddit