## Comment viewing options

### mot-a-mot?

Google's translation software doesn't proceed word by word (I'm presuming that's what you mean by "mot-a-mot".) It is, however, a slave of its training set. Given an appropriate bilingual corpus that has sufficient evidence that the translation of "Birds of a feather flock together" should be "Qui se ressemble s'assemble", that is exactly the translation it should produce. Peter Norvig goes over the details in this video (starting at around 21:00.)

We're probably off-topic for LTU at this point...
 ... and, indeed, the parent appears to have disappeared.

### spam-mot

Sorry, I deleted that comment (before I saw any response) because it appeared to be spam for a translation service. The comment was not obviously illegitimate, but another one in a different thread by the same account was clearly nonsensical. The comments also violated the policy against signatures.

### Nice

I agree completely, trying to teach "computational thinking" without teaching some kind of programming language is asking for trouble. However many (most?) introductory programming courses don't really delve into computational thinking, instead wasting vast amounts of time on "objects", syntax, development tools, etc etc. Teachers need something lightweight so they can cut to the chase, and start talking about useful algorithms quickly.

One of my favorite algorithms is the euclidean algorithm: it's really easy to teach people, including children, what this notation means (in a purely operational sense) and how to execute it by hand:

gcd (x,0) = x
gcd (x,y) = gcd (y, x mod y)


Admittedly, sometimes I opt for repeated subtraction instead. Interestingly, most adults have never heard of the Euclidean algorithm, including some non-math, non-CS, but technical Ph.D. students.

I think this is something that should be taught hand in hand with fractions: here's a mysterious notation, here's how to execute it by hand, here's how to apply it to reducing fractions, and oh by the way, you can type it into a computer and let it do the work for you.

And that reminds me of a forum topic I've been thinking about posting for a while now: what language should a child's first programming language be?

### I like "funner" algorithms

I like "funner" algorithms than Euclid's GCD algorithm.

I have long wanted to write a book focused on interesting but easy to understand Computer Science problems. I have a pretty huge collection (in my head) of these sorts of problems. One that comes to mind is found in Magic Tricks, Card Shuffling and Dynamic Computer Memories by S. Brent Morris (Morris received a Ph.D. in computer science for card tricks). Likewise, Richard Korf received his Ph.D. in computer science for automated rubik's cube solvers. Also, Hans van Ditmarsch has done some very interesting stuff with so-called knowledge games, including a detailed study on the optimal strategy for playing Clue/Cluedo; he got his Ph.D. in mathematics by answering to the review committee exactly just who killed Professor Plum! See the project's gnuclue / cludos 2.0 archive.org home page from 2006 for a fun story on the project's history.

### Sounds like a fun project

Sounds like a fun project (pun definitely intended).

### Algorithmics

Are you familiar with Harels "Algorithmics" book? It does precisely this; a 'popular science' presentation of computer science topics with a lot of algorithms. I think it would make an excellent text for this type of course.

### I have all three editions of

I have all three editions of that book. I have read most of what Harel has written, since I consider him to be one of the great computer scientists.

I am not sure how well it parallels to what I am thinking, though. Could you elaborate?

### Karel the Robot

I wrote a "Karel the Robot" simulator for this, still one of my favourites.

### Scott-Strachey

I've been meaning to write up a talk I gave at the Foundations of the Formal Sciences IV conference for over 5 years now, which argued that the parallels between current problems in the philosophy of language and those in computer science go much deeper than most people realise.

I argued there that there are a number of schools of thought in computer science, with particular emphasis on what I called the Scott-Strachey school, characterised by its focus on programming languages as the central concept in computer science (as opposed to, e.g., abstract study of computational phenomena, the practical construction and use of computing machinery, or use-based study of human-computer interaction, each of which can claim to be fundamental to some school or another). The Scott-Strachey school, I claim, has a parallel to analytic philosophy, and its advent can be likened to the so-called linguistic turn.

I could say more, you know, but I risk drifting further off-topic...

### abstract study of

abstract study of computational phenomena

Not sure what this would mean. Perhaps you mean automata? Algorithms?

the practical construction and use of computing machinery

Hardware was adopted by Electrical and Computer Engineering. Most of the physical aspects of CS went to an engineering discipline.

use-based study of human-computer interaction

This is definitely an field ripe for development, though I'm not sure it falls under Computer Science.

CS's focus on languages and information systems seems appropriate to me.

### I've been finding HCI to be

I've been finding HCI to be an Achille's heel preventing a lot of PL and systems research from being meaningful. Try it out sometime.

### HCI-centrism

No school can be successful if it tries to explain everything in terms of one pole, but each of the poles can make sense. HCI-centrism isn't my favourite approach, but it does have things going for it.

### Perhaps I should be clearer.

Perhaps I should be clearer. There's an over-emphasis in HCI in optimizing for novice, child, or initial use -- though luckily it seems that there seems to be a rising backlash against the unbalance here. This is not what I'm referring to.

Many PL papers open up with "developers struggle to do x, so we propose to make it a linguistic (primitive | guarantee | ...)". We can describe a runtime to show it is a primitive or a proof to validate the guarantee, but that doesn't mean developers no longer struggle with it, and the changes may cause new (and worse) problems. I bet most language features enthusiastically discussed on LtU would not pass such scrutiny. I don't think this is inherent to the features. However, without such scrutiny and the ensuing iteration to assuage the fundamental usage problems, we're significantly and artificially limiting our impact.

As someone who experiments with PL features, I recognize the difficulty of doing such usability studies, but, from such a perspective, an otherwise inspiring conference like POPL can be disheartening if not embarrassing when you treat PL as a science. This is a problem we have as a community. I don't know what happened since the 1970s, but while we have raised the bar in terms of semantics, we seem to have lowered it in other regards. Wild and crazy ideas are fine, but they're just that until they're evaluated and refined, no matter how 'correct' they are.

### Abstract state machines?

abstract study of computational phenomena

Not sure what this would mean. Perhaps you mean automata? Algorithms?

Leslie Lamport wrote a note a little while ago in which he decried the emphasis on programming languages in computer science (possible blasphemy on this site, I know), and argued for more of a focus on "fundamental concepts". For Lamport, that seems to mean viewing all computation as an abstract state machine of some sort, expressed in terms of sets and logic rather than a specific programming language. From the abstract of his note on the topic:

For quite a while, Iâ€™ve been disturbed by the emphasis on language in computer science. ... Computer science should be about concepts, not languages. But how does one teach concepts without getting distracted by the language in which those concepts are expressed? My answer is to use the same language as every other branch of science and engineeringâ€”namely, mathematics. But how should that be done in practice? This note represents a small step towards an answer. It doesnâ€™t discuss how to teach computer science; it simply addresses the preliminary question of what is computation.
Not surprisingly, Lamport uses a notation that closely resembles his own TLA+. But the same ideas can presumbly be applied using Z, Gurevich's Abstract State Machine notation, or some other approach that allows state machines to be represented abstractly.

### Regress

If the abstract machine is described formally, does that not entail at least one formal language? ;-)

### Indeed

Yes :-)

I believe that Lamport's argument is partly that the formal language in question should just be "mathematics" (although by that he appears to mean "mathematics as expressed using TLA+"), and partly that the focus should be on teaching a general notion of operational semantics (i.e. state machines) that can be applied to many "real" languages, rather than focusing on applying a specific "real" language. Of course, it probably would be a good idea for students to also get some practice actually implementing their state machines, if for no other reason than to build an intuitive understanding of how the state machines are operating (but presumably also so that the students don't decide that all they're learning is a bunch of impractical abstract theory).

### So it is not about

So it is not about "languages" (a red herring if ever I saw one) but rather on the appropriate level of abstraction for specifying algorithms.

Now this reminds me of something...

Right! Programming language folks are the ones thinking about exactly this issue ;-)

### Sounds on topic to me...

Sounds on topic to me, Charles... (But then, I am perhaps not the typical member when it comes to philosophy). I am pretty sure, though, that I will end up rejecting your analogy to the linguistic turn in philosophy.

### Linguistic turn

My analogy: the linguistic turn in philosophy is essentially the story of how analytic philosophy came to be, and how it became dominant. A central thread in analytic philosophy is the explanation of the meaning of expressions in terms of reference; crucial figures are Frege, Tarski, and Davidson. And what that means is the explanation in terms of T-schema. The revolution in the semantics of programming in general in the mid 1960s to early 1970s can be understood as an attempt to carry out a similar project for programming languages, and the work of Scott-Strachey is the most rigorous and wholehearted attempt in this vein.

I think the analogy is hard to resist...

### Turn, turn, turn

I think the analogy is hard to resist...

I think it is a tribute to your clear presentation of this idea that, now that you've said it, it seems obvious. ;-)

To my mind, they differ in their outcomes though: the "linguistic turn" in computation uncovered deep truths about its subject (I think that computation is deeply linguistic in nature, whether that language used to describe it is mathematical notation, automata formalisms, or PLs).

I think the "linguistic turn" in philosophy is important, necessary and useful but failed to meet its ends entirely.

The difference is in large part because computation is a much more restricted domain of meaning than the more general notion of meaning that the analytic philosophers were after.

### I'll second that

I'd certainly like to hear more, Charles. (Here or in a new thread...)

### Don't forget the Greeks

Side remark, I guess I stated it before: I always thought data vs. algorithm, DB vs. application logic, OO vs. FP boils down to Parmenides/Plato vs Heraklitos. I.e.: "Everythings which is, is"/"Atoms" vs. "Everything moves" visions on the world.

Somehow large parts of the industry still seems divided into these camps: those who think about data, and those who think about algorithms.

### I will

I forgot about him, I just read some discussions of his work over time.

Funny down-to-earth banality derived from Wikipedia:

As in Heraclitus, a concrescence never reaches the unity of its final cause, hence Whitehead uses the term "presupposed actual occasions", which are "falsifications." An object therefore is identified with its concrescence; there is no other. The process of transforming "alien" entities into "data" for a new concrescence is termed a "feeling." Whitehead thus builds up statements that are scarcely less obscure, if at all, than those of Heraclitus: "... an actual occasion is a concrescence effected by a process of feelings."

Great, algorithms are feelings?

### His Nature and Life is short

His Nature and Life is short and quite clear. You can digest it in one sitting.

### Ironically Scott received

Ironically Scott received his Turing Award for his work about finite automata...

I guess the biggest hindrance for the purification of "computational thinking" had already been detected by Dijkstra and to some extent also by Wirth: the computer. Without computers at hand we are almost naturally bound to explore the territory through mathematical formalism, models, calculi, toy languages etc. With them everything becomes a heuristic that approximately works - Dijkstras nightmare.

My favorite example is statistical machine translation recently advocated by Peter Norvig and Google. If anything this represents the linguist un-turn. We are slowly leaving the 20th century.

### My favorite example is

My favorite example is statistical machine translation recently advocated by Peter Norvig and Google. If anything this represents the linguist un-turn. We are slowly leaving the 20th century.

Hear, hear! (I think... Or are you saying it like it's a good thing...?)

### Machine Translation

I'll admit I only know English, so my ability to judge Google translate is very limited, but it seems to work as well or better than other automatic translators.

Also, Google translate has the dubious distinction that you can pass English text through the system to another language and back, and the result is something very close to the original instead of barely intelligible gibberish. This seems like a good sign, though this smoke test probably isn't overly applicable to this particular algorithm, judging from translations of foreign-language texts to English.

Of course, I'm rather skeptical of the computer's ability to process natural language. I'll be mildly surprised if somebody comes up with translation software that works as well as even a marginally competent human translator. There may well be fundamental limitations here that we can't elucidate yet.

### Though the bad thing about mathematical formalisms

Though the bad thing about mathematical formalisms is that they so seldomly seem to capture the idea of behaviour right. In math stuff just is. I always found it bewildering that the foremost used model for computation still is the Turing machine, which to me, always seemed some model which just "fell out of the air" without any just claim as for why it should be a model of computation.

[I once had a discussion with someone that the 'Platonic atom' of CS is the 'bit', I now think I fervently disagree with that notion. The 'Platonic atom' of CS is not the 'bit' but the 'Î²Î®Î¼Î±/bema' or 'step'. Although, we never used those words then.]

### Hey! It's because it is

Hey! It's because it is similar to a bi-directional typewriter... (If you haven't read Turing's biography by Hodges you should).

(More seriously, we now realize that it is much easier to achieve computational universality that to define sub-Turing computational models).

### More seriously

It just "works". But I don't think a lot of people think about why it works. And if it "works" well.

### Not a lot of people... but

Not a lot of people... but many do. (Not that I am really sure what you have in mind when you say "works well").

### Works well

Because it shows the Time/Space consumption. I.e. the tape is a measure of space (bits), and the automaton has timed step like behaviour (I'll be pedantic: bema).

The question just is: Why that automaton? [Should SKI not be the default, for example.]

[One reason not to use a Turing machine is that it needs to step a lot into any of two directions to access/shift data, often adding log(n) or n where it needn't.]

### History

Turing created the first universal machine, so it is a natural choice.

[When I said first, I mean the first that is actually like a machine. Lambda calculus is much more abstract in comparation. Also, as neelk said in another post, the motivation for the proposed operations is very clear.]

### Because they are machines.

Because they are machines. As a technique oriented culture we are not interested in computations per se as if they were some platonic ideas created by God used to enjoy human beings who love to contemplate them. This might somehow touch our private sentiments and in particular those who adhere to the spirit of a medieval institution like the university but this not the great game anymore. With TMs we enter the state where mathematics becomes an applied science and engineers take over. Not applied mathematics i.e. pure reason that is applied to the dirty world but something that can just work algorithmically without being more solid than required i.e. just well tested. So the unviversal TM is an abstract model of computation appealing to engineers and it is just-good-enough for this purpose.

### Hardyhar...

Scientists are not interested in minimal models? Come on... Even engineers prefer the best models they can get.

[A Fourier transform has little to do with machines. Why would TMs be better excepted by engineers?]

[Oh, it's ironic. Is it? Obligatory emoticon: ;-)]

### I do not quite understand

I do not quite understand where your problem is?

It's not that computing science is Superstring Theory that performs the eternal drama of finding save foundations for morass of data and incompatible theories full of mathematical inconsistencies and workarounds. Whether or not someone uses TMs or Lambda Calculus as a foundational notation is a matter of preference rather than a do or die. Wolfram prefers universal cellular automata. I've little to complain about it. The "liberation" from the von Neumann style also isn't as revolutionary hot as it was in 1977.

### Ha!

It's not that computing science is Superstring Theory that performs the eternal drama of finding save foundations for morass of data and incompatible theories full of mathematical inconsistencies and workarounds.

Can't help it: I think you just gave a pretty good description of fundamental CS. ;-)

### I'm surprised that someone

I'm surprised that someone believes that the foundations of CS are not solid. It's as if a biochemist wants to change physics because it's hard to understand protein folding and DNA replication on the level of quantum mechanics. One shouldn't ignore the main issue of finding an adequate systemic level of understanding or a "semantics" of protein folding. It's just not that anyone can expect this by altering orbital models.

So I still don't know what you hope for?

### Solid at times

Well, people do cut corners, also in fundamental CS.

Examples: in a plethora of mathematical models we assume step-wise semantics where there is none. In reductions between computational models we forget that names need bit representations and lookups. In models, different assumptions are made for multiplication (is it O(n^2), some loglog(n), or O(1)), so different results often don't carry over as easily as often as authors in the field assume. Big mistakes are still made when giving axiomatic descriptions of theories. There are no real preferable or encompassing models for computation, logic, or distributed computations. We don't really know what a good programming language is, we might not even have arrived at the right computational model for AI (maybe it should be massively parallel), etc.

Yes, a lot of models are solid at the fundamental level. But when looking at all the articles produced, and the results therein, I believe that a claim that fundamental CS is a patchwork of theories with widely incompatible results, unjustifiable claims, and, yeah, a morass of fundamental trouble is not that far off.

Is the difference with String Theory that big?

I guess I am just hoping for some "final cause" for most fields, theories we know are minimal, unifying, but also workable. But they might not exist.

### More concrete

A story which didn't happen.

As stated, once I was looking for some computational model where 'time' and 'space' would converge. Bits are not it, I thought, since, though you can ascribe meaning to them, they are inherently meaningless. So I assumed TMs are not the final answer, found SKI to be preferable to TMs because a symbol in SKI has two qualities I thought are fundamental. I.e. it has 'state' when written down, it's representation, and it has behaviour/step-wise semantics as described by the rewrite rules.

Not so nice is that SKI is a 'textual' model, so I was wondering whether I could find something more 'concrete' where the symbols would either 'remain-in-place' or be able to 'move a step' and only refer to symbols left/right, maybe up/down. The symbols should also have some introspective quality. Kind-of like cellular automata. [With a difference that marbles are 'inserted' in series.]

I ended up playing something I can only describe as marble-games where 'left-turning' and 'right-turning' marbles interact but never really got it to work very well. [I know Life/Langton's ant, btw.]

Maybe a foolish attempt, but I had some fun with it.

[ Btw, I am not claiming a unifying theory should look like cellular automata, just claiming that 'we don't know what we don't know'. I am not that sure that, say around 2045, we will laugh at half of the theories used in the 20th century. ]

[ It also didn't work that well, I couldn't get 'time' and 'space' to collapse except for series of marbles which reduce to other series of marbles. Like converging LC terms. ] [ I wanted something in which some algorithms either take space, therefore, need less time, or take time, therefore need less spaces.]

[ Another way of looking at this. Cellular automata somehow imply some architecture where each cell has a state and an associated processor. Yes, emulatable by a TM but as a design radically different. If you really want to design programs for such an architecture, you need good models for that. There is no reason not to assume that in one or two centuries people will look back at our current processor designs and think of the concept of having one CPU which changes one memory-cell at a time as just plain foolish.]

### Interesting hypothesis. Care

Interesting hypothesis. Care to suggest how would you go about substantiating it? [I am not kidding]

### I'd ask media theory a la

I'd ask media theory a la McLuhan, Flusser, Kittler ... and sociology a la Marx, Weber, Luhmann... which made serious attempts to tell the history of the human mind not as one of ideas and pure reason but reflecting their historical, institutional and material conditions. Neither of those are particularly empiric though. If substantiating means "hard data" those recommendations are probably premature.

### I didn't mean the

I didn't mean the theoretical framework (though that's important of course), but the concrete details (hard or soft) you'd refer to.

### You can find enough evidence

You can find enough evidence that the industry had a major impact on many essential developments in our field and this is not restricted to IBM, Xerox and AT&T. The question is where and who are the driving forces? Which are the major programming languages taught at universities and where did they originate? Which are the major processor models and which are the favorite formalisms used by those who create the hardware?

The various prescriptions have become so powerful and diverse that even pop-cultural phenomena emerged that are related to programming languages and OSS. There is enough material to keep whole humanity research institutes busy ( which might be not that hard though because they are usually small and are still shrinking anyway ).

Regarding the question about the influence of TMs I'd rather ask why machine-distant notions of computations could have become popular? They were always available along with Turings own work but just recently "pure reason" could celebrate a little renaissance - at least in the wikiredditblogosphere.

### what are we stepping on?

Though the bad thing about mathematical formalisms is that they so seldomly seem to capture the idea of behaviour right. In math stuff just is.

But e.g. lambda calculus and similar formalisms go beyond that, with reduction steps.

I once had a discussion with someone that the 'Platonic atom' of CS is the 'bit', I now think I fervently disagree with that notion.

Bits seem useful for information theory, but for computer science we need abstractions: things that denote other things. That also allows us to abstract away from bits.

The 'Platonic atom' of CS is not the 'bit' but the 'Î²Î®Î¼Î±/bema' or 'step'.

Once you have abstractions, you need steps to reduce the abstractions to get an answer.

I agree about Turing machines - but I think they persisted because they were so vividly concrete, which matched the perception and capabilities of computers at the time. Consider that with e.g. denotational semantics, they went to a lot of trouble to provide a spatial/geometric interpretation, in terms of lattices. Turing machines were spatial from the start, and needed no such grounding.

### Or stepping off?

[To Kay and Anton]

The question, for me, just is/was: if space and time are the fundamental notions of computation, what then is 'the best,' in sense of Einstein's definition of mimimal, model to capture those notions?

I never felt TMs fit Einstein's criterion. Btw, I guess series of bits are also a good measure of information density which added to the popularity of TMs.

LC suffers somewhat from beta-reduction, substitution is a whole term step, it's another computational model than TM, for me. (Ok, one can do the environment trick explicitly.)

Cellular automata are widely distributed computations, which, again to me, imply a different computational model, even hint at a different processor design.

Nit-picking?

[Comment: they all are Turing complete models: TM,LC,SKI,Life. But you arrive at different Time/Space complexities with the different models.] [Ok, that is pending the reduction one uses to convert, and most will only be of by at most log(n) or n.]

### Jot

Guess I should refer to Jot.

### Daydreaming

Actually, for me the question at some point was whether a formalization exists with a uniform notation where, to some extend, you can make time and space converge. I.e. there is a time/space trade-off, something akin to e=mc^2, but then for CS.

### Nowadays, I spend my time

Nowadays, I spend my time thinking in terms of PRAM, BSP, etc., depending on what I'm trying to achieve. Lambda calculus, semantic domains, and TMs aren't really in the picture. In a more declarative / mechanized / statistical future, I might feel differently (but can't commit even then -- all models seem to be struggling, albeit to different extents). Either way, I probably won't be coding by the time that hits ;-)

To be fair, I'm assuming knowledge of a dynamic semantics that maps down into these ASM-like models.

Edit: this is only very true as far as my attempts to make things fast ;-) for simple problems, of course not -- i like semantic domains :) unfortunately, machines are still slow; even in supposedly 'simple' problems, going away from models that make space/time clear quickly leads to headaches. as stated by others, rewrite rules are not as intuitive as moving stuff around, and it's surprising to think that moving away from physical models would do otherwise. sometimes we get lucky (DSLs), but the general hairy case?

### Turing's paper is very clear

I always found it bewildering that the foremost used model for computation still is the Turing machine, which to me, always seemed some model which just "fell out of the air" without any just claim as for why it should be a model of computation.

You should read Turing's original paper, then. It's a model of clarity! At the time he wrote his paper on TMs, mathematicians and logicians had spent almost fifty years trying to figure out how what an "effective procedure" or "finite computation" meant. His paper was the first entirely satisfying account of what that was.

In the early part of nineteenth century, when mathematicians used the word "function", they meant some algebraic expression built out of things like +, -, × ÷, sine, cosine, exponentiation, and so on, perhaps defined piecewise over intervals. Basically, the idea was that you could interpret functions as rules telling you how to compute one number from another.

However, people kept generalizing the notion of function, and between the twin demands of analysis and set-theoretic formalization, eventually the concept of function had to be generalized to its modern form, which is to interpret a function from a set A to a set B, as a relation pairing each element of A with a single element of B. However, this allows obviously non-rule-like functions, especially since the post-Cantorian world allows the definition of enormously infinite sets.

But obviously, something has been lost in this generalization -- namely, we've given up the idea that a function must supply an effective method for producing Bs from As. Since this is obviously a valuable idea, mathematicians then spent a lot of time effort trying to formalize what an effective method might be. This was especially vital given the importance of finitist methods to both Hilbert's program and Brouwer's constructivism.

They came up with a lot of contenders! Skolem suggested using primitive recursive arithmetic definitions to formalize Hilbert's notion of finite method. Church advocated the lambda calculus. Goedel suggested the use of systems of guarded recursive equations. And those are just the systems of the most famous logicians; there were many more.

The reason that none of them took over is because while it was possible to see that many definitions could be expressed in each one, it wasn't clear that any intuitively effective method could be so expressed. What Turing did was to analyze the operations that human mathematicians performed while doing a calculation, and then give a formal model in which each thing that we do corresponds to exactly one of the operations of his machine.

This made the intuitive argument that he had gotten things right much more compelling, and that's why Goedel and Church and all those guys hailed TMs as such a triumph -- Turing had made it extremely clear exactly what was going in in the transition from informal to formal. This meant that you could now take any model of computation you like, chosen for whatever good mathematical properties it had, and then show its universality simply by showing its equivalence with TMs.

For example, I love lambda calculus because of its tight connections to intuitionistic mathematics, and I know I haven't lost anything because it's easy to prove that the lambda calculus is equivalent in power to TMs.

### Awesome!

Thanks very much for that!

### Much glossed over subject

Yes, the discovery of equivalence of these models and the connection Turing makes to how a real person (with limited memory, bounds on pages to flip between steps, etc.) computes something is much neglected in intro theory classes.

Martin Davis wrote a very accessible book on this subject: Engines of Logic.

### I always found it

I always found it bewildering that the foremost used model for computation still is the Turing machine, which to me, always seemed some model which just "fell out of the air" without any just claim as for why it should be a model of computation.

You should read Turing's original paper, then. It's a model of clarity!

I don't read a lot of "philosophy of math" texts like it seems some here do, but... I've always thought the best comparison of lambda calculus to turing machines was by algorithmic information complexity creator Gregory Chaitin. In particular, I'm fond of the speeches and essays in the book Exploring Randomness, where he compares Church, Turing, Godel and Cantor. Chaitin summarizes Turing's significance so smoothly that I barely knew what hit me once I finished reading.

### scott-strachey v. analytic philosophy

I think there might be something not quite right about how Charles is looking at the parallels between Scott-Strachey and and analytic philosophy.

The programs of analytic philosophy originated prior to Goedel and Turing's work on computability. Scott-Strachey comes afterwards.

The difference matters because the analytic philosophers were on a quest to find a kind of philosopher's stone - foundational systems that would objectively resolve all the hard problems. Scott and Strachey lived in a different state of awareness and sought no such thing.

The difference runs deep because Scott and Strachey are in some sense trying to work with, rather than around, limits of computability and limits of knowledge and discourse. Their program was in some sense the opposite of what the analytic philosophers tried to do. I'm looking, for example, at the preface of Milne and Strachey ("A theory of programming language semantics"). Mathematical semantics is motivated entirely by contingent, practical needs: to compare a programming language spec to an implementation; to compare two algorithms in some cases; to better inform the design of programming languages by making it awkward to write out (in a semantics) many kinds of common mistake in language design; that kind of thing. They weren't looking for a universal approach to the logic of computation: they were offering up some useful math for thinking about a bunch of "best practices" in certain engineering areas.

Here's the thing, though: I think that the Scott-Strachey approach is, indirectly, incidentally, and accidentally, the foundation of a good corrective to the programs of analytic philosophy.

After Goedel and Turing, analytic philosophy necessarily lost its footing. It had sought foundations which were rigorous, axiomatic, and complete - only to be absolutely refuted for having chosen such goals. It had *practiced* "partial solutions" - people expressing themselves in terms of (ideally) rigorous and axiomatic foundations regarded as "not yet necessarily complete". It learned that not only was "complete" unachievable but that there was no rigorous and axiomatic basis for choosing between competing, incompatible axiomatic foundations in many cases. So, what was left? The wind got knocked out of the sails of anything like a positive program from the movement. Analytic approaches became just another "style among styles", soldiering on as 20th century positivism in a lot of fields.

The inherent nihilism of the analytic / positivist movement lies in the fact that at the end of the day none of the practitioners could really explain why anyone should care. A complete axiomitization of truth (even in principle if not on paper) was the original reason anyone should care but that was gone: so aren't they just jawing about opinions in formal language?

Wittgenstein (post-Tractatus - the Philosophical Investigations) introduced to philosophy the concept of "language games" - an understanding of the meaning of language in operational terms - though his approach is purely intuitive, not formal.

Scott-Strachey give us (incidentally, by accident) an understanding of what, in principle, a rigorous mathematical theory of a specific language game might look like.

Foucault, in my understanding of him at least, is essentially of the same view as Wittgenstein on language games as the essence of meaning in speech acts: I see no other way to view his analysis of the relationship between power and discourse. In his view, discourse creates politically significant objects - e.g., the demographic category "teenager" - which in turn have operational significance during the construction of material institutions - e.g., the movie rating system and the enforcement of age restrictions at the box office. He points out that the "internal" discourse that governs the operation of something like the movie rating system has its own internal theories of the meaning - e.g., "we protect innocent children this way" - while, extensionally, those theories of meaning have little or nothing to do with how institutions of power evolve over the course of history. To have better insight into the evolution of such institutions we need to look at the discourse that operates and look not in the hermeneutic of self-description it offers up but in terms of its operational semantics in the nature of power exercised upon actual bodies.

The question then arises whether Foucault's sense of meaning is essential and insightful or is simply "an alternative theory" in the sense of yet-another "just so" story. At the very least, least fixed-point semantics of programming languages give us a very strong suggestion that Foucault's sense of meaning is not absurd on its face: he might be wrong about particular cases because of the necessarily non-rigorous guess-work he engages in BUT we have good reason to suspect that he is at least guessing about a meaning that is, in principle, rigorous and real - even if too complicated to measure with complete precision.

Wittgenstein of the Tractatus wanted to suppress the concerns of earlier and contemporary philosophers, at least as spoken out loud, for example, concern over the question of the existence of the soul. Any proposition about the soul, he argued, would necessarily refer to facts outside the world and consequently be simply meaningless. Foucault's sense of meaning offers an alternative point of view. Denotational semantics gives support to Foucault's general sense of the nature of meaning.

One way to see that Scott-Strachey make a nice counter-point and corrective to analytic philosophy is to imagine Wittgenstein and Foucault plucked out of the past and moved forward in time:

What if the-Wittgenstein-who-wanted-to-right-the-Tractatus had been less informed by Russel et al. and more informed by Goedel and Scott? And what would Foucault have made of that alternative universe's Tractatus?

-t

### analyitic phil

I think there's a lot of confusion about analytic philosophy in this post. The 'linguistic turn' that Charles refers to post-dates Whitehead and Russell, and analytic philosophy has certainly continued as a program after the death of both the axiomitization and positivist programs. It's hard to say what exactly Kripke (or Chalmers, or Parfit) has to worry about from incompleteness.

Also, statements like this: "least fixed-point semantics of programming languages give us a very strong suggestion that Foucault's sense of meaning is not absurd on its face" are more reminiscent of the Sokal hoax than anything anyone talks about in philosophy or in PL. Foucault is not talking about semantics in the formal sense, formal languages are not like natural languages, and the least fixed-point is not the same as a gradual process by which we construct the meaning of language.

Finally, there's nothing more 'mathematical' of Scott-Strachey (or any other model-theoretic approach) than there is in other ways of giving the semantics of a formal language (as Church does in his papers on the lambda calculus, for example).

### linguistic turn, etc.

"The 'linguistic turn' that Charles refers to post-dates Whitehead and Russell"

That doesn't significantly alter their "foundation-seeking" program, though: they still look(ed) for the stable point from which to move the universe with articulate rigor.

Here's a contrast: With the analytic folks, we never look at a particular case - some real situation - except as an application or examination of some "theory of everything". Later, the same tradition had to accept that there was no "theory of everything" but still maintained that perhaps there was a "theory of everything we can say" and so we get attempts at that like structuralism and post-modernism. In contrast, Foucault, Scott, and Strachey are all examples of "big topic" thinkers who explicitly limit themselves to particular real cases before them - there's no aspiration of "universality" in their theories. With the analytic types (pre and post the linguistic turn), particular cases are always reduced to some theory that is supposed (impossibly) be universal and complete. Foucault, Scott, and Strachey don't have that pretense.

Also, statements like this: "least fixed-point semantics of programming languages give us a very strong suggestion that Foucault's sense of meaning is not absurd on its face" are more reminiscent of the Sokal hoax than anything anyone talks about in philosophy or in PL.

Gee, what do you *really* think?

To unpack my statement a bit:

Foucault looks for meaning in discourse in terms of the space of computable implications of the assumed truths and in terms of the implications of those implications in the real environment of bodies. For example, "confessional" practices are treated as particularly interesting not in relation to theories of the soul or of various kinds of redemption but instead in relation to flows of information and their power structure relationship to a panoptic society. How can we explain, in principle, that such a connection can be drawn rigorously, at least in principle? Well, if we regard what really happens to real bodies as a kind of computation, and the discourse that significantly (not completely) "programs" that consequential computation - and if we're interested in, in that light, connecting the internal logic of that discourse to a tangible meaning - then least fixed point semantics offer confirmation we can do so and suggestion of how.

Of your linking me to Sokal all I can say without excessive digression here is that if you think he embarrassed the Social Text editors you need only look to the social consequences of the article to be corrected. Sokal's article was a "joke", sure, but not the joke people often profess to have taken to have been.

Finally, I called the "Scott-Strachey" approach "mathematical semantics" because that is the term used in Milne and Strachey. So I'm not sure what your objection there is - I was just *trying* to use a familiar name for the approach. Apparently pulling one out of the foundational literature was the wrong approach.

-t

### &c

"The 'linguistic turn' that Charles refers to post-dates Whitehead and Russell"

That doesn't significantly alter their "foundation-seeking" program, though: they still look(ed) for the stable point from which to move the universe with articulate rigor.

This is not true. If you look at modern analytic philosophy (say, since 1950), you won't find the 'foundation-seeking' that you're talking about.

Here's a contrast: With the analytic folks, we never look at a particular case - some real situation - except as an application or examination of some "theory of everything". Later, the same tradition had to accept that there was no "theory of everything" but still maintained that perhaps there was a "theory of everything we can say" and so we get attempts at that like structuralism and post-modernism.

I would be interested if you can find some examples of modern analytic philosophy to back up this argument. Here's a link to a prestigious journal of analytic philosophy: http://www.oxfordjournals.org/society/analysis/

Also, note that the term 'linguistic turn' means two very different things in different parts of the humanities. In philosophy, it refers to the idea that understanding language is central to (or the same as) understanding philosophical questions. In other humanities, it refers to something much more like what I think you're talking about, the centrality of 'discourse' to the way people represent and understand the world. Despite the seeming similarities, analytic philosophy generally takes a dim view of postmodernism and poststructuralism.

I don't really see what the similarity between Foucault on the one hand, and Scott and Strachey on the other hand, could possibly be about. What does it mean for a mathematician to "limit themselves to particular real cases before them"? In what sense is Foucault doing that?

As to the relationship between fixed points and discourse, you continue not to make any sense. (1) Can you find any reference to computability in Foucault? I doubt it. (2) Regarding "what happens to real bodies" as "computation" is a terrible category mistake. (3) "Discourse" is not a "program". (4) A least fixed-point (leaving semantics aside) requires several things: a function (what's the function here, and how could you make it precise?), a carrier set (would that be the set of possible discourses?), a partial order on the set (how could we specify that?).

You seem to be under the impression that by drawing analogies between mathematics and human language, some of the results of mathematics carry over to the statements about human language. But this is silly - the mathematics depends on the *precise* nature of the underlying definitions, precision which is not available in discussions about people and their language.

Finally, as to Sokal, I don't want to get into a discussion about who was proved to be what. I'll make just a few points: (1) my original statement analogized your claims to the ones Sokal makes in the paper, which I think we can all agree are nonsense. (2) The natural science community (at least the part that paid attention) certainly drew the conclusion Sokal desired. (3) Journals shouldn't publish papers that are unreviewable by their own editors without getting someone capable to review it, which is what happened to Social Text in this instance.

### it's sorta funny

It's sorta funny. In defiance of my claim that late 20th and now, I gather 21st century analytic philosophy is the tail spin of foundation seeking you pointed me to the Oxford journal "Analysis" and challenged me to find evidence there. Of course, that journal is behind a pay-wll so I could not directly take you up on that challenge. I did find a pre-print of the "speckled hen" article in the latest issue and, damn, there is no other way to read it but as the tail-spin of foundation seeking.

I'm sure we can't sort out our differences in blog comments so I give up on trying but, for the record, I don't think your corrections here are, um, correct.

You go on to ask some questions like "can you find reference in Foucault to computability" and, at that point, it's clear you aren't actually tracking me conversationally at all - so I don't have much to say other than: no and I'm not interested in the game you propose.

-t

### Not that I'm a postmodernist but

It seems to me, coming from a programming viewpoint, that what Thomas is saying here makes perfect sense. It's a cross-disciplinary, generalist position - but there's no reason why a person should be criticised for comparing two disciplines / bodies of theory and seeing similarities. In fact I believe we need far more generalists. Read some Christopher Alexander, for example, and you'll see how ideas from architecture have migrated to computer science (or at least to software engineering).

From what little I know about Foucault, once you take all the social-science language fluff away he's saying something that should be very familiar to computer programmers:

It's not what a system *says* that it does (the theory or documentation) that's important. It's what a system *really does* to real, observable, kickable things that's important/true/real.

When talking about the true effects of social systems or social 'programs' - information constructs such as ideas, political positions, myths, 'discourses' - you look at the actual effect of this 'software' on the state of the 'hardware' - which in sociology and politics, is *human bodies*, because that's what everything reduces down to in the human/social realm: interactions between and among human bodies. That's what architecture, ergonomics, cybernetics, and human/computer interaction studies are about.

When talking about the true effects of a computer program, you look at what happens to the bits or the registers or the latches of the machine state, because that's what everything reduces down to in the machine realm. You might *think* you have a correct formal description of a problem - but unless you can test and *observe* that that's actually the case in the real world, your formalised toy system might have led you very much astray.

And 'discourses' - socially constructed and shared ideas - can do the same thing. If we only look at, for example, what TV shows say about crime on subways, we don't know what the real subways are like. But we can look at that 'discourse' of 'subways in fiction' and try to work out what the *real implications of people holding that idea* are.

How is problematic, because of course in social science we can't easily freeze all variables except one. It's similar to testing a large and complicated real-time, networked software system which we didn't write and to which we don't have the source code, and which is constantly communicating and changing state. We can make models and theories by generalising our observations, but formal verification of those models is very hard because we can never have 100% complete knowledge of the state of the system and its dependencies. But we can at least guess.

A discourse then, at first glance, seems like it would be a function from one 'social state' to another. Or a system or collection of such functions, if you want to be a bit more precise.

In other words, an idea or set of ideas held by a group of people is something which changes those people's observable, physical behaviour.

There, is that so very hard to look at and say 'hmm, that looks like it maps fairly closely onto the realm of computing: state vectors, functions, arcs, transitions?'

Now: I'm not saying that Foucault is *exactly* saying that, since I haven't studied him in depth. And it's probably the case that he and the other postmodernist / poststructuralist / critical theory writers haven't really looked at the parallels between their studies of how human ideas change human physical systems, and how mathematical or software constructs change physically-embodied mathematical symbol processing systems. But the parallels seem pretty darn obvious to me.

Disclaimer: I'm an outsider in both realms here, so what I say may be completely wrong. But I think outside perspectives can be useful.

### Nothing wrong with postmodernism

I don't have much objection to what you're saying here. If you want to say that we can usefully model social systems with symbol pushing, that's great, it's called economics. If you want to say that generalism can lead to cross-disciplinary insights, a la Alexander, that's great too.

What Tom was saying, and what I strongly object to, is the idea that specific mathematical results tell us things beyond their domain. His example was Foucault being proven correct by a fix-point theorem. If you model Foucault's ideas about discourse in a formal way (something that I'm not sure he'd be a fan of), then maybe some theorem would tell you something about that model. But there's a big stretch between that and the actual ideas about human interaction.

Similarly, we might describe some kinds of human interaction as a recursive process, and that might gives us the kinds of insight that metaphor is very useful for. But we shouldn't think that formal results of recursion theory are applicable to that human interaction.

The belief that formal mathematical results give us deep insight into human nature is surprisingly widespread, and I think totally wrong. That's the point I'm trying to make.

### overinterpretation

I didn't claim that least fixed point semantics "proved Foucault".

-t

### yes

That's correct. You said: "least fixed-point semantics of programming languages give us a very strong suggestion that Foucault's sense of meaning is not absurd on its face" and "we have good reason to suspect that he is at least guessing about a meaning that is, in principle, rigorous and real" and "Denotational semantics gives support to Foucault's general sense of the nature of meaning".

### meaning

Right, I said those things. To elaborate briefly:

Consider the discourse in a corporate board room where certain demographic facts and figures are being discussed. Let's say, they are working on setting policy for how to measure the users of a web site. If we go into that room and ask people "Ok, but what does that mean?" we can imagine them answering in terms of various theories about statistics, empirical observations, past marketing research and so forth. If we ask "why is your discussion true" they'll explain in terms of those other theories. That's an ordinary sense of "meaning".

Foucault sometimes uses "truth" to refer to those meanings but he is using it as a term of art. He doesn't mean that the demographic discussion is in some transcendent or metaphysical sense "true" he means that in that room, in the mentality of the board members, that is what is treated as "truth". People will behave as if the statements are "true" (so, in that sense, they are).

Now suppose it is a few years later. Some change in mentality has occurred. Some disruption of formerly accepted, incrementally evolving scientific thought has shifted. In the new situation, if you ask people to look at a transcript of that old meeting and explain its meaning and what is true, they'll perhaps say something like "Actually, they were fooling themselves. It's partly not meaningful and partly false." Referring the new "truth", they'll give an account of what went wrong at that older meeting.

For Foucault, that term-of-art "truth" is still present at both meetings, regarded in their historic actuality. This is not to make some mystery out of the word "truth" or to deny objective reality or any such thing - it's just a term of art that points out an interesting aspect of how discourse functioned in the two meetings.

"Power" is another term of art in Foucault and, not wanting to oversimplify or over-interpret it too badly, it means roughly what you would expect. The larger social context of both board meetings is a context that makes the meetings a locus of control. The discourse is determining, in each case, how various subjugating forces will be managed. In this case, for example, the board is modulating the operation of machinery of surveillance and intervention: web site visitors will be watched from behind the firewall and, on the basis of what is seen, the environment of those users will be manipulated by other machinery controlled by the board. The meetings are a place where power flows through and is controlled. The discourse determines the rules.

At the meetings, of course people will cough, crack jokes, pursue personal agendas, and so forth. The outcome of each meeting is quite human, in that sense, but there is still something formalizable there.

The board's freedom to direct the surveillance and intervention machinery is not (usually) unconstrained. The board will prepare a report. They'll issue orders, containing rationales. In the larger social context, those orders and reports will be weighed against the formalizable logics of the relevant statistical and sociological theories. The board has choice about what specific orders it gives, but the orders must ultimately either conform to the logic of those demographic theories or else be understood as a departure from those theories. The formalizable logic of those theories defines a sharp, specific, boundary around what can (normally) be said and what can (normally) not. In that sense, at least if nothing normally not said comes out of the meeting, the discursive logic of the demographic theories controls the range of possible "settings" the machinery of surveillance and intervention might get put at.

That (permeable but normalizing) constraining of how power can be modulated is especially interesting if it contains an intrinsic bias. For example, it may be the case that unless they break with accepted "truth", any action the board takes must necessarily increase the level of surveillance and intervention.

Such a bias, when discovered by studying the logic of the discourse, is one of the main things that interested Foucault. You can't tell what the board will do before the meeting - but you can delineate what they will likely do. They're almost certain to increase surveillance and intervention. It is that *meaning* Foucault found in historically situated discursive logics.

That meaning is very, very different from the meanings the board members would describe in the two meetings. Foucault's "meaning" here is outside of the discursive logics being studied.

The question arises, then: is Foucault telling an absurd "just so" story to pseudo-explain why surveillance and intervention keep ramping up in some circumstances, or is there some objectivity to his sense of meaning?

Now we have all the pieces arrayed before us: we have an institution that controls machinery of power and subjugation. We have a location of central control - the board room. We have a social context in which the linkage between the board room and the configuration of the machinery is (partially, but significantly) constrained by "what can be said" within certain discursive logics of demographics. Those discursive logics are formalizable as formal languages and rules of inference (reduction rules).

So there it is: denotational semantics suggests that we can construct a model of the formalized discursive logics in play, regard them as denoting particular configurations of the machinery of power, and in principle have an objective theory of meaning that reflects what can (normally) be said in the board room. While we haven't proved that any particular meaning about specific situations is right - including those Foucault offered as examples - we have at least shown that his sense of the meaning of discourse is not absurd on its face.

Above, Sam, you wrote: "If you model Foucault's ideas about discourse in a formal way (something that I'm not sure he'd be a fan of), then maybe some theorem would tell you something about that model. But there's a big stretch between that and the actual ideas about human interaction."

There are two things to say, worth saying, that come to mind.

First, the formalizability of discursive logics and Foucault's assignment of meaning to them - as I described it here - was central to his program. I think he would be delighted, actually, but perhaps not think it was necessary to be so convoluted about it.

Second, you are right that nothing in such a formalization tells us much of much about human interaction. It doesn't need to. That's not the point. It tells us, roughly, that there is a real and objective meaning to "what the board can (normally) say" - it doesn't tell us what they will say and it provides no account of what happens when the board ignores the formal constraint and says something else anyway.

That second point was one of Foucault's central fascinations: occasions when there is a break, a disruption, a sudden shift in the hold dominant discursive logics have on institutions of power. His historic studies mainly focused on just those unexplained, sudden changes in the flow of power. He noted that in many historic situations a given set of discursive logics settles in and remains the dominant constraint for a long time - the board never says that which can not normally be said, so to speak. And he noticed that there are abrupt changes, dotting history, with interesting cases of such changes often leading to large changes in the social order. Studying specific examples, he found that contemporary or traditional accounts of why those shifts occurred when they did and where they did, and why the shift went in direction X instead of direction Y -- he found all of those accounts wanting. He began searching for a better understanding of those quite human shifts, looking not so much for a grand theory of them as for intellectual tools to bring them about. I think that to a significant extent he saw his life's work as a quest for such tools, with some successes and some failures and gaps. He died with the mystery of the potential spontaneity of social change very much in tact. I don't think he ever hoped to resolve the mystery but just to make tools that might or might not apply in various situations - ways of looking at things, ways of describing them. What I have pointed out here is that his descriptions are not, from a naive perspective, obviously meaningful but that if you look at their deep structure in relation to denotational semantics, you can argue that regardless of whether his specific descriptions are right or wrong, his unusual manner of description is plausible and meaningful.

In other words, denotational semantics helps us to see that Foucault's sense of meaning is not absurd on its face.

-t

### -

I appreciate the elaboration. This is basically what I took you to be saying before, and I still think it's very wrongheaded.

There's basically three points I want to make here. One, it's very interesting for someone who was so disparaging of a analytical project to believe such strong claims about the formalizibility of human behavior (including language). Two, can you provide some citation to Foucault's interest in "the formalizability of discursive logics". I would be interested in that. Three, I think this paragraph is incoherent, so I'd be interested in a clarification:

Second, you are right that nothing in such a formalization tells us much of much about human interaction. It doesn't need to. That's not the point. It tells us, roughly, that there is a real and objective meaning to "what the board can (normally) say" - it doesn't tell us what they will say and it provides no account of what happens when the board ignores the formal constraint and says something else anyway.

I don't see how the first and third sentences go together at all. The claim I'm making is the kind of formalization and symbol pushing we do in formal semantics can't capture human interaction (except in an 'all reducible to QM' sort of way). If that's true, which it seems like you're conceding, then it's not just true for a break in the social order, but for the normal operation of the social order too. I don't see why one would be more formalizable than the other.

### formalizability

(1 "formalization" v. "analytic project") The analysis of formal systems is a question about what sentences can be shown to be true, false, or undecidable in some formal system. Foundation seeking (like the way the speckled hen paper wants to talk about "seeing" and "consciousness") is the quixotic attempt to find formal systems for things not obviously reducible to such.

(2 Foucault cite): I'm lousy at giving cites but lucked out. Closest book at hand was "The Essential Works of Foucault vol. 3" ed. by Rabinow, titled "Power", first essay "Truth and Juridical Power", first three pages. Online here: Truth and Juridical Forms (Excerpt). Note the discussion of language games and, sure, there is some superficial irony that he draws from the analytic tradition but note he does not foundation-seek but quickly moves away from foundation seeking to trace historic specificities.

(3 "confusing paragraph"): As an example, the board can say "Select the color of the front page to maximize the number of clickthroughs" and the largest shareholders will normally accept that as an application of the latest theories about how to maximize revenue. On the other hand, the board might unusually (not normally) say "Run a random number generator to create the front page," and then they have some explaining to do if they want to keep their seats. So is there an objective "map", so to speak, of what the board can "normally" say about how to treat the home page? Well, yes - if you formalize the way that business performance is modeled, that user performance is modeled, that clickthroughs are modeled, and so forth, whatever the board says it will be "normal" if it makes some sense under those formalized theories. Is there an objective class of statements the board can "normally" make in that respect? If so, can we describe and begin to analyze it? Yes, essentially by using a denotational semantics in which the boards statement is syntax denoting configurations of the web site with certain mathematical properties given by the formalizations of the discourses around business model, models of users, etc.

-t

### Formal semantics or otherwise

Heaven help us when board meetings dictate website design. :)

### Sigh! You had me excited for a moment there....

With an url like "programming_languages_as_a_notation".

Yay! For a moment I thought, somebody has finally got it! Programming languages are merely (yet another) a notation, and you can choose whichever notation is most expressive and convenient for your current problem.

In fact, if you think of it that way... it frees from thinking about the mechanism (this does that to those bits) and puts the focus on where it should be. Getting safely to the Right Answer fastest and simplest manner and understanding how you got there.

My flavourite most example is Maxwell's Equations and differential forms notation.

Why? Well, literally half of Maxwell's equations become "Duh! Obvious!" and the rest become extremely simple AND generalize trivially to special relativistic forms.

In full expanded PDE notation it takes you a nearly a page to write them down.... and then change dramatically in the special relativistic case.

Maxwell's Equations