Pages

Showing posts with label taocp. Show all posts
Showing posts with label taocp. Show all posts

Tuesday, May 4, 2010

An actual Turing machine!

A month ago I saw this post on programing reddit,
"While thinking about Turing machines I found that no one had ever actually built one"

and it's about the site http://aturingmachine.com/


Of course, Turing machines were not devised to be used like actual computers.
The Art of Computer Programming, Volume 1
1.4 Some Fundamental Programming Techniques
1.4.5 History and Bibliography, pg 230.

[...] The first interpretative routine may be said to be the "Universal Turing Machine", a Turing machine capable of simulating any other Turing machines. Turing machines are not actual computers; they are theoretical constructions used to prove that certain problems are unsolvable by algorithms.
Nevertheless, that's a really impressive work.

(*) I won't be surprised if you tell me that this is the first time you encounter the term "interpretative routine".

Knuth, emphasis on function as well as form is basic to design problems

The Art of Computer Programming, Volume 1
2.2 LINEAR LISTS
2.2.1 Stacks, Queues, and Deques, pg. 238

[...]

We must decide in each case how much structure to represent in our tables, and how accessible to make each piece of information.  To make such decisions, we need to know what operations are to be performed on the data.  For each problem considered in this chapter, therefore, we consider not only the data structure but also the class of operations to be done on the data; the design of computer representations depends on the desired function of the data as well as on its intrinsic  properties.  Indeed, an emphasis on function as well as form is basic to design problems in general.