“Timing Toast”, by Piet Hein:

There’s an art of knowing when.
Never try to guess.
Toast until it smokes and then
twenty seconds less.

This sounds really, really doubtful to me. I knew Iverson reasonably well and worked with him at the IBM Philadelphia Scientific Center. He knew an awful lot of mathematics and computing, and I’m absolutely sure he knew about Turing.

Iverson was concerned with notation and expressibility. The claim above has all the hallmarks of a misunderstanding that has been repeated multiple times and changed in the telling.

Certain programs have the property that they manipulate their input data in a “type-safe” way. That is, if the encoding of the input data is changed, then the program will continue to run correctly as long as the data is accessed through the proper channels. This is an extremely important property in practice, and one of the major focuses of high-level language design is ensuring type safety. In fact, I would say one of the most important things that a program expresses, perhaps more important even than its semantics, is the interaction of its data structures.

In a Turing machine, all the data accesses are “flattened out” to pure bit manipulation. In this way, a Turing machine can never be type safe, because it lacks the formalism to specify which data accesses are properly controlled.

This is an example of a important aspect of computation that can be expressed only in high-level languages, not Turing machines.

What do you people think about nondiscrete models of computation as possible counterexamples to the Church-Turing thesis?

http://edelstein.huji.ac.il/staff/shagrir/papers/physical_computation.pdf
(section 3)

I remember other papers but cannot find the references.

I think the Church-Turing thesis for those models is that continuous computation modulo finite precision measurement and setup of computing apparati is equivalent to classical computation.

And do you think that continuous models of computation with beyond-Turing capability (before imposing feasibility assumptions) are useful?

Any reference?

“Common-sense must be used here to avoid embarking on an over-axiomatized, and hence misguided, piece of theoretical physics. We [\hellip;] should not be trapped into axiomatizing theoretical ideas out of existence.”
   — Christopher Isham (1984)

(quoted in Matthias Blau’s popular on-line lecture notes “Symplectic geometry and geometric quantization” (1992).

Isham’s remark descends from

“If one finds a difficulty in a calculation which is otherwise quite convincing, one should not push the difficulty away; one should rather try to make it the centre of the whole thing.”
   — Werner Heisenberg (1971)

(which a Google search finds quoted in many places)

Here the point is that a great deal of heat commonly is generated — especially in the blogosphere — when postulates are mistaken for and/or claimed to be deductions. And the rhetorical motivation for such claims is evident: the correctness of deductions can be verified by more-or-less irrefutable reasoning … the correctness of postulates is susceptible to no such checks!

Testbooks on complexity theory (example: Arora and Barak Computational Complexity: a Modern Approach) and books on quantum theory (example: Nielsen and Chuang Quantum Computation and Quantum Information) generically begin with a statement of postulates. Three questions then are natural.

Q1  What is the likelihood that the reasoning of standard textbooks is globally and seriously flawed? Both common-sense and history indicate that this likelihood is vanishingly small.

Q2  What is the likelihood that, in coming decades, the postulates of 20th century textbooks will be appreciated as mathematically limiting and/or physically unrealistic? Both common-sense and history indicate that this likelihood is sufficiently great as to amount to a near-certainty.

Q3  What new and/or amended postulates, regarding complexity theory and/or quantum dynamics, will the great textbooks of the 21st century embrace? We are very unlikely to collectively appreciate the answer to this question … until someone writes these textbooks.  

It is a pretty safe bet — if we are guided by Isham and Heisenberg — that the amended complexity/quantum theoretic postulates of the 21st century will originate in physical concepts rather than reasoning from axioms (Isham’s principle) and that these postulates will embrace as central, difficulties that at present are regarded as peripheral (Heisenberg’s principle).

Conclusion  Should we be skeptical of deductions that follow from the CT thesis? Reasonably, no. Should we be skeptical that the CT thesis provides uniquely optimal foundations for complexity theory? Reasonably, yes.

I recall my experience of learning formal logic. Prior to my university education, I would never have dreamed or imagined that natural language could be given a mathematical semantics. Learning formal logic was one of the most tedious experiences of my sophomore year of university and to date, I think the presentation of a lot of logic texts does not help this state of affairs. Still, it was completely amazing that the difference between “some child likes all chocolates” and “all chocolates are liked by some child” can be turned into a mathematical theorem. Even more amazing was the realisation that it was, in principle, possible to codify the language of mathematical theorems and proofs entirely in logical terms. This universality lead to the mind-blowing results of Goedel. Mind-blowing for me, not because of their content, but because it was possible at all to make statements that were about an entire area of mathematics, and not just about specific objects.

That was cool, but it is infeasible and feels rather inhuman to work purely with logical symbols (though I have observed people doing that, including a few programming language researchers). It is more comfortable for most working mathematicians and computer scientists to work with natural language, while being aware of the formalist underpinnings.

Moreover, once I understood better, the results of Goedel didn’t seem as universal. Gentzen for example did prove a completeness result.

The second example is about the independence of the continuum hypothesis from the Axiom of Choice. I was fascinated to learn that there were models of set theory that could be constructed using forcing. This in turn led to the realisation that the ZF and ZFC axioms for set-theory are axioms like any other and the universe of sets we work in in day-to-day mathematics is a model of a set of axioms, like any other model. There are many axiom systems possible and many models.

Here’s the point of the reminiscence. Learning formal logic was a bit tedious but it felt like a rite of passage to a world where I could continue to do mathematics but with a far deeper understanding of the internal structure of that mathematics. The same applies to set-theory. At some point I realised that the kind of sets and operations on sets that we use are just specific models and there are many more possible and alternative interpretations of the membership predicate, for example. Once I knew better, the results I found mind-blowing initially remained fascinating, but definitely seemed less universal.

In a discussion of these areas and results, it is not clear to me how much this matters. Turing machines and the Church-Turing thesis feel similar to me. Learning to reduce between computational models and about the Church-Turing thesis feels like a rite of passage and one that reveals something deep and fascinating about computation. But the Church-Turing thesis also has a context, which from a specific perspective is not as universal as it may have first seemed.

And here’s where I feel at a bit of a loss. In the case of certain logical theorems, or independence results in set theory, or the Church-Turing thesis, there is a context in which those results are true and for most computer scientists that context is always in the background, but for some it is not. Does anyone see what I’m trying to say?

Still no answer to my questions on the other thread?

Would Umesh help?

LOL!

I know Ketan possibly couldn’t, because I know his collaborator Milind Sohoni, and came to know through Milind that neither of them could (which was in 2003/4). I don’t think they might have progressed in this matter sufficiently, in the meanwhile. And, separately, I do know, Manindra couldn’t—and that he would be ready to admit that he couldn’t.

As to one of those lesser known Indians, _if_ they fulfill the other important criteria, e.g. that they are not stooges of Americans (and, if I may expand, also Brits/Russians/etc.), sure do feel free to ask them. The matter is simple enough for highly honest and reasonably intelligent people.

Despite what so many Indians settled in the USA might make it look like, here, in India, an assuringly many number of Indians are far more thoughtful about such things. They do acknowledge the existence of so many Indians’ willingness to trade integrity for mere material comforts or powerlust as found in the advanced countries, the existence of stooges (a routine matter), etc. A relatively small minority of Indians settled in the USA also is thoughtful about such things, and do reach the same judgment about stooges and (really) influential Americans’ sick use of such stooges, etc. (Vivek Randive might be a borderline case of those who reach the right judgment in this issue, though personally I tend to have my own doubts. Vinod Khosla certainly isn’t one to fall on the better side. So many IITians very certainly aren’t. They would rather willingly obfuscate issues to hide the said trade of integrity with material comforts, powerlust, etc.)

As to people of Indian descent. If you mean those raised in the USA and all, I have not met too many of them to be able to form a judgment about them as a group. I know one Standford CS graduate girl of Indian descent who seemed a bit ill at ease while interacting with Indians (I mean people born and raised in India), esp. in front of the white folks of Abrahamic religions, esp. males. And, overall, I think she represents a trend, though I can’t be too sure—just too small a sample size, just too few interactions with these folks (popularly known as ABCDs). On the other side of the spectrum, I know of one Canadian girl of Indian descent (a Saradaran) who seemed perfectly at ease with people of all kind: Indians/NRIs/people of Indian descent, and white/black Abrahamics/others. I remain open, on this count—not even a temporary judgment thus far.

Let me check out if this comment makes it or not—sure, it is _your_ blog, Scott, not mine. But, yes, would Umesh help? Would it be possible for him to help? I do wonder.

Ajit
[E&OE]