This is excellent. Starting with a physical computing system, built from basic parts, the individual operation of which can be simulated with transistors and other passive devices, such as resistors, capacitors and diodes, Ben Eater explains what Universal Conputability is (that is not a typo!) and how it can be demonstrated in practice, on this concrete, tangible machine, built from electronic components which can be seen, in principle, with the naked eye.
I still don't have a clue what this is about, or why it seems so sad, ...
This will surely be a significant part of the explanation, which I think will start becoming apparent in the next few days: see Interesting Fragment of Early History of the West German Intelligence Agency.
See On Law Enforcement and Scientific Knowledge. The US/UK "special relationship" was something which had existed before the United States: it dates back to Benjamin Franklin's stay in London, just before the Declaration of Independence, when he was awarded an honorary doctorate by Oxford University. But the special relationship was reinvigorated in the 1940's by Alan Turing's collaboration with Alonzo Church and Kurt Gödel at Princeton. In 1940, Church published a paper entitled A Formulation of the Simple Theory of Types, (also available from JSTOR, the official source, at http://www.jstor.org/stable/2266170) which describes a formal system of calculation and proof which, quite literally transcends the limited notion of computability which Turing, Kleene and Church had settled on in the pre-war years. This system, which was a typed lambda calculus, is not limited to the computation of partial recursive functions: it can calculate the much larger set of total recursive functions. This system was derived from the one described by Ada Augusta Lovelace in her "notes", published in 1843. Here are the last four theorems proved by the system:
In fact, this theorem scheme, 43 alpha, is the only theorem the system needs to be able to be able to prove. [It turns out that is not a typo either. See scheme 40 alpha.]. Every other theorem is proved as an inner model of this infinite set which is computed as a total function on the set of positive non-zero integers. See John H. Conway on Weird Programming Languages.
... and the sequel is even better, ...
For an answer to how types fit into this general scheme, see Damas and Milner's paper Principal Type Schemes for Functional Programs. Note the slightly gnomic-sounding comment at the end of section 4 on page 4:
This seems to be referring to some kind of inner model of the polymorphic type system's semantics. Now see this, from the introduction to The Definition of Standard ML, by Robin Milner, Mads Tofte, Robert Harper and David MacQueen, and it's about language design in very general terms.
I haven't looked at Harvey Friedman's proof of the number of symbols you would need to prove TREE(3) is finite in finite arithmetic, but I think he must have made some sort of assumption about the metalanguage syntax that is not necessary. See, for example Peter Hurford on diagonalising Conway's Chained Arrow Notation. The point is that you could define the semantics of finite arithmetic using Conway's notation, with Hurford's extension, starting with the exponential function, so I cannot see why the number of symbols and time to produce the proof is interesting. This article by Jean-Yves Girard sounds like it is relevant: The Skeleton in the Closet.
Robin Milner was a student of Dana Scott at Princeton, and Scott was a student of Alonzo Church. Shortly after arriving in Bolivia, I wrote this brief two-page note, hoping merely to spark discussion of something which I found interesting. It is untitled, but it could have been entitled On Tarski's Semantic Theory of Truth "Convention-T". I sent a few copies to various people by e-mail, including Ebbe Elsborg, Peter Sewell, Thomas Forster, and, I think, one or other of Mike Gordon or Larry Paulson at Cambridge. Mike Gordon was a student of Robin Milner at Edinburgh. The only acknowledgement I received was from Thomas Forster who was in New Zealand at the time, or on the point of departure from England.
Now, it turns out that Hindley-Milner type inference, with polymorphic type-schemes in the object language can type the lambda-calculus predecessor function without using type-raising operators, which are effectively Bertrand Russell's Singular Descriptions which he wrote about in On Denoting, and which is full of weird statements about the exact identity of anybody called simply Scott! You know, as in Great Scott! I had no fucking idea it was you! For details, on the polymorphic typing of the predecessor function, see The Hindley-Milner Type Inference Algorithm, which I wrote as a kind of tribute to Robin Milner, from whom, I think, I learned more than any other living person, even though we only ever had one conversation about philosophy, which was mostly me telling Robin what a wonderful essay is Brouwer's Life, Art, and Mysticism, as we cycled from J.J. Thompson Avenue, across Claire Bridge towards The Old Schools in Cambridge. Maybe that was my mistake? 😂
This tune reminds me of Arne Naess who is another philosopher I never had the opportunity to discuss anything with. But he did once tell me, -- slightly weirdly I thought, at the time -- "I like to watch you walk." It was as we walked back to The Old Postern at Dartington, in Devon, after attending some talk or other. The concrete path is so narrow, as it crosses a farmer's field, and fenced on both sides, that it makes it impracticable for anyone but a pair of lovers to walk to along side-by side, so I walked ahead, as it was dark, and I thought that I would rather I trip over something in the gloom than him.
Apart from Sir Winston Churchill, Arne Naess is the only philosopher I recall who was quoted by Karl Popper. So I think Arne's strange-sounding comment was a reference to peripatetia. Maybe I should get around to reading Aristotle On The Gaits of Animals. I think it will transpire that philosophers are immortal, down to polymorphism.
It ought to interest some physicists, Roger Penrose in particular, that computation as defined in this polymorphic type scheme, is reversible, because the sheme models all the total functions between domains as bijections, so all functions have inverses. Combined with the thermodynamic ideas in this essay ”Process Synchronisation by Communication”, which I typed in 2015, should give people some ideas about how to build practical computing machines which are thermodynamically reversible, thanks to Joseph Fourier (see Measuring Ignorance and this strange essay which is all about final cause in modern physics.
As to the enigma behind Pink Floyd's "Marooned", it will surely turn out that Pontryagin duality will be central.
Here's a fun game of games, and a wild conjecture, which might amuse someone with time in their hands: it is from Conway's FRACTRAN talk, which he gave at Berkeley in 1996. See John H. Conway on Weird Programming Languages. In this video, Conway describes a generalization of the Collatz problem, which he calls the n-game. Hmmm, ...
So here is an idea you might want to try:
Generalised Collatz problem:
n --> a_i n + b_i if n = i mod p
With p = 2, and a_0 = 1/2, b_0 = 0, a_1 = 3, b_1 = 1, then we can write the Collatz problem as
n_i,j+1 = [[1/2,0],[3,1]] n_i,j for i = 0,1
These are linear functions of n. So as we increase p, we build up a pair of p-vectors, and this generates a list of lists of vector spaces where each is spanned by the next space in the sequence, ...
Can we not then generalise it further still, and consider polynomials in p, which could be successive Padé approximants to some function of a complex variable?
n_i,j+1,p = Sigma_k=0,p-1 a_i,j,k (n_i,j,k)^k
For the Collatz problem, we would be looking at integer solutions, which might correspond to the roots of the Padé basis functions, ... I'm just talking out of my hat, you try it, ...
Suggests to me that the Collatz sequence might be the encoding of a search for non-trivial zeros of the Riemann Zeta function on Re(s) = 1/2, or something like that, ... see p-adic number, Stern–Brocot tree and Pontryagin duality.
See this excellent lecture by Neil Wildberger on Lagrange's differential geometry of analytic functions for an idea of how this might work. See also Surfing the Cloud for an example of how this way of looking at differential calculus is useful in numerical methods. Look for "laying text out on an ellipse" in the code at the end.
Here's part II:
Man, I just can't get ahead of this guy! This stuff works on finite fields:
At 34 minutes 13 seconds, this is where brachistochrones enter the picture: see All About e and Quaternions Visualised.
Now watch this:
I have a feeling that we can come up with a better definition of a complex logarithm function, which will approximate ln(z) by a series, the elements of which will yield stable ways to numerically solve (and therefore to systematically find all the roots of) complex differential equations: see Aristotle on The Continuum
Just forget about the prizes for solving "hard problems", they're complete bullshit and seem to be some sort of prison sentence, ... I'll never forget seeing Andrew Wiles crying on camera when he talked about the moment he managed to finish his proof of Fermat's last theorem, ... another Princeton IAS refugee, ... from what, for fuck's sake! This is just too fucking stupid for words!
And don't get me started on Anton Rubik and the Free Will Theorem! Cue video:
This reminds me a beautiful Japanese-Australian girl called Sarah whom I met in Budapest in what I thought was 1989, but which now seems to have been 1990, ...
And this was the first piece of classical music that really gripped me, ...
... and, for some reason I know not, this just sounds like the natural sequel, ...
... from which follows, ...
... and then ...
... now, if there really is a nuclear bomb under an old air-base near Reading, ... how would we know for sure that it really is a threat? What other sorts of threat does humanity face? Why can't we just forget about the nuclear bomb, for a while, since there's apparently fuck-all that anyone can do about it anyway, and instead we can concentrate on helping other people with their problems. You never know, after a few years of doing that, someone else might've solved your problem, for you, ...
Great Scott! No wonder you have no fucking idea who you are!
Movies!
Madonna's lyrics have driven them all nuts!
Oh babe, any day! But promise me to always eat your boiled eggs with a little spoon, from an egg-cup, otherwise the people in Hollywood will go completely insane when they realise what they did to me, with a bit of help from Alan Parker. Funny guy, that Alan Parker! Surprised he didn't also make a film called Edge of Darkness, ...
I now realise that that FBI guy I told about this programme didn't have a fucking clue what I was talking about, even though I said it was made by the BBC, ...
... but he did tell me it was "beautiful", ... so, ... it can't have been this he was thinking of, can it?
Maybe he meant the sound track?
Serious shit, that! What does all this have to do with computing? Well, just eyeballing them might not be good enough, you will want to be sure your transistors work the way you think they do, so listen to Jeri, ... but don't be distracted by the fact that it's NMOS, ...
... and you'll want to check how semiconductor lattice's work, ... hint: 3D matrix laser pinball, see Feynman on Patents and the Value of an Idea, ... then you can start your own chip cooking facility, ... it doesn't have to be in Wales, ...
... but do be careful about what happens when you carry one of these things all the way around the world, ... you'll want to make sure it's the right way up, you see. UK MPs aren't worried about this, so that's alright, then. UK MPs seize control of parliament to try & block a no-deal Brexit.
Now, how does this relate to computability v. conputability? It's all to do with Les montres à moutarde de Jean-Yves Girard, which I called "incommensurable hair-splitting in the time-domain", and which is a key element in linear logic and has some practical applications in digital analogic computing and communications. Here's Jeri Ellsworth putting it into practice:
That, folks, is how you implement an infinite tape on your finite state Universal Turing machine, and you can use Standard ML to define the semantics soundly. So somebody please tell Frank Stajano, who now appears to be at Google doing AI, presumably in Python, on non-universal, finite machines with finite tapes, ....
Let's use this idea to build a kick-ass video card that describes video images using differential equations, which Dijkstra called "fancy languages" for the message interpreter: see What is a Screen, Really?, The T.H.E. Multiprogramming System Mk II and What is a user interface supposed to do?
Hey, Frank, I'm not Brown Dan in anything, but I am Green Hanky in twatting little cunts who just don't know when to give-up:
Don't I deserve some sort of endurance fellowship award? I am suffering from that "funny correctness criterion" Girard calls "the long-trip condition"! Over a quarter of a fucking century!
See FOM Rejection
I still don't have a clue what this is about, or why it seems so sad, ...
This will surely be a significant part of the explanation, which I think will start becoming apparent in the next few days: see Interesting Fragment of Early History of the West German Intelligence Agency.
See On Law Enforcement and Scientific Knowledge. The US/UK "special relationship" was something which had existed before the United States: it dates back to Benjamin Franklin's stay in London, just before the Declaration of Independence, when he was awarded an honorary doctorate by Oxford University. But the special relationship was reinvigorated in the 1940's by Alan Turing's collaboration with Alonzo Church and Kurt Gödel at Princeton. In 1940, Church published a paper entitled A Formulation of the Simple Theory of Types, (also available from JSTOR, the official source, at http://www.jstor.org/stable/2266170) which describes a formal system of calculation and proof which, quite literally transcends the limited notion of computability which Turing, Kleene and Church had settled on in the pre-war years. This system, which was a typed lambda calculus, is not limited to the computation of partial recursive functions: it can calculate the much larger set of total recursive functions. This system was derived from the one described by Ada Augusta Lovelace in her "notes", published in 1843. Here are the last four theorems proved by the system:
In fact, this theorem scheme, 43 alpha, is the only theorem the system needs to be able to be able to prove. [It turns out that is not a typo either. See scheme 40 alpha.]. Every other theorem is proved as an inner model of this infinite set which is computed as a total function on the set of positive non-zero integers. See John H. Conway on Weird Programming Languages.
... and the sequel is even better, ...
For an answer to how types fit into this general scheme, see Damas and Milner's paper Principal Type Schemes for Functional Programs. Note the slightly gnomic-sounding comment at the end of section 4 on page 4:
The job of a language-definer is twofold. First – as we have already suggested – he must create a world of meanings appropriate for the language, and must find a way of saying what these meanings precisely are. Here, he meets a problem; notation of some kind must be used to denote and describe these meanings – but not a programming language notation, unless he is passing the buck and defining one programming language in terms of another. ...
... The second part of the definer’s job is to define evaluation precisely. This means that he must define at least what meaning, M, results from evaluating any phrase P of his language (though he need not explain exactly how the meaning results; that is he need not give the full detail of every computation). This part of his job must be formal to some extent, if only because the phrases P of his language are indeed formal objects. But there is another reason for formality. The task is complex and error-prone, and therefore demands a high level of explicit organisation (which is, largely, the meaning of ‘formality’); moreover, it will be used to specify an equally complex, error-prone and formal construction: an implementation. We shall now explain the keystone of our semantic method. First, we need a slight but important refinement. A phrase P is never evaluated in vacuo to a meaning M, but always against a background; this background – call it B – is itself a semantic object, being a distillation of the meanings preserved from evaluation of earlier phrases (typically variable declarations, procedure declarations, etc.). In fact evaluation is background-dependent – M depends upon B as well as upon P.
The keystone of the method, then, is a certain kind of assertion about evaluation; it takes the form
B |-- P ⇒ M
and may be pronounced: ‘Against the background B, the phrase P evaluates to the meaning M’. The formal purpose of this Definition is no more, and no less, than to decree exactly which assertions of this form are true. [their emphasis, not mine.]This explains the true motivation for let-polymorphism in Principal Type Schemes for Functional Programs: the Standard ML interpreter is implemented as a polymorphic function it, of type forall alpha. alpha, and I suspect that by sing Standard ML's abstract types, together with imperative types, which provide a way to define unquantified polymorphic types at the top-level, this iteration can be continued trans-finitely. This ought to interest Harvey Friedman: see part II of this Numberphile video:
I haven't looked at Harvey Friedman's proof of the number of symbols you would need to prove TREE(3) is finite in finite arithmetic, but I think he must have made some sort of assumption about the metalanguage syntax that is not necessary. See, for example Peter Hurford on diagonalising Conway's Chained Arrow Notation. The point is that you could define the semantics of finite arithmetic using Conway's notation, with Hurford's extension, starting with the exponential function, so I cannot see why the number of symbols and time to produce the proof is interesting. This article by Jean-Yves Girard sounds like it is relevant: The Skeleton in the Closet.
Robin Milner was a student of Dana Scott at Princeton, and Scott was a student of Alonzo Church. Shortly after arriving in Bolivia, I wrote this brief two-page note, hoping merely to spark discussion of something which I found interesting. It is untitled, but it could have been entitled On Tarski's Semantic Theory of Truth "Convention-T". I sent a few copies to various people by e-mail, including Ebbe Elsborg, Peter Sewell, Thomas Forster, and, I think, one or other of Mike Gordon or Larry Paulson at Cambridge. Mike Gordon was a student of Robin Milner at Edinburgh. The only acknowledgement I received was from Thomas Forster who was in New Zealand at the time, or on the point of departure from England.
Now, it turns out that Hindley-Milner type inference, with polymorphic type-schemes in the object language can type the lambda-calculus predecessor function without using type-raising operators, which are effectively Bertrand Russell's Singular Descriptions which he wrote about in On Denoting, and which is full of weird statements about the exact identity of anybody called simply Scott! You know, as in Great Scott! I had no fucking idea it was you! For details, on the polymorphic typing of the predecessor function, see The Hindley-Milner Type Inference Algorithm, which I wrote as a kind of tribute to Robin Milner, from whom, I think, I learned more than any other living person, even though we only ever had one conversation about philosophy, which was mostly me telling Robin what a wonderful essay is Brouwer's Life, Art, and Mysticism, as we cycled from J.J. Thompson Avenue, across Claire Bridge towards The Old Schools in Cambridge. Maybe that was my mistake? 😂
This tune reminds me of Arne Naess who is another philosopher I never had the opportunity to discuss anything with. But he did once tell me, -- slightly weirdly I thought, at the time -- "I like to watch you walk." It was as we walked back to The Old Postern at Dartington, in Devon, after attending some talk or other. The concrete path is so narrow, as it crosses a farmer's field, and fenced on both sides, that it makes it impracticable for anyone but a pair of lovers to walk to along side-by side, so I walked ahead, as it was dark, and I thought that I would rather I trip over something in the gloom than him.
Apart from Sir Winston Churchill, Arne Naess is the only philosopher I recall who was quoted by Karl Popper. So I think Arne's strange-sounding comment was a reference to peripatetia. Maybe I should get around to reading Aristotle On The Gaits of Animals. I think it will transpire that philosophers are immortal, down to polymorphism.
It ought to interest some physicists, Roger Penrose in particular, that computation as defined in this polymorphic type scheme, is reversible, because the sheme models all the total functions between domains as bijections, so all functions have inverses. Combined with the thermodynamic ideas in this essay ”Process Synchronisation by Communication”, which I typed in 2015, should give people some ideas about how to build practical computing machines which are thermodynamically reversible, thanks to Joseph Fourier (see Measuring Ignorance and this strange essay which is all about final cause in modern physics.
As to the enigma behind Pink Floyd's "Marooned", it will surely turn out that Pontryagin duality will be central.
Here's a fun game of games, and a wild conjecture, which might amuse someone with time in their hands: it is from Conway's FRACTRAN talk, which he gave at Berkeley in 1996. See John H. Conway on Weird Programming Languages. In this video, Conway describes a generalization of the Collatz problem, which he calls the n-game. Hmmm, ...
So here is an idea you might want to try:
Generalised Collatz problem:
n --> a_i n + b_i if n = i mod p
With p = 2, and a_0 = 1/2, b_0 = 0, a_1 = 3, b_1 = 1, then we can write the Collatz problem as
n_i,j+1 = [[1/2,0],[3,1]] n_i,j for i = 0,1
These are linear functions of n. So as we increase p, we build up a pair of p-vectors, and this generates a list of lists of vector spaces where each is spanned by the next space in the sequence, ...
Can we not then generalise it further still, and consider polynomials in p, which could be successive Padé approximants to some function of a complex variable?
n_i,j+1,p = Sigma_k=0,p-1 a_i,j,k (n_i,j,k)^k
For the Collatz problem, we would be looking at integer solutions, which might correspond to the roots of the Padé basis functions, ... I'm just talking out of my hat, you try it, ...
Suggests to me that the Collatz sequence might be the encoding of a search for non-trivial zeros of the Riemann Zeta function on Re(s) = 1/2, or something like that, ... see p-adic number, Stern–Brocot tree and Pontryagin duality.
See this excellent lecture by Neil Wildberger on Lagrange's differential geometry of analytic functions for an idea of how this might work. See also Surfing the Cloud for an example of how this way of looking at differential calculus is useful in numerical methods. Look for "laying text out on an ellipse" in the code at the end.
Here's part II:
Man, I just can't get ahead of this guy! This stuff works on finite fields:
At 34 minutes 13 seconds, this is where brachistochrones enter the picture: see All About e and Quaternions Visualised.
Now watch this:
I have a feeling that we can come up with a better definition of a complex logarithm function, which will approximate ln(z) by a series, the elements of which will yield stable ways to numerically solve (and therefore to systematically find all the roots of) complex differential equations: see Aristotle on The Continuum
Just forget about the prizes for solving "hard problems", they're complete bullshit and seem to be some sort of prison sentence, ... I'll never forget seeing Andrew Wiles crying on camera when he talked about the moment he managed to finish his proof of Fermat's last theorem, ... another Princeton IAS refugee, ... from what, for fuck's sake! This is just too fucking stupid for words!
And don't get me started on Anton Rubik and the Free Will Theorem! Cue video:
This reminds me a beautiful Japanese-Australian girl called Sarah whom I met in Budapest in what I thought was 1989, but which now seems to have been 1990, ...
And this was the first piece of classical music that really gripped me, ...
... and, for some reason I know not, this just sounds like the natural sequel, ...
... from which follows, ...
... and then ...
... now, if there really is a nuclear bomb under an old air-base near Reading, ... how would we know for sure that it really is a threat? What other sorts of threat does humanity face? Why can't we just forget about the nuclear bomb, for a while, since there's apparently fuck-all that anyone can do about it anyway, and instead we can concentrate on helping other people with their problems. You never know, after a few years of doing that, someone else might've solved your problem, for you, ...
Great Scott! No wonder you have no fucking idea who you are!
Movies!
Madonna's lyrics have driven them all nuts!
Oh babe, any day! But promise me to always eat your boiled eggs with a little spoon, from an egg-cup, otherwise the people in Hollywood will go completely insane when they realise what they did to me, with a bit of help from Alan Parker. Funny guy, that Alan Parker! Surprised he didn't also make a film called Edge of Darkness, ...
I now realise that that FBI guy I told about this programme didn't have a fucking clue what I was talking about, even though I said it was made by the BBC, ...
... but he did tell me it was "beautiful", ... so, ... it can't have been this he was thinking of, can it?
Maybe he meant the sound track?
Serious shit, that! What does all this have to do with computing? Well, just eyeballing them might not be good enough, you will want to be sure your transistors work the way you think they do, so listen to Jeri, ... but don't be distracted by the fact that it's NMOS, ...
... and you'll want to check how semiconductor lattice's work, ... hint: 3D matrix laser pinball, see Feynman on Patents and the Value of an Idea, ... then you can start your own chip cooking facility, ... it doesn't have to be in Wales, ...
... but do be careful about what happens when you carry one of these things all the way around the world, ... you'll want to make sure it's the right way up, you see. UK MPs aren't worried about this, so that's alright, then. UK MPs seize control of parliament to try & block a no-deal Brexit.
Now, how does this relate to computability v. conputability? It's all to do with Les montres à moutarde de Jean-Yves Girard, which I called "incommensurable hair-splitting in the time-domain", and which is a key element in linear logic and has some practical applications in digital analogic computing and communications. Here's Jeri Ellsworth putting it into practice:
That, folks, is how you implement an infinite tape on your finite state Universal Turing machine, and you can use Standard ML to define the semantics soundly. So somebody please tell Frank Stajano, who now appears to be at Google doing AI, presumably in Python, on non-universal, finite machines with finite tapes, ....
Let's use this idea to build a kick-ass video card that describes video images using differential equations, which Dijkstra called "fancy languages" for the message interpreter: see What is a Screen, Really?, The T.H.E. Multiprogramming System Mk II and What is a user interface supposed to do?
Hey, Frank, I'm not Brown Dan in anything, but I am Green Hanky in twatting little cunts who just don't know when to give-up:
Don't I deserve some sort of endurance fellowship award? I am suffering from that "funny correctness criterion" Girard calls "the long-trip condition"! Over a quarter of a fucking century!
See FOM Rejection
No comments:
Post a Comment