what 'The Imitation Game' didn't tell you

[michel paul]

Turing's 1936 paper On Computable Numbers was published in the proceedings of the London Mathematical Society. It was arguably the founding document of the computational age. Math teachers should find it significant that this was a purely mathematical article dealing with some of the same topics that Godel did.

What the 'The Imitation Game' doesn't make clear is that Turing's great achievement was actually the invention of software, but the movie focused on hardware. It closes with the message "His machine was never perfected, though it generated a whole field of research into what became known as 'Turing Machines'. Today we call them 'computers'." Well, that's not exactly accurate. Computers already existed in some rudimentary forms prior to Turing, so Turing's great achievement was not the construction of computational machinery per se but supplying a theory of computation. A 'Turing Machine' is a purely theoretical simplification of what all computing is. Though he was interested in and did dabble with the physical construction of computing hardware, he was primarily a mathematician.

Here is a nice discussion of the matter: What 'The Imitation Game' Didn't Tell You

--

​Michel

​

===================================
"What I cannot create, I do not understand."

- Richard Feynman

===================================
"Computer science is the new mathematics."

- Dr. Christos Papadimitriou
===================================

[kirby urner]

I tend to give Ada Byron a lot of credit for the whole idea of software.  Not that loom guy.

http://code.activestate.com/lists/python-edu-sig/10662/  

(random Kirby re Ada per usual, has link to my essay contra New Yorker attempt at character assassination and failed attempt to take her title as "first computer programmer").

Kirby

--
You received this message because you are subscribed to the Google Groups "MathFuture" group.
To unsubscribe from this group and stop receiving emails from it, send an email to mathfuture+...@googlegroups.com.
To post to this group, send email to mathf...@googlegroups.com.
Visit this group at http://groups.google.com/group/mathfuture.
For more options, visit https://groups.google.com/d/optout.

[michel paul]

Yeah, I also prefer to say that Ada was the first programmer. I took the expression 'invention of software' from the article, but that's not necessarily the most accurate expression.

The accurate point is that Turing's achievement was abstract. A Turing machine is an idea rather than the latest trend setting gadget or app. Turing gave us a vision, and that is what a theory really is about. 

--

[kirby urner]

I just referred a career cryptographer to the movie, someone who cracked codes in the Vietnam Era and then worked for the NSA in Maryland HQS.

He was then more a back to the land guy, raising a family off the grid, before becoming a city rat in old age, more like me (very city rat, but no military).

Anyway, like me, Glenn realized The Imitation Game was hugely fictionalized, made a Hollywood film for movie-goers (a truism?). 

I think it bothered him more than it bothered me.  I'm like:  "it's a comic book;  the important thing is now more people know" about that chapter in history.

Even a Hollywood version is better than nothing, I guess my thinking is.

We both read Neal Stephenon's Cryptonomicon, also fictionalized, and ripe for turning into a film (we think).  Lots about Enigma / Turing in that one.

My background is philosophy and Wittgenstein's in particular. 

Alan Turing was one of LW's students, around the time H.S.M Coxeter was letting them borrow his suite for small groups.

Kirby

[Ted Kosan]

Michel wrote:

> Turing's great achievement was not the construction of computational
> machinery per se but supplying a theory of computation.

The formalized notion of computability is characterized by the
following three equivalent formalizations (one of which is Turing’s
theory):

------------------------------
Before a precise definition of computation was developed,
mathematicians often used the informal term “effectively calculable”
to describe functions that are computable by paper-and-pencil methods.
In the 1930s, several independent attempts were made to formalize the
notion of computability:

1) In 1933, Austrian-American mathematician Kurt Gödel, with Jacques
Herbrand, created a formal definition of a class called general
recursive functions. The class of general recursive functions is the
smallest class of functions (possibly with more than one argument)
which includes all constant functions, projections, the successor
function, and which is closed under function composition and
recursion.

2) In 1936, Alonzo Church created a method for defining functions
called the λ-calculus. Within λ-calculus, he defined an encoding of
the natural numbers called the Church numerals. A function on the
natural numbers is called λ-computable if the corresponding function
on the Church numerals can be represented by a term of the λ-calculus.

3) Also in 1936, before learning of Church's work, Alan Turing created
a theoretical model for machines, now called Turing machines, that
could carry out calculations from inputs by manipulating symbols on a
tape. Given a suitable encoding of the natural numbers as sequences of
symbols, a function on the natural numbers is called Turing computable
if some Turing machine computes the corresponding function on encoded
natural numbers.

Church and Turing proved that these three formally defined classes of
computable functions coincide: a function is λ-computable if and only
if it is Turing computable if and only if it is general recursive.
This has led mathematicians and computer scientists to believe that
the concept of computability is accurately characterized by these
three equivalent processes.

On the other hand, the Church–Turing thesis states that the above
three formally defined classes of computable functions coincide with
the informal notion of an effectively calculable function.
------------------------------
(http://en.wikipedia.org/wiki/Church%E2%80%93Turing_thesis)


In addition to being mathematicians, Gödel, Herbrand, Church, and
Turing were also formal logicians. I think this indicates that to
fully understand these three formalizations of computability, one must
first have a solid understanding of formal logic. However, I think
most computer programmers have had enough exposure to formal logic to
gain an intuitive understanding of parts of these formalizations.

For example, most microprocessors are based on the Von Neumann
architecture, and the Von Neumann architecture is based on the concept
of a Turing machine.
(http://en.wikipedia.org/wiki/Universal_Turing_machine) The only
computer language that these microprocessors “understand” is machine
language (which can be created directly from the low-level language
called assembly language). (http://en.wikipedia.org/wiki/Machine_code)
Therefore, if someone understands a Turing machine, they have what can
be thought of as a low-level language understanding of computation.

Most programmers don’t learn assembly language as their first computer
programming language because its very low-level of abstraction makes
it difficult to grasp the fundamental concepts of programming. They
learn a high-level language instead. Even though machine language can
be created directly from assembly language, most machine language is
created by the transFORMation of high-level language programs into
equivalent machine language programs using a compiler.

General recursive functions and the lambda calculus are analogous to
high-level computer programing languages. For example, one of the
highest-level computer programming languages is Lisp, and Lisp is
directly based on the lambda calculus. High-level languages and
machine languages are equivalent because the above three concepts of
computation are equivalent.

Just like most beginning programmers should not study machine language
first, most people who are interested in learning how computation
works should not start by studying Turning machines. Instead, they
should study general recursive functions and the lambda calculus
before studying Turing machines. Also, every programming language is a
formal language (http://en.wikipedia.org/wiki/Formal_language). Anyone
who wants to understand what a programming language is must first
understand what a formal language is.

Ted

[kirby urner]

On Sun, Mar 1, 2015 at 9:08 AM, Ted Kosan <ted....@gmail.com> wrote:

<< SNIP >>
 

2) In 1936, Alonzo Church created a method for defining functions
called the λ-calculus. Within λ-calculus, he defined an encoding of
the natural numbers called the Church numerals. A function on the
natural numbers is called λ-computable if the corresponding function
on the Church numerals can be represented by a term of the λ-calculus.

Yes, he chose  λ somewhat at random by his own account.

On Math Forum / math-teach I recommend we help high school

Algebra students plot a course forward by packaging it in the form

of a choice:

Delta Calc or Lambda Calc?

http://worldgame.blogspot.com/2014/09/lambda-versus-delta.html

Not that you can't take both, but in Oregon and some other states,

three years of math is required and I can understand a student

wanting to forgo pre-calc in favor of something more REPL-base
(console based) and lambda-calc informed.

3) Also in 1936, before learning of Church's work, Alan Turing created
a theoretical model for machines, now called Turing machines, that
could carry out calculations from inputs by manipulating symbols on a
tape. Given a suitable encoding of the natural numbers as sequences of
symbols, a function on the natural numbers is called Turing computable
if some Turing machine computes the corresponding function on encoded
natural numbers.

Wolfram waited until later in the game to publish A New Kind of Science (NKS).

I have some Python code for doing NKS work with a subclass of "Tractor".

A Tractor class is your basic read / write head in a Field (where tractors "plow").

https://mail.python.org/pipermail/edu-sig/2013-September/010887.html

http://4dsolutions.net/presentations/pycon2013.pdf


 

Praise Allah for Donald Knuth and The Art of Computer Programming.

In this foundational series, Dr. Knuth introduces MMIX and later the parallel

version, a fictional (but doable) assembly language that helps CS people

keep their edge over liberal arts dabblers (like me, a philo grad, but also a

Knuth fan for sure).

http://en.wikipedia.org/wiki/MMIX
 

General recursive functions and the lambda calculus are analogous to
high-level computer programing languages. For example, one of the
highest-level computer programming languages is Lisp, and Lisp is
directly based on the lambda calculus. High-level languages and
machine languages are equivalent because the above three concepts of
computation are equivalent.

Python has "little lambda".  E.g.:  identity_function = lambda x: x

In my "faux" or "cyber" geography lecture to "GIS In Action" (a conference,
where I gave like a keynote), I talked about the Great Lambda Worshipers
to the North (as if LISP /Scheme / Racket were a "place" with Python a
"nation").  Or maybe I just talked about Republic of Perl in that lecture.

You can see Guido's house from there.

http://www.4dsolutions.net/presentations/gis_2009_workshop.pdf

 

Just like most beginning programmers should not study machine language
first, most people who are interested in learning how computation
works should not start by studying Turning machines. Instead, they
should study general recursive functions and the lambda calculus
before studying Turing machines. Also, every programming language is a
formal language (http://en.wikipedia.org/wiki/Formal_language). Anyone
who wants to understand what a programming language is must first
understand what a formal language is.

Ted

Excellent post, thanks.

Kirby

[Ted Kosan]

Kirby wrote:

> On Math Forum / math-teach I recommend we help high school
> Algebra students plot a course forward by packaging it in the form
> of a choice:
>
> Delta Calc or Lambda Calc?
>
> http://worldgame.blogspot.com/2014/09/lambda-versus-delta.html
>
> Not that you can't take both, but in Oregon and some other states,
> three years of math is required and I can understand a student
> wanting to forgo pre-calc in favor of something more REPL-base
> (console based) and lambda-calc informed.

Your idea of lambda vs. delta is very interesting. I am looking
forward to reading more of you thoughts on this topic.

Ted

[kirby urner]

Mostly I've just showcased on math-teach (Math Forum) how one
might work that way of talking into the lingo.  I write about:

(A) the lambda track (more CS-friendly) and
(B) the more traditional AP / IB delta track (differential calculus).

... with a fork in the road after Algebra. 

Lambda calc branches off Algebra where we talk about composition
of functions g(f(x)) and turn that into an operator (composition operator). 

Given the open circle (◦)is somewhat hard to come by on most
keyboards, this is also a place to introduce operator overloading i.e.

g(f(x)) == (g * f)(x)

where * means "to compose" (a re-purposed multiplication sign --

some languages allow this).  We're on our way in lambda calc

with the above, on our way to the Tulgey Wood (the wild world

of the Internet and so on). [0]  Once you start doing operator

overloading, it's easier to introduce abstract algebra concepts.

Historical review:

We had some lobbying here in Oregon, me a player, starting around
2009 saying a Discrete and/or Computational math course should
count towards the three year math requirement, in contrast to
making everything CS-friendly "elective" as in "doesn't count". [1]

We were successful in this endeavor as were many states, so

now I think we're ready for a flood of pioneering curricula that

showcase what I often call Gnu Math (a pun on New Math) with

an REPL (interactive console -- not just a calculator) front and

center. [2]

One of the textbooks we flashed around in the lobbying chapter

was this one, from Skylit Press:

http://www.skylit.com/mathandpython.html

Over on math-teach, even the Florida conservatives like Bob Hansen

can't deny such a textbook holds water.  It's used at Phillips / Andover,

a top prep school in the nation, where the authors teach.  The intro is

telling, saying:  you could use this on a math track, to make it CS

flavored, or you could use it as a CS course that's mathy.  Either way.

Or call it STEM.

More analysis: 

I think the floodgates on new curricula have yet to reallyopen
because people still think we're playing the 1980s "winner take all"
sweepstakes when California and Texas picked their textbooks

and everyone fell into place behind them, as those were the big

numbers and the big demographics.  People are waiting to see
"who wins". 

But now, with electronic media, PDFs and all that, there's really
no economics to back up that waiting game.  The marginal costs
of each wood pulp unit (textbook) used to be the driving cost i.e.
to make a math text economical you needed a whole lot of them
(truck load upon truck load, so much fossil fuel).

But now we just look at our tablets and notebooks and don't

think about lugging around those giant tomes as much.

Helping schools themselves gain more authority to source their own
curriculum in a place-based mode is my objective, not "one size
fits all" with one textbook shared by all.  Diversity beats uniformity,

what biology teaches us, which is why these "math wars" but not
something to be uber-concerned about.[3]  There's a healthy give
and take of views, public debate, and that's a sign of things working,
not a sign of trouble or broken process. 

Big wheels turn slowly.  That's like a law of physics.

Kirby

Abbreviations:

CS = computer science

IB = International Baccalaureate

PDF = Portable Document Format

AP = Advanced Placement

REPL = Read, Evaluate Print Loop

STEM = Science Technology Engineering Mathematics

(I add Anthropology for STEAM but the more ethnocentric want Art)

NOTES:

[0]  http://en.wiktionary.org/wiki/tulgey

[1]  http://worldgame.blogspot.com/2009/08/education-planning.html

(getting started on State of Oregon lobby efforts six years ago)

[2]  REPL:  http://en.wikipedia.org/wiki/Read%E2%80%93eval%E2%80%93print_loop

[3]  http://wikieducator.org/Digital_Math (Martian Math is what I focus

on here on mathfuture, because its futuristic).