Speranza
This below is the first Google page for hits "Anton Marty Grice". Enjoy!
Meaning and Expression: Marty and Grice on Intentional
...
link.springer.com/.../10.1007%2F978-94-009-050... - Traduci questa
pagina
di F Liedtke - 1990 - Citato da 3 - Articoli correlate
Paul
Grice's essay 'Meaning' — one of the fundamental works for semantics — was
published in 1957. Almost fifty years before — in 1908 — Anton Marty's book
...
Mind, Meaning and Metaphysics. The Philosophy ... -
JStor
www.jstor.org/stable/2108070 - Traduci questa pagina
Anton Marty
(1847-1914) was professor of philosophy at the German University ... Frank
Liedtke, in "Meaning and Expression: Marty and Grice on Intentional.
Anton
Marty (Stanford Encyclopedia of
Philosophy)
plato.stanford.edu/entries/marty/
Simili
Traduci questa
pagina
19 dic 2008 - Anton Marty (October 18, 1847-October 1, 1914) was a
philosopher of ...... Liedtke, Frank, 1990, “Marty and Grice on Intentional
Semantics”, ...
Anton Marty -
Wikipedia
it.wikipedia.org/wiki/Anton_Marty
Copia
cache
Simili
Questa teoria anticipò molti elementi successivamente
introdotti nella filosofia analitica da Paul Grice, come la distinzione tra
significato naturale e non-naturale ...
[PDF]Meaning and Intentionality in
Anton Marty: Debates and
...
www.unige.ch/lettres/philo/.../Affiche%20Marty.p...
Copia
cache
Traduci questa pagina
12.00 – Anne Reboul (CNRS): Grice et Marty.
14.45 – Arkadiusz ... 16.45 – Savina Raynaud (Milan): Anton Marty's Heritage,
from Philosophy to Linguistics.
Mind, Meaning and Metaphysics - Barnes &
Noble
www.barnesandnoble.com/w/.../1102341510?...
Copia cache
Traduci
questa pagina
31 dic 2013 - ... Philosophy and Theory of Language of Anton
Marty by K. Mulligan. ... Meaning and Expression: Marty and Grice on Intentional
Semantics.
Themes from Brentano - Pagina 162 - Risultati da Google
Libri
https://books.google.com/books?isbn=9401209936 - Traduci questa
pagina
Denis Fisette, Guillaume Fréchette - 2013 - Philosophy
Anton
Marty, Karl Bühler: philosophes du langage, Basel: Schwabe. Liedtke, F. 1990.
'Meaning and Expression: Marty and Grice on Intentional Semantics' in
...
Meaning, Expression and
Thought
https://books.google.com/books?isbn=1139441159 - Traduci questa
pagina
Wayne A. Davis - 2002 - Philosophy
Alternative Analyses Grice
originated the program of defining speaker meaning in ... A similar view was
developed by Anton Marty (1908), a student ofBrentano.
History of
Linguistics, 1993: Papers from the Sixth
...
https://books.google.com/books?isbn=9027245657 - Traduci questa
pagina
Kurt R. Jankowsky - 1995 - Language Arts &
Disciplines
"Meaning and Expression: Marty and Grice on intentional
semantics". Mulligan 1990.9-50. Mulligan ... theory of language of Anton Marty.
Dordrecht: Kluwer ...
[DOC]Kevin
Mulligan
www.unizar.es/.../filologia.../Mulligan.K.doc
Copia
cache
Traduci questa pagina
The Philosophy and Theory of Language of Anton
Marty. Ed. Kevin ... Liedtke, Frank. "Meaning and Expression: Marty and Grice on
Intentional Semantics.
Friday, February 6, 2015
Grice as an intentionalist -- according to Suppes
Speranza
It perhaps wasn't clear that when I chose to title a recent post of mine, "Grice as intentionalist" I was echoing a brilliant passage by Suppes!
I was recently re-reading Suppes's contribution to the Griceian festschrift, P. G. R. I. C. E., "philosophical grounds of rationality: intentions, categories, ends".
Suppes focuses on a few points:
Paul Yu's point on Grice's relying on 'literal meaning' -- Yu is wrong.
John Biro's point about Grice being circular in his reasoning -- But Biro is wrong. Apparently Biro held some private correspondence with Suppes on that point, and they agreed to disagree!
Chomsky's exegesis of Grice as a behaviourist. Suppes relies on Chomsky's "John Locke Lectures" at Oxford, -- "Reflections on language" -- where Chomsky quotes profusely from the reprint of one of Grice's William James lectures in Searle, "Philosophy of Language" (Oxford readings in Philosophy, ed. by G. J. Warnock).
Suppes writes:
"It seems to me that Chomsky is badly off the mark"
The implicature of 'it seems to me' can here very appropriately be cancelled:
Chomsky IS badly off the mark -- never mind what it seems to Suppes!
Suppes goes on:
Chomsky is widely off the mark "in the passages" on Grice in "Reflections on language" on Grice being a behaviourist."
Suppes goes on:
"In terms of more reasoned and dispassionate analyses, it seems to me that one would ordinarily think of Grice not as a behaviourist" -- as Ryle was -- "but as an intentionalist" -- as the good ole phenomenologists.
I love the term 'intentionalist', and I think of Martin Anton Maurus Marty.
Martin Anton Maurus Marty (18 October 1847, in Schwyz – 1 October 1914, in Prague) was a Swiss philosopher. He specialized in philosophy of language, psychology and ontology. He was considered the successor of Franz Brentano.
More of his links with Grice later.
It perhaps wasn't clear that when I chose to title a recent post of mine, "Grice as intentionalist" I was echoing a brilliant passage by Suppes!
I was recently re-reading Suppes's contribution to the Griceian festschrift, P. G. R. I. C. E., "philosophical grounds of rationality: intentions, categories, ends".
Suppes focuses on a few points:
Paul Yu's point on Grice's relying on 'literal meaning' -- Yu is wrong.
John Biro's point about Grice being circular in his reasoning -- But Biro is wrong. Apparently Biro held some private correspondence with Suppes on that point, and they agreed to disagree!
Chomsky's exegesis of Grice as a behaviourist. Suppes relies on Chomsky's "John Locke Lectures" at Oxford, -- "Reflections on language" -- where Chomsky quotes profusely from the reprint of one of Grice's William James lectures in Searle, "Philosophy of Language" (Oxford readings in Philosophy, ed. by G. J. Warnock).
Suppes writes:
"It seems to me that Chomsky is badly off the mark"
The implicature of 'it seems to me' can here very appropriately be cancelled:
Chomsky IS badly off the mark -- never mind what it seems to Suppes!
Suppes goes on:
Chomsky is widely off the mark "in the passages" on Grice in "Reflections on language" on Grice being a behaviourist."
Suppes goes on:
"In terms of more reasoned and dispassionate analyses, it seems to me that one would ordinarily think of Grice not as a behaviourist" -- as Ryle was -- "but as an intentionalist" -- as the good ole phenomenologists.
I love the term 'intentionalist', and I think of Martin Anton Maurus Marty.
Martin Anton Maurus Marty (18 October 1847, in Schwyz – 1 October 1914, in Prague) was a Swiss philosopher. He specialized in philosophy of language, psychology and ontology. He was considered the successor of Franz Brentano.
More of his links with Grice later.
This Year of Grice; or Grice's Predictions
Speranza
Jones wrote in his Commentary to "Grice as intentionalist":
"One of these days AI researchers will stop making mistaken predictions of proximate success. possibly because of actual success."
Right. On the other hand, there's nothing wrong with Turing (who wasn't an AI researcher) making the optimist (if wrong) prediction. I love an optimist, as Vivian Ellis, did too!
The rule is old
So I've been told,
But still it's worth its weight in gold.
It pays you back a thousand fold,
So be enrolled
Upon the lists of optimists
And disregard the pessimists.
This life is short, so try to smile,
Each little while.
----- Vivian Ellis, "Spread a little happiness as you go by".
Jones wrote in his Commentary to "Grice as intentionalist":
"One of these days AI researchers will stop making mistaken predictions of proximate success. possibly because of actual success."
Right. On the other hand, there's nothing wrong with Turing (who wasn't an AI researcher) making the optimist (if wrong) prediction. I love an optimist, as Vivian Ellis, did too!
The rule is old
So I've been told,
But still it's worth its weight in gold.
It pays you back a thousand fold,
So be enrolled
Upon the lists of optimists
And disregard the pessimists.
This life is short, so try to smile,
Each little while.
----- Vivian Ellis, "Spread a little happiness as you go by".
Thursday, February 5, 2015
Grice as intentionalist: comments on Jones, "Behaviourist, dispositional, functionalist"
Speranza
In "Behaviourist, dispositional, functional", Jones writes: "JL and I had an exchange about the relationship between "behaviourist" and "dispositional" (I wanted to know the difference)."
And a fine difference too! (Etymologically, of course, 'fine', applies best to differences!).
(Perhaps 'nice' applies best to differences, too).
Jones goes on:
"I was Googling today and found an account by [the sometime Oxonian philosopher A. N.] Prior of the difference between behaviourism and functionalism which casts some light on this. I've lost the Prior site, but no matter, there is a more complete account under "functionalism" by Janet Levin at [the Stanford Encyclopedia of Philosophy]"
which is especially Griceian in spirit, since Grice couldn't look outside the window without thinking "Stanford" (He lived in Berkeley, overlooking the bay). Keyword: "Hands across the Bay".
Jones:
"I propose here a little discussion of how Turing, Grice, Ryle and Carnap may be placed relative to the varieties of behaviourism and functionalism described by Levin and each other (dispositional appears in the definition of behaviourism)."
Good. Levin should have access to "Disposition and Intention". That may make change, dispositionally, her mind on this -- and that!
Jones:
"At SEP under the heading "Antecedents of Functionalism" we find a section on the Turing test and a section on behaviourism. I discuss the latter first."
Good. I suppose Levin got that from Block. I was fascinated to see that Block discusses Grice and Functionalism and Turing in, alas, "PROBLEMS with Functionalism" -- or problems of functionalism, I forget. _His_ problems with functionalism, or is he being, philosophically, more generally? (and speaking on behalf of other people NEEDING to find a problem where there ain't?)
Jones goes on:
"Two varieties of behaviourism, empirical and logical or analytic, are distinguished, and are considered precursors to corresponding variants of functionalism (which seek to remedy defects in the behaviourist theories)."
Good. With Ryle the main exponent of 'analytic' bheaviourism, I trust. I guess he would rather see himself dead than a living 'empirical behaviourist' alla Watson!
Jones:
"Both of these behaviourisms seek to explain something in terms of behavioural dispositions (so, both the behaviourisms and the subsequent functionalisms are dispositional)."
Perhaps Grice would use a formalism here. Take "A" to represent "A" (open the umbrella).
The disposition to open the umbrella.
Or the disposition to laugh.
Or the disposition to smile.
--- I guess we have to be specific. Only a few items counts as good follow-ups for clauses reporting 'dispositions'.
----
"2 + 2" for example, does not have a disposition to be "4".
Neither does a bachelor a disposition to be an unmarried male!
-----
Nor Spring a disposition to follow Winter!
Jones goes on:
"The empirical behaviourist explains behaviour in that way, the logical behaviourist explains the meanings of mental concepts in that way (Malcolm, Ryle and perhaps the later Wittgenstein are mentioned)."
As they should!
I am slightly saddened that Ryle chose "The concept of mind" as the title of his book. He should have called it: "The ghost without the machine", or something.
----- But he was provocative enough to have Chomsky writing "Cartesian linguistics" and bringing the anti-behaviouristic movement back to the forum (cf. Chomsky's review of Skinner?)
Jones goes on:
"The principal difference between behaviourism and functionalism is that the former deny the reality of mental states and seek explanations of behaviour or language which are independent of mental states or concepts, whereas the latter insist on mental states and offer explanations of mental states or concepts which may involve other mental states or concepts."
Indeed. Aristotle was, surprisingly, a functionalist. But of course, the way 'function' is used by Aristotelians differs from this more 'mathematical' idea of 'function', which is what functionalists use when they say that psychological attitude
psi
(in symbols, Pap ---- Agent A has psychological attitude P towards proposition p)
co-relates to some perceptual INPUT (which need not be reported in psychologistic terms) and behavioural output ('open the umbrella') (which again need not be reported in psychologistic terms).
----
Jones writes:
"It sounds as if there is a metaphysical aspect here, which relates to Ryle's desire to refute Cartesian dualism, but there are more concrete differences as well."
Indeed, and I'm glad I mentioned Chomsky's "Cartesian linguistics" because the standard mainstream Anglo-American tradition that Chomsky is criticizing is usually associated with Empiricism and Behaviourism, and, who knows, some sort of Monistic Materialism.
(But functionalists need not be monists).
----
Jones goes on:
"The functionalist allows himself to talk about mental states when giving an account of mental concepts, he does not have to give an account exclusively in terms of behaviours."
This is something that somewhat irritated Grice, when commenting on Witters. Because Witters is saying that if we say something like,
"He raised his arm against me."
WHILE a purely physical interpretation may be possible, it seems that the vocabulary used to describe behaviour is psychologically-theory-laden, as Hanson would put it.
Jones goes on:
"Functionalism comes in three varieties according to its origins. Different varieties come from early AI research (and therefore connect with Turing), and from the empirical (or "psycho-") and logical behaviourisms (the latter connecting with Ryle, the former being an empirical theory rather than a philosophical one or a philosophical theory about empirical scientific theories of mind)."
Good. Of course, Grice concentrates on Ryle in his "Method in Philosophical Psychology". I guess that as an Oxonian philosopher Grice was VERY TIRED of having to deal with Ryle's book as the opus magnum of post-war Oxford philosophy!
----
Jones goes on
"The description of "machine state functionalism" given by Levin is I hope, not quite correct (it would otherwise reflect badly on Putnam), because she seems not to understand the difference between a finite-state automaton and a Turing machine (the difference is the tape, which is a big difference)."
Good. I think Grice knew Putnam well. I love a phrase by Grice on Putnam. I guess they met when Grice first went to Harvard, although I would NOT be surprised if Putnam had had a scholarship at Oxford (it seems all American philosophers then had!). Grice writes that he used to be too formal, until, "Putnam (of all people) told me I was." I just love the implicature of "of all people".
I cannot use "of all people" without triggering the wrong implicature. I guess Grice can be literal, and he means, that, out of the set of all people, Putnam told Grice that he was _too_ formal, implicating there is something wrong about 'too'. There shouldn't. (I like my coffee too sweet, for example).
Putnam was possible formal enough, and that is where Grice's joke lies. Cfr. Putnam on H20 and XYZ.
Jones:
"If we recast her definition appropriately then Putnam's account of this kind of functionalism asserts that any creature with a mind "can be regarded as" (this seems very weak) a Turing machine and that its mental states are then to be identified with the states of the Turing machine (and that would have to be the state of the automaton and the content and position its tape, though Levin talks only of the state of the automaton)."
Excellent point.
It may all relate to the KEYWORD: multiple physical realisability, if I may use a techno-kryptical expression.
I.e. the identification (or individuation, as I prefer -- cfr. Grice's ontological marxism) of a psychological state need to be made with the STATE of the automaton AND THE CONTENT AND POSITION OF THE TAPE!
Jones:
"I quote Levin for the nub of her description of the other two kinds of functionalism."
Good.
"What is distinctive about psycho-functionalism is its claim that mental states and processes are just those entities, with just those properties, postulated by the best scientific explanation of human behavior."
I like her distinction (or difference) between a 'state' and a process. Or an event, as I may prefer. Thus,
I think that Grice is an Englishman.
I think that all Englishmen are brave.
----
Therefore, I think that Grice is brave.
Here we seem to have THREE states (three beliefs) but also one event or process. MY believing that Grice is an Englishman AND that all Englishmen are brave YIELDS or causes my belief that Grice is brave.
----
Jones goes on to quote from Levin:
"the goal of analytic functionalism is to provide “topic-neutral” translations, or analyses, of our ordinary mental state terms or concepts".
I think the vocabulary is Broadian?
Jones:
"So how do our four protagonists relate to these various kinds of behaviourism and functionalism This is my present impression. Turing so far as I can see from "Computing Machinery and Intelligence" does not fit well into any of these schemes."
If Hodges is right (and he makes the point quite a few times) that Turing was no philosopher, then Turing would NOT care! The problem is that he possibly did not see as a psychologist either (But then why submit an essay to "Mind"?). He saw himself as a mathematician, and mathematicians need not commit to any of the varieties defined (rather arbitrarily) by Levin.
Jones:
"First of all, [Turing] is very clear that his test does not test for thinking, and he explicitly disavows any opinion about whether machines can think. I think the manner of his dismissal might be thought to implicate a similar attitude to other mental concepts. Here is a salient quote: "It will simplify matters for the reader if I explain first my own beliefs in the matter. Consider first the more accurate form of the question. I believe that in about fifty years' time it will be possible, to programme computers, with a storage capacity of about 109, to make them play the imitation game so well that an average interrogator will not have more than 70 per cent chance of making the right identification after five minutes of questioning. The original question, "Can machines think?" I believe to be too meaningless to deserve discussion." He does not appear to be interested in analysis of the meaning of mental concepts, and therefore is neither an analytic behaviourist nor an analytic functionalist.
Furthermore, the above quote I believe gives the central purpose of his paper, which is to make a claim about what computers will be able to achieve at some point in the future. He not only lacks interest in the meaning of mental concepts (beyond what is unavoidable is describing his thesis), but also does not appear to be interested in scientific theories about the mind."
Excellent point. The blame here is possibly SHERBORNE, his alma mater?
----- INTERLUDE ON SHERBORNE -- (Grice went to Clifton, and that's why he became a classicist, and Renaissance-interest person gaining a scholarship to Oxford -- On the other hand,
Sherborne's s origins date back to the eighth century, when a tradition of education in Sherborne was begun by St Aldhelm.
According to legend, Alfred the Great was one of the school's early pupils.
The school was then linked with Sherborne Abbey, formerly a Benedictine house. The earliest known Master was Thomas Copeland in 1437. After the Dissolution of the Monasteries, Edward VI re-founded the school in 1550 as King Edward's School, a free grammar school for local boys. The present-day school stands on land which once belonged to the abbey's monastery. The Library, Chapel, and Headmaster's rooms, which adjoin the Abbey Church, are modifications of its original monastic buildings.
The present school's earlier lives take us back four hundred, perhaps a thousand years."
"In the Beckett Room below the library there survives Anglo-Saxon masonry, a reminder that the school occupies all that remains of the site of Sherborne Abbey (AD 705, remodelled as a Benedictine abbey in 998). The Headmaster and the senior staff now have their offices, appropriately enough, in the Abbot's house, rather grandly refashioned, like the Abbey itself, in the 15th century; the library was, perhaps, the Abbot's "Guest Hall" (13th–15th century); the Chapel occupies another monastic refectory (12th–15th century, but much rebuilt and extended in the 19th century). Go just beyond the Headmaster’s block and face the Abbey and you can see quite clearly on the walls to your right the outlines of the monastic cloister with its curious first floor Abbot’s Chapel; the conduit, where the monks wash, was removed by the Victorians and rebuilt outside Bow House.
In 2005, Sherborne School was one of 50 of the country's leading independent schools that were found guilty of running an illegal price-fixing cartel, which had allowed them to drive up fees for thousands of parents. Each school was required to pay a nominal penalty of £10,000. All schools involved in the scandal agreed to make ex-gratia payments, totalling £3 million, into a trust. The trust was designed to benefit pupils who attended the schools during the period in respect of which fee information was shared. However, Jean Scott, the head of the Independent Schools Council, said that independent schools had always been exempt from anti-cartel rules applied to business, were following a long-established procedure in sharing the information with each other, and were unaware of the change to the law (on which they had not been consulted). She wrote to John Vickers, the OFT director-general, saying, "They are not a group of businessmen meeting behind closed doors to fix the price of their products to the disadvantage of the consumer. They are schools that have quite openly continued to follow a long-established practice because they were unaware that the law had changed."
---- END OF INTERLUDE about Sherborne. My point is that perhaps while at Sherborne, Turing was motivated by the staff ONLY to concentrate on mathematics, hence his lack of interest in philosophy, the classics, or science! After all, it is an independent school. Meaning, 'independent' from the rest of the world?
----
Jones:
"This I think excludes [Turing] from being considered an empirical behaviourist or functionalist, at least as far as we can see from this paper (the paper does not exclude this, though we might think his assertion that the "Can Machines Think?" is meaningless does exclude him from being an analytic behaviourist or functionalist)."
Indeed. But then, of course, Ryle perhaps did enjoy that some of the questions that he thought meaningful, "can machines think?", say, turned out to be, according to Turing, a 'systematically misleading' one!
Jones:
"Turing is closest to a "Machine state functionalist", not surprisingly since they were probably influenced by his work. But does he fit the description? Does he think anything with a mind "can be regarded as" a Turing machine? Possibly. But this is not, on my reading, the thesis which his paper presents. I believe he is asserting functional identity between minds and Turing machines (to each mind there is a corresponding Turing machine with which it is functionally identical), though he does not say that explicitly. But "can be regarded as" I still think, though vague, a little too strong."
Good points. Hodges, for that matter, teaches TURING at Wadham, and Oxford is of course strong in KEYWORD: Philosophy of Mind, so I would not be surprised that, if we search within the Oxford Sub-Faculty of Philosophy, people with interest in mathematics, logic, and philosophy of mind, we find a neo-Turingian -- or two!
----
Jones:
"Let us now consider Grice, which I am ill qualified to do, but perhaps these remarks will provoke a better informed response from Speranza."
I can all-ways talk!
Jones:
"Grice seems to me certainly to be an analyst and to be interested in the meanings of mental concepts.
I doubt that he is any kind of behaviourist, but it seems to me that he might well be an analytic functionalist."
So far so good. He is no behaviourist, I would think, because Grice took generations very seriously, and Ryle was born in 1900, while Grice was born in 1913 -- different generation, thus, different philosophies. What's the good of philosophy if we are not going to have a HISTORY OF PHILOSOPHY? So, just to be different, Grice would NOT have liked to a be associated with Ryle, at all! (Oscar Wood did -- and other Oxonian philosophers did).
I would think Grice was a functionalist in that the basis for "Method in philosophical psychology" is said to be D. K. Lewis, and Lewis WAS a functionalist!
Jones:
"In relation to Turing, my impression is that there is little contact, neither agreement nor disagreement. Insofar as Grice is interested in automata, I would imagine this to be concerned with the insights which might be gleaned from them into the nature of language or other philosophical problems. Would he have any interest in predictions about what computers will be able to do at some point in the future?"
Don't think so. His wife said that Grice STRONGLY disliked computers for mainly two reasons:
Everytime he wrote 'sticky wicket', the spelling checking device in his computer noted that there was something wrong there.
The second reason is that his computer did not recognize "pirot" (and wanted it to be replaced, alla Locke, by parrot).
Grice had a beautiful handwriting. Is there an implicature there? And he disliked word processors, never mind computers!
-----
Also he possibly would have thought that Turing was overrated. There he was, Turing was, playing almost something like chess and crosswords -- I have to find this genial paragraph in "The imitation game" -- while Grice, qua Captain of the Royal Navy -- was offering the ultimate sacrifice in the mid-Atlantic theatre of operations!
(He was soon transferred to the Admiralty, though).
Jones:
"Ryle I should perhaps have mentioned before Grice, because he preceded Grice and behaviourism preceded functionalism we may think of Ryle (as he is cited by Levin) as being some kind of behaviourist."
Yes. Only he would not use the Americanism 'behaviour'. One tends to associate 'behaviour' with Watson, and Skinner -- a VERY AMERICAN thing, and let's recall that Ryle is famous in Oxford for avoiding the "American" influence in the city of the dreaming spires. They were reading Johnson, and Price and Cook Wilson, and all the obscure British authors -- but few American philosophers.
Perhaps there is a history of philosophical American behaviourism that connects with PRAGMATISM which seems to have been popular at Oxford for some time. I recall that when Lewis Carroll wrote "The Hunting of the Snark", it was parodied in a comical issue of "Mind" (called "Mind!") by a pragmatist philosopher of two.
William James, who was almost a behaviourist (or is he more of an introspectionalist?) was perhaps pretty influential too in Oxford. And let us not forget that when Grice went to the USA it was to give the bi-annual lecture in memory of William James co-ordinated by the Department of Philosophy and the Department of Psychology.
Let us not forget, either, that Grice lectured at Oxford on PEIRCE, whose theory of symbols, indexes, and icons (that Grice disliked) gave Grice impetus to create his theory of meaning as intention.
John Holloway is an interesting figure to consider -- Oxford educated, comes up with a book on "Language and Intelligence" that has the merit of having the name of "H. P. Grice" mentioned when H. L. A. Hart reviewed it for "The Philosophical Quarterly".
We should not forget, either, that the ONLY PHILOSOPHER that Grice quotes in "Meaning" is C. L. Stevenson (his Yale University Press book on language and ethics), and most of Stevenson's examples are BEHAVIOURISTIC in nature. In fact, D. E. Cooper and other historians of pragmatics (such as S. Levinson, in "Pragmatics", Cambridge textbooks in linguistics) traces the history of Griceian pragmatics to behaviourism, pragmatism, Peirce and Morris -- Carnap has something to do with these authors, too).
----
Jones: "Because of [Ryle's] anti-dualistic zeal and his belief that some of our language (if perhaps only at the meta-linguistic level) is tainted by dualism, it is hard to see his position as being purely analytic. He attributes category errors to certain kinds of ordinary discourse about mental concepts.
It seems to me that Ryle is engaged (in his own terms) in both descriptive and revisionary metaphysics, in analysing the metaphysical content and pathologies of language as it is, and in undertaking a profylactic metaphysical synthesis."
I loved that!
God knows what he was attempting with his "Concept of Mind". At that time, "Mind", which he edited, was still subtitled, "A review of psychology and philosophy", I think, and I would not be surprised if some of his Ryle's friends WERE psychologists, and even behaviourists (George?)
Jones:
"[Ryle's] descriptive metaphysics reveals pathologies (category errors particularly) which his revisionary metaphysics seeks to repair. What makes him seem a behaviourist is that his metaphysics is monistic, materialistic. Perhaps this is enough to call him an analytic behaviourist, but I am inclined to think that to crude a characterisation."
Yes, and perhaps too American to Ryle's taste. Note that after "Concept of Mind" he have lecture after lecture on "THINKING". Professionally, he was the official professor at Oxford of "Metaphysical Philosophy", to be succeeded by Strawson. So I guess that Ryle's favourite motto, from "Punch" was:
-- What is the matter?
-- Never mind!
---
Jones:
"Between Ryle and Turing I see no connection, their ideas seem logically independent, neither supporting nor confuting each other, though possibly mutually sympathetic in a weaker sense."
Yes. We've seen that Hodges seeks a link here, in that Ryle's Concept of Mind came out in 1949, and Turing's essay was published in "Mind", edited by Ryle, in 1950. But then, I don't think Turing was ever invited (being a Cambridge person) to educate Oxonians on this -- or that.
----
Jones:
"What of Ryle and Grice?"
---- The obituary by G. E. L. Owens of Ryle in "Aristotelian Society" is a good one. He says that Ryle belonged to this group that had Mabbott (fellow at St. John's, with Grice) and a few others. But this group never inter-acted with Austin's Play Group (we are talking post-war Oxford) to which Grice belonged ("the class of philosophers who have no other class"). Owens goes on to say that when Austin died, it was Grice who led this "Play Group" -- Ryle was still active then. Recall that Grice left Oxford for good in 1967 (although he would return for his Locke Lectures and was surprised at how rude Oxonians philosophes could be -- one, he met on High Street -- "I haven't seen you in a while. You've been away?" "Of course they knew", Mrs. Grice regrets).
Rumour has it that Grice left Oxford because when Ryle retired as Waynflete professor of philosophy, the chair was given to Grice's pupil, Strawson, rather than to Grice himself. But this seems nonsense. Grice came to LOVE Berkeley where he was given full professor credentials from the beginning and he soon was leading his own little group there -- Grice's "at homes", attended by Searle, Davidson, Barry Stroud, George Myro, Judith Baker, and almost EVERY PHILOSOPHER and graduate student on Moses Hall!
Jones:
"Of our four protagonists here, these two are probably the closest to each other." Physically, too. So English! I'm sure in their manners, they were very much alike. Public school background and all that. Only Grice grew out of that background and never allowed his son or his daughter to attend a public school!
Jones:
"Insofar as Ryle is engaged in metaphysics, this would be of interest to Grice, though perhaps only the descriptive rather than the revisionary metaphysics."
Indeed.
Ryle was hardly systematic, though. While Grice was the systematic philosopher par excellence. And the older he got he more systematic he became. On the other hand, one reads Ryle's collection of essays, and one doesn't know what he is trying to achieve! (I always find him entertaining, though, and find his "Fido"-Fido theory of meaning a delight to refute!).
Jones:
"Grice's ontological pragmatism" or Marxism, as I prefer, "would I imagine leave him poorly motivated to enter into a crusade against Cartesian dualism."
Indeed. I was fascinated, when I got my copy of WoW (Way of Words) to find that Grice cared to include a historical essay he had written, back in the day, on DESCARTES!
Grice is into criticizing Descartes's rather casual difference between
"It is certain".
and
"I am certain".
Certainly, Grice saw a world of a difference between what he calls 'objective certainty' ("It is certain that it is raining, hence Smith is dispositionally inclined to open his umbrella") and 'subjective certainty' ("Smith is certain that it will rain; of course, this is quite different from saying that he KNOWS that it will rain").
Subjective certainty had been posed by Ayer as a criterion for empirical knowledge, and Grice knew better than that! ("I was certain that p, but it turned out that p was false" makes a lot of sense; whereas, "I knew that p, but then it turned out that p was false" triggers a contradictory implicature!).
Jones:
"Functionalism is however very accommodating, it does not seem to exclude much, and so Grice might well be an analytic functionalist, the distinction between him and Ryle similar to that between an analytic functionalist and an analytic behaviourist."
Problem with Grice's "Method in philosophical psychology" is that when one was thinking he would get into Turing and all that, he starts discussing Aristotle's idea of a 'soul'!
Grice thinks that 'soul' can only be analysed 'gradually'. He notes that Aristotle says that there are a few concepts (not just 'soul') that require this 'gradual' analysis. The other is 'number'.
So, he dedicates the central part of "Method in philosophical psychology: from the banal to the bizarre", to see how we can create creatures (if you allow me the redundancy -- Grice calls them pirots -- and the science of pirots: pirotology) which more and more complex psychological abilities.
He is interested in embedding connectives within psychological states.
As if I were to say:
"If Grice thinks that all Englishmen are brave AND Grice thinks that he is an Englishman; Grice thinks that he is brave. And this is analytic".
This is still different from:
"Grice thinks that if all Englishmen are brave, and that he is an Englishman, he is brave. And he thinks that this is analytic".
I am thinking of the analytic conditional associated with a piece of valid deductive reasoning. And possibly failing!
Let us not forget that Grice's third book, "Aspects of reason", is ALL ABOUT psychology, and how psychological operators can embed complex logical expressions.
Jones: "I now come to Carnap, the scientifically oriented scourge of metaphysics. The special features which Carnap brought in his anti-metaphysical fervour are of interest here. Before Carnap we would expect a positivist to be also a phenomenalist, and therefore to have no truck with Cartesian dualism and to be close to analytical and psychological behaviourism."
Good you bring PHENOMENALISM in!
Jones goes on: "Carnap's anti-metaphysics is novel (for a positivist) in being ontologically liberal and pragmatic rather than nominalistic."
Indeed. His distinction between internal and external questions may relate here.
Jones:
"This is reflected in his linguistic pluralism, and so, though he worked primarily with ontologies in which there were no mental entities (phenomenal, physical, and theoretical languages), he would not have ruled them out on principle (that would violate his principle of tolerance)."
Indeed. And it would not be difficult to trace him to tendencies found in American pragmatism, alla Morris, and other philosophers who were into 'operational' approaches to 'mentalistic' talk.
Jones:
"In consequence Carnap could not be a doctrinaire behaviourist, but would admit a behaviouristic scientific theory if it could by empirically confirmed."
Indeed. As opposed to Popper who would rather endose any FALSIFIED theory anyday!
Grice spends some time on issues of falsification and confirmation of theories in "Method" and goes on to quote a few 'psychological laws' from the literature, as he calls them. He is especially interested in finding them EMPTY!
Qua functionalist, Grice is allowing for psychological predicates to be introduced (via Ramsified naming and Ramsified describing) as theoretical terms, to be correlated with perceptual input and behavioural input ("No need of psychological concepts without behaviour which such concepts are called on to explain" -- his rewrite of Witters's dictum).
Jones:
"[Carnap] was concerned with scientific method, and I think it plausible that he would have been some kind of empirical or psycho- functionalist. Carnap's conception of philosophy was as a kind of analysis, but like Turing, he lacked interest in the details of natural languages, for much the same reasons. He advocated the use of formal notations and methods in philosophy and science, and explained the relationship between formalised concepts and those of natural languages as "explication", a relationship too weak perhaps to allow that the formal theories provided analyses of the natural concepts."
I like that. We have Carnap's explications and Grice's explicatures.
And I'm reminded of Byron who referring to an exegesis of a literary critic of a specially obscure poem, he wrote, "His explication is fine; but I fear we may need an explication of his explication." (I owe the quote to J. L. Borges, who gave the Eliot Lectures at Harvard while Grice was delivering the William James lectures).
Joness:
"Because of [Carnap's] desire to formalise and his scientific orientation it seems to me that Carnap is closer to Turing than to Ryle or Grice [...]"
and perhaps associated to the movement, so popular in America for a time, of a 'unified science'...
Jones: "[A]nd I see no conflict between the views of Carnap and Turing. Carnap's relationship to Ryle and Grice is more difficult."
Indeed, especially in view of a sort of generalized anti-scientism prominent in post-war Oxford. Grice kept lecturing on the 'devil of scientism' in his "Method in philosophical psychology", but he must have found that his audience had changed! (Perhaps Haugeland, Dreyfus, and Searle, found a strong sympathy on these issues, though).
Jones:
"As a formalist [Carnap] lacked interest in the minutiae of natural languages, as a positivist one would expect him to be antagonistic to the metaphysical aspects of Ryle's thesis (nominalism is metaphysics for Carnap). What is the point of this long ramble?"
"Should rambles have a point?" This is a favourite question in one of my favourite books.
Edward Step.
Step E. (1930) Nature Rambles: an Introduction to Country-lore, (4 volumes) Frederick Warne & Co. Ltd., London & NY: 256 pp.
Jones concludes:
"Well, one thing which I think important is a point about varieties of analysis."
Or "Annals of Anaysis", as I prefer -- Travis's title for his LONG review of Grice's WoW -- Way of Words -- in "Philosophical Review"!
Jones:
"Analytic philosophers seem often exclusively concerned with the analysis of ordinary language, and may too readily assume that what other philosophers (or even non-philosophical analysts) are doing is the analysis of language."
Or worse, English!
I am often amused by the fact that Grice found Latin and Greek superior to English. In "Aspects of Reason" he is discussing psychological predicates and the clauses by which they are followed, and find that Greek and Latin (that he had learned at Clifton) allow for nuances that English doesn't. Example: the imperative mode (never mood!) -- the optative mode, the so-called 'subjunctive' mood. Why are they becoming archaic in English? True, they ARE archaic in the archaic Greek and Latin he learned at Clifton too!
(Grice was amused that of all things, this was the minutiae that Gellner and Bergmann cared to choose when criticisng the "Oxford" type of analysis -- "futilitarianism", Bergmann called it -- a sensitivity for English usage found only, Gellner and Grice agree, on those educated at public school and later one of what Grice (and many others) call the 'stone-wall' Oxbridge, never redbrick! Grice is amused by this because he knew Gellner was oversimplifying: of course you don't have to be a public school Oxbridge type to delight in this or that linguistic mannerism!)
Jones: "Turing and Carnap in different ways offer examples of work which may be misconstrued as concerned with the analysis of ordinary language. Turing may be misconstrued as giving a test for or an analysis of the meaning of the concepts of "thought" or of "intelligence" when his purpose was simply to argue that humans had no intellectual capacities which could not be realised in a machines"
- and he proved that! (I love that episode when he breaks his engagement with Ms. Clarke, played by Keira Knightley -- I should find her genial riposte -- or is it retort? -- in the screenplay)
Jones:
"Carnap can be construed as primarily concerned with the explication of terms in ordinary language, and it is the central thrust of Carus's book on Carnap and 20th Century thought that the notion of explication is the centrepiece of Carnap's philosophy."
As perhaps Grice's explicature ain't!
Jones:
"However, this flies in the face of what Carnap writes about his motivations and objectives. His principal aim was to apply the new methods he learned first from Frege to the advancement of science, and to progress Russell's conception of a scientific philosophy using formal methods.
In my view "explication" is merely Carnap's way of connecting his methods with ordinary language for the benefit of philosophers who would not otherwise understand it."
Good. I guess that Rorty would say that Carnap saw that there was a 'linguistic turn' in the air and that even HE would rather not ignore it!
Jones: "For many philosophers it seems that the only purpose of formal languages is to provide models of aspects of the semantics and logic of natural languages"
such as English. As if an English speaker cared as to what an Oxbridge (or other) has to say about what he (the English speaker) is allegedly IMPLICATING! (or cancelling, for that matter! -- all implicatures are otiosely cancellable!).
Jones:
"But just as one speaks a second language fluently only when thinking in that language rather than translating into it,"
or as my French teacher used to say, "DREAMING" in that language too. Perhaps she had read Malcom on "Dreaming".
Jones:
"proficiency in the application of formal languages results in their native use. A formal language is the best kind of language for a variety of tasks involving the analysis of some non-linguistic subject matter, and the role of natural languages in this process is ancillary. One begins with the formal model, and perhaps adds some informal annotation to help the reader see the point. The analysis yields no information about language. This kind of analysis, of problems or of scientific domains, is more important to Carnap than the analysis of language, and should not be confused with it.
Turing is one step further from the analysis of language, for his central purpose is not analytic at all, it is technological, he is talking about what kinds of machine will in the future be constructed."
Indeed. And apparently, his prognosis went wrong. For he was rightly writing in 1950, and talking about what would be achieved in 'fifty years from now'.
And if SAYGIN is right, what we are having is computer-generated conversations that don't stop from violating Grice's maxims and stuff!
In "Behaviourist, dispositional, functional", Jones writes: "JL and I had an exchange about the relationship between "behaviourist" and "dispositional" (I wanted to know the difference)."
And a fine difference too! (Etymologically, of course, 'fine', applies best to differences!).
(Perhaps 'nice' applies best to differences, too).
Jones goes on:
"I was Googling today and found an account by [the sometime Oxonian philosopher A. N.] Prior of the difference between behaviourism and functionalism which casts some light on this. I've lost the Prior site, but no matter, there is a more complete account under "functionalism" by Janet Levin at [the Stanford Encyclopedia of Philosophy]"
which is especially Griceian in spirit, since Grice couldn't look outside the window without thinking "Stanford" (He lived in Berkeley, overlooking the bay). Keyword: "Hands across the Bay".
Jones:
"I propose here a little discussion of how Turing, Grice, Ryle and Carnap may be placed relative to the varieties of behaviourism and functionalism described by Levin and each other (dispositional appears in the definition of behaviourism)."
Good. Levin should have access to "Disposition and Intention". That may make change, dispositionally, her mind on this -- and that!
Jones:
"At SEP under the heading "Antecedents of Functionalism" we find a section on the Turing test and a section on behaviourism. I discuss the latter first."
Good. I suppose Levin got that from Block. I was fascinated to see that Block discusses Grice and Functionalism and Turing in, alas, "PROBLEMS with Functionalism" -- or problems of functionalism, I forget. _His_ problems with functionalism, or is he being, philosophically, more generally? (and speaking on behalf of other people NEEDING to find a problem where there ain't?)
Jones goes on:
"Two varieties of behaviourism, empirical and logical or analytic, are distinguished, and are considered precursors to corresponding variants of functionalism (which seek to remedy defects in the behaviourist theories)."
Good. With Ryle the main exponent of 'analytic' bheaviourism, I trust. I guess he would rather see himself dead than a living 'empirical behaviourist' alla Watson!
Jones:
"Both of these behaviourisms seek to explain something in terms of behavioural dispositions (so, both the behaviourisms and the subsequent functionalisms are dispositional)."
Perhaps Grice would use a formalism here. Take "A" to represent "A" (open the umbrella).
The disposition to open the umbrella.
Or the disposition to laugh.
Or the disposition to smile.
--- I guess we have to be specific. Only a few items counts as good follow-ups for clauses reporting 'dispositions'.
----
"2 + 2" for example, does not have a disposition to be "4".
Neither does a bachelor a disposition to be an unmarried male!
-----
Nor Spring a disposition to follow Winter!
Jones goes on:
"The empirical behaviourist explains behaviour in that way, the logical behaviourist explains the meanings of mental concepts in that way (Malcolm, Ryle and perhaps the later Wittgenstein are mentioned)."
As they should!
I am slightly saddened that Ryle chose "The concept of mind" as the title of his book. He should have called it: "The ghost without the machine", or something.
----- But he was provocative enough to have Chomsky writing "Cartesian linguistics" and bringing the anti-behaviouristic movement back to the forum (cf. Chomsky's review of Skinner?)
Jones goes on:
"The principal difference between behaviourism and functionalism is that the former deny the reality of mental states and seek explanations of behaviour or language which are independent of mental states or concepts, whereas the latter insist on mental states and offer explanations of mental states or concepts which may involve other mental states or concepts."
Indeed. Aristotle was, surprisingly, a functionalist. But of course, the way 'function' is used by Aristotelians differs from this more 'mathematical' idea of 'function', which is what functionalists use when they say that psychological attitude
psi
(in symbols, Pap ---- Agent A has psychological attitude P towards proposition p)
co-relates to some perceptual INPUT (which need not be reported in psychologistic terms) and behavioural output ('open the umbrella') (which again need not be reported in psychologistic terms).
----
Jones writes:
"It sounds as if there is a metaphysical aspect here, which relates to Ryle's desire to refute Cartesian dualism, but there are more concrete differences as well."
Indeed, and I'm glad I mentioned Chomsky's "Cartesian linguistics" because the standard mainstream Anglo-American tradition that Chomsky is criticizing is usually associated with Empiricism and Behaviourism, and, who knows, some sort of Monistic Materialism.
(But functionalists need not be monists).
----
Jones goes on:
"The functionalist allows himself to talk about mental states when giving an account of mental concepts, he does not have to give an account exclusively in terms of behaviours."
This is something that somewhat irritated Grice, when commenting on Witters. Because Witters is saying that if we say something like,
"He raised his arm against me."
WHILE a purely physical interpretation may be possible, it seems that the vocabulary used to describe behaviour is psychologically-theory-laden, as Hanson would put it.
Jones goes on:
"Functionalism comes in three varieties according to its origins. Different varieties come from early AI research (and therefore connect with Turing), and from the empirical (or "psycho-") and logical behaviourisms (the latter connecting with Ryle, the former being an empirical theory rather than a philosophical one or a philosophical theory about empirical scientific theories of mind)."
Good. Of course, Grice concentrates on Ryle in his "Method in Philosophical Psychology". I guess that as an Oxonian philosopher Grice was VERY TIRED of having to deal with Ryle's book as the opus magnum of post-war Oxford philosophy!
----
Jones goes on
"The description of "machine state functionalism" given by Levin is I hope, not quite correct (it would otherwise reflect badly on Putnam), because she seems not to understand the difference between a finite-state automaton and a Turing machine (the difference is the tape, which is a big difference)."
Good. I think Grice knew Putnam well. I love a phrase by Grice on Putnam. I guess they met when Grice first went to Harvard, although I would NOT be surprised if Putnam had had a scholarship at Oxford (it seems all American philosophers then had!). Grice writes that he used to be too formal, until, "Putnam (of all people) told me I was." I just love the implicature of "of all people".
I cannot use "of all people" without triggering the wrong implicature. I guess Grice can be literal, and he means, that, out of the set of all people, Putnam told Grice that he was _too_ formal, implicating there is something wrong about 'too'. There shouldn't. (I like my coffee too sweet, for example).
Putnam was possible formal enough, and that is where Grice's joke lies. Cfr. Putnam on H20 and XYZ.
Jones:
"If we recast her definition appropriately then Putnam's account of this kind of functionalism asserts that any creature with a mind "can be regarded as" (this seems very weak) a Turing machine and that its mental states are then to be identified with the states of the Turing machine (and that would have to be the state of the automaton and the content and position its tape, though Levin talks only of the state of the automaton)."
Excellent point.
It may all relate to the KEYWORD: multiple physical realisability, if I may use a techno-kryptical expression.
I.e. the identification (or individuation, as I prefer -- cfr. Grice's ontological marxism) of a psychological state need to be made with the STATE of the automaton AND THE CONTENT AND POSITION OF THE TAPE!
Jones:
"I quote Levin for the nub of her description of the other two kinds of functionalism."
Good.
"What is distinctive about psycho-functionalism is its claim that mental states and processes are just those entities, with just those properties, postulated by the best scientific explanation of human behavior."
I like her distinction (or difference) between a 'state' and a process. Or an event, as I may prefer. Thus,
I think that Grice is an Englishman.
I think that all Englishmen are brave.
----
Therefore, I think that Grice is brave.
Here we seem to have THREE states (three beliefs) but also one event or process. MY believing that Grice is an Englishman AND that all Englishmen are brave YIELDS or causes my belief that Grice is brave.
----
Jones goes on to quote from Levin:
"the goal of analytic functionalism is to provide “topic-neutral” translations, or analyses, of our ordinary mental state terms or concepts".
I think the vocabulary is Broadian?
Jones:
"So how do our four protagonists relate to these various kinds of behaviourism and functionalism This is my present impression. Turing so far as I can see from "Computing Machinery and Intelligence" does not fit well into any of these schemes."
If Hodges is right (and he makes the point quite a few times) that Turing was no philosopher, then Turing would NOT care! The problem is that he possibly did not see as a psychologist either (But then why submit an essay to "Mind"?). He saw himself as a mathematician, and mathematicians need not commit to any of the varieties defined (rather arbitrarily) by Levin.
Jones:
"First of all, [Turing] is very clear that his test does not test for thinking, and he explicitly disavows any opinion about whether machines can think. I think the manner of his dismissal might be thought to implicate a similar attitude to other mental concepts. Here is a salient quote: "It will simplify matters for the reader if I explain first my own beliefs in the matter. Consider first the more accurate form of the question. I believe that in about fifty years' time it will be possible, to programme computers, with a storage capacity of about 109, to make them play the imitation game so well that an average interrogator will not have more than 70 per cent chance of making the right identification after five minutes of questioning. The original question, "Can machines think?" I believe to be too meaningless to deserve discussion." He does not appear to be interested in analysis of the meaning of mental concepts, and therefore is neither an analytic behaviourist nor an analytic functionalist.
Furthermore, the above quote I believe gives the central purpose of his paper, which is to make a claim about what computers will be able to achieve at some point in the future. He not only lacks interest in the meaning of mental concepts (beyond what is unavoidable is describing his thesis), but also does not appear to be interested in scientific theories about the mind."
Excellent point. The blame here is possibly SHERBORNE, his alma mater?
----- INTERLUDE ON SHERBORNE -- (Grice went to Clifton, and that's why he became a classicist, and Renaissance-interest person gaining a scholarship to Oxford -- On the other hand,
Sherborne's s origins date back to the eighth century, when a tradition of education in Sherborne was begun by St Aldhelm.
According to legend, Alfred the Great was one of the school's early pupils.
The school was then linked with Sherborne Abbey, formerly a Benedictine house. The earliest known Master was Thomas Copeland in 1437. After the Dissolution of the Monasteries, Edward VI re-founded the school in 1550 as King Edward's School, a free grammar school for local boys. The present-day school stands on land which once belonged to the abbey's monastery. The Library, Chapel, and Headmaster's rooms, which adjoin the Abbey Church, are modifications of its original monastic buildings.
The present school's earlier lives take us back four hundred, perhaps a thousand years."
"In the Beckett Room below the library there survives Anglo-Saxon masonry, a reminder that the school occupies all that remains of the site of Sherborne Abbey (AD 705, remodelled as a Benedictine abbey in 998). The Headmaster and the senior staff now have their offices, appropriately enough, in the Abbot's house, rather grandly refashioned, like the Abbey itself, in the 15th century; the library was, perhaps, the Abbot's "Guest Hall" (13th–15th century); the Chapel occupies another monastic refectory (12th–15th century, but much rebuilt and extended in the 19th century). Go just beyond the Headmaster’s block and face the Abbey and you can see quite clearly on the walls to your right the outlines of the monastic cloister with its curious first floor Abbot’s Chapel; the conduit, where the monks wash, was removed by the Victorians and rebuilt outside Bow House.
In 2005, Sherborne School was one of 50 of the country's leading independent schools that were found guilty of running an illegal price-fixing cartel, which had allowed them to drive up fees for thousands of parents. Each school was required to pay a nominal penalty of £10,000. All schools involved in the scandal agreed to make ex-gratia payments, totalling £3 million, into a trust. The trust was designed to benefit pupils who attended the schools during the period in respect of which fee information was shared. However, Jean Scott, the head of the Independent Schools Council, said that independent schools had always been exempt from anti-cartel rules applied to business, were following a long-established procedure in sharing the information with each other, and were unaware of the change to the law (on which they had not been consulted). She wrote to John Vickers, the OFT director-general, saying, "They are not a group of businessmen meeting behind closed doors to fix the price of their products to the disadvantage of the consumer. They are schools that have quite openly continued to follow a long-established practice because they were unaware that the law had changed."
---- END OF INTERLUDE about Sherborne. My point is that perhaps while at Sherborne, Turing was motivated by the staff ONLY to concentrate on mathematics, hence his lack of interest in philosophy, the classics, or science! After all, it is an independent school. Meaning, 'independent' from the rest of the world?
----
Jones:
"This I think excludes [Turing] from being considered an empirical behaviourist or functionalist, at least as far as we can see from this paper (the paper does not exclude this, though we might think his assertion that the "Can Machines Think?" is meaningless does exclude him from being an analytic behaviourist or functionalist)."
Indeed. But then, of course, Ryle perhaps did enjoy that some of the questions that he thought meaningful, "can machines think?", say, turned out to be, according to Turing, a 'systematically misleading' one!
Jones:
"Turing is closest to a "Machine state functionalist", not surprisingly since they were probably influenced by his work. But does he fit the description? Does he think anything with a mind "can be regarded as" a Turing machine? Possibly. But this is not, on my reading, the thesis which his paper presents. I believe he is asserting functional identity between minds and Turing machines (to each mind there is a corresponding Turing machine with which it is functionally identical), though he does not say that explicitly. But "can be regarded as" I still think, though vague, a little too strong."
Good points. Hodges, for that matter, teaches TURING at Wadham, and Oxford is of course strong in KEYWORD: Philosophy of Mind, so I would not be surprised that, if we search within the Oxford Sub-Faculty of Philosophy, people with interest in mathematics, logic, and philosophy of mind, we find a neo-Turingian -- or two!
----
Jones:
"Let us now consider Grice, which I am ill qualified to do, but perhaps these remarks will provoke a better informed response from Speranza."
I can all-ways talk!
Jones:
"Grice seems to me certainly to be an analyst and to be interested in the meanings of mental concepts.
I doubt that he is any kind of behaviourist, but it seems to me that he might well be an analytic functionalist."
So far so good. He is no behaviourist, I would think, because Grice took generations very seriously, and Ryle was born in 1900, while Grice was born in 1913 -- different generation, thus, different philosophies. What's the good of philosophy if we are not going to have a HISTORY OF PHILOSOPHY? So, just to be different, Grice would NOT have liked to a be associated with Ryle, at all! (Oscar Wood did -- and other Oxonian philosophers did).
I would think Grice was a functionalist in that the basis for "Method in philosophical psychology" is said to be D. K. Lewis, and Lewis WAS a functionalist!
Jones:
"In relation to Turing, my impression is that there is little contact, neither agreement nor disagreement. Insofar as Grice is interested in automata, I would imagine this to be concerned with the insights which might be gleaned from them into the nature of language or other philosophical problems. Would he have any interest in predictions about what computers will be able to do at some point in the future?"
Don't think so. His wife said that Grice STRONGLY disliked computers for mainly two reasons:
Everytime he wrote 'sticky wicket', the spelling checking device in his computer noted that there was something wrong there.
The second reason is that his computer did not recognize "pirot" (and wanted it to be replaced, alla Locke, by parrot).
Grice had a beautiful handwriting. Is there an implicature there? And he disliked word processors, never mind computers!
-----
Also he possibly would have thought that Turing was overrated. There he was, Turing was, playing almost something like chess and crosswords -- I have to find this genial paragraph in "The imitation game" -- while Grice, qua Captain of the Royal Navy -- was offering the ultimate sacrifice in the mid-Atlantic theatre of operations!
(He was soon transferred to the Admiralty, though).
Jones:
"Ryle I should perhaps have mentioned before Grice, because he preceded Grice and behaviourism preceded functionalism we may think of Ryle (as he is cited by Levin) as being some kind of behaviourist."
Yes. Only he would not use the Americanism 'behaviour'. One tends to associate 'behaviour' with Watson, and Skinner -- a VERY AMERICAN thing, and let's recall that Ryle is famous in Oxford for avoiding the "American" influence in the city of the dreaming spires. They were reading Johnson, and Price and Cook Wilson, and all the obscure British authors -- but few American philosophers.
Perhaps there is a history of philosophical American behaviourism that connects with PRAGMATISM which seems to have been popular at Oxford for some time. I recall that when Lewis Carroll wrote "The Hunting of the Snark", it was parodied in a comical issue of "Mind" (called "Mind!") by a pragmatist philosopher of two.
William James, who was almost a behaviourist (or is he more of an introspectionalist?) was perhaps pretty influential too in Oxford. And let us not forget that when Grice went to the USA it was to give the bi-annual lecture in memory of William James co-ordinated by the Department of Philosophy and the Department of Psychology.
Let us not forget, either, that Grice lectured at Oxford on PEIRCE, whose theory of symbols, indexes, and icons (that Grice disliked) gave Grice impetus to create his theory of meaning as intention.
John Holloway is an interesting figure to consider -- Oxford educated, comes up with a book on "Language and Intelligence" that has the merit of having the name of "H. P. Grice" mentioned when H. L. A. Hart reviewed it for "The Philosophical Quarterly".
We should not forget, either, that the ONLY PHILOSOPHER that Grice quotes in "Meaning" is C. L. Stevenson (his Yale University Press book on language and ethics), and most of Stevenson's examples are BEHAVIOURISTIC in nature. In fact, D. E. Cooper and other historians of pragmatics (such as S. Levinson, in "Pragmatics", Cambridge textbooks in linguistics) traces the history of Griceian pragmatics to behaviourism, pragmatism, Peirce and Morris -- Carnap has something to do with these authors, too).
----
Jones: "Because of [Ryle's] anti-dualistic zeal and his belief that some of our language (if perhaps only at the meta-linguistic level) is tainted by dualism, it is hard to see his position as being purely analytic. He attributes category errors to certain kinds of ordinary discourse about mental concepts.
It seems to me that Ryle is engaged (in his own terms) in both descriptive and revisionary metaphysics, in analysing the metaphysical content and pathologies of language as it is, and in undertaking a profylactic metaphysical synthesis."
I loved that!
God knows what he was attempting with his "Concept of Mind". At that time, "Mind", which he edited, was still subtitled, "A review of psychology and philosophy", I think, and I would not be surprised if some of his Ryle's friends WERE psychologists, and even behaviourists (George?)
Jones:
"[Ryle's] descriptive metaphysics reveals pathologies (category errors particularly) which his revisionary metaphysics seeks to repair. What makes him seem a behaviourist is that his metaphysics is monistic, materialistic. Perhaps this is enough to call him an analytic behaviourist, but I am inclined to think that to crude a characterisation."
Yes, and perhaps too American to Ryle's taste. Note that after "Concept of Mind" he have lecture after lecture on "THINKING". Professionally, he was the official professor at Oxford of "Metaphysical Philosophy", to be succeeded by Strawson. So I guess that Ryle's favourite motto, from "Punch" was:
-- What is the matter?
-- Never mind!
---
Jones:
"Between Ryle and Turing I see no connection, their ideas seem logically independent, neither supporting nor confuting each other, though possibly mutually sympathetic in a weaker sense."
Yes. We've seen that Hodges seeks a link here, in that Ryle's Concept of Mind came out in 1949, and Turing's essay was published in "Mind", edited by Ryle, in 1950. But then, I don't think Turing was ever invited (being a Cambridge person) to educate Oxonians on this -- or that.
----
Jones:
"What of Ryle and Grice?"
---- The obituary by G. E. L. Owens of Ryle in "Aristotelian Society" is a good one. He says that Ryle belonged to this group that had Mabbott (fellow at St. John's, with Grice) and a few others. But this group never inter-acted with Austin's Play Group (we are talking post-war Oxford) to which Grice belonged ("the class of philosophers who have no other class"). Owens goes on to say that when Austin died, it was Grice who led this "Play Group" -- Ryle was still active then. Recall that Grice left Oxford for good in 1967 (although he would return for his Locke Lectures and was surprised at how rude Oxonians philosophes could be -- one, he met on High Street -- "I haven't seen you in a while. You've been away?" "Of course they knew", Mrs. Grice regrets).
Rumour has it that Grice left Oxford because when Ryle retired as Waynflete professor of philosophy, the chair was given to Grice's pupil, Strawson, rather than to Grice himself. But this seems nonsense. Grice came to LOVE Berkeley where he was given full professor credentials from the beginning and he soon was leading his own little group there -- Grice's "at homes", attended by Searle, Davidson, Barry Stroud, George Myro, Judith Baker, and almost EVERY PHILOSOPHER and graduate student on Moses Hall!
Jones:
"Of our four protagonists here, these two are probably the closest to each other." Physically, too. So English! I'm sure in their manners, they were very much alike. Public school background and all that. Only Grice grew out of that background and never allowed his son or his daughter to attend a public school!
Jones:
"Insofar as Ryle is engaged in metaphysics, this would be of interest to Grice, though perhaps only the descriptive rather than the revisionary metaphysics."
Indeed.
Ryle was hardly systematic, though. While Grice was the systematic philosopher par excellence. And the older he got he more systematic he became. On the other hand, one reads Ryle's collection of essays, and one doesn't know what he is trying to achieve! (I always find him entertaining, though, and find his "Fido"-Fido theory of meaning a delight to refute!).
Jones:
"Grice's ontological pragmatism" or Marxism, as I prefer, "would I imagine leave him poorly motivated to enter into a crusade against Cartesian dualism."
Indeed. I was fascinated, when I got my copy of WoW (Way of Words) to find that Grice cared to include a historical essay he had written, back in the day, on DESCARTES!
Grice is into criticizing Descartes's rather casual difference between
"It is certain".
and
"I am certain".
Certainly, Grice saw a world of a difference between what he calls 'objective certainty' ("It is certain that it is raining, hence Smith is dispositionally inclined to open his umbrella") and 'subjective certainty' ("Smith is certain that it will rain; of course, this is quite different from saying that he KNOWS that it will rain").
Subjective certainty had been posed by Ayer as a criterion for empirical knowledge, and Grice knew better than that! ("I was certain that p, but it turned out that p was false" makes a lot of sense; whereas, "I knew that p, but then it turned out that p was false" triggers a contradictory implicature!).
Jones:
"Functionalism is however very accommodating, it does not seem to exclude much, and so Grice might well be an analytic functionalist, the distinction between him and Ryle similar to that between an analytic functionalist and an analytic behaviourist."
Problem with Grice's "Method in philosophical psychology" is that when one was thinking he would get into Turing and all that, he starts discussing Aristotle's idea of a 'soul'!
Grice thinks that 'soul' can only be analysed 'gradually'. He notes that Aristotle says that there are a few concepts (not just 'soul') that require this 'gradual' analysis. The other is 'number'.
So, he dedicates the central part of "Method in philosophical psychology: from the banal to the bizarre", to see how we can create creatures (if you allow me the redundancy -- Grice calls them pirots -- and the science of pirots: pirotology) which more and more complex psychological abilities.
He is interested in embedding connectives within psychological states.
As if I were to say:
"If Grice thinks that all Englishmen are brave AND Grice thinks that he is an Englishman; Grice thinks that he is brave. And this is analytic".
This is still different from:
"Grice thinks that if all Englishmen are brave, and that he is an Englishman, he is brave. And he thinks that this is analytic".
I am thinking of the analytic conditional associated with a piece of valid deductive reasoning. And possibly failing!
Let us not forget that Grice's third book, "Aspects of reason", is ALL ABOUT psychology, and how psychological operators can embed complex logical expressions.
Jones: "I now come to Carnap, the scientifically oriented scourge of metaphysics. The special features which Carnap brought in his anti-metaphysical fervour are of interest here. Before Carnap we would expect a positivist to be also a phenomenalist, and therefore to have no truck with Cartesian dualism and to be close to analytical and psychological behaviourism."
Good you bring PHENOMENALISM in!
Jones goes on: "Carnap's anti-metaphysics is novel (for a positivist) in being ontologically liberal and pragmatic rather than nominalistic."
Indeed. His distinction between internal and external questions may relate here.
Jones:
"This is reflected in his linguistic pluralism, and so, though he worked primarily with ontologies in which there were no mental entities (phenomenal, physical, and theoretical languages), he would not have ruled them out on principle (that would violate his principle of tolerance)."
Indeed. And it would not be difficult to trace him to tendencies found in American pragmatism, alla Morris, and other philosophers who were into 'operational' approaches to 'mentalistic' talk.
Jones:
"In consequence Carnap could not be a doctrinaire behaviourist, but would admit a behaviouristic scientific theory if it could by empirically confirmed."
Indeed. As opposed to Popper who would rather endose any FALSIFIED theory anyday!
Grice spends some time on issues of falsification and confirmation of theories in "Method" and goes on to quote a few 'psychological laws' from the literature, as he calls them. He is especially interested in finding them EMPTY!
Qua functionalist, Grice is allowing for psychological predicates to be introduced (via Ramsified naming and Ramsified describing) as theoretical terms, to be correlated with perceptual input and behavioural input ("No need of psychological concepts without behaviour which such concepts are called on to explain" -- his rewrite of Witters's dictum).
Jones:
"[Carnap] was concerned with scientific method, and I think it plausible that he would have been some kind of empirical or psycho- functionalist. Carnap's conception of philosophy was as a kind of analysis, but like Turing, he lacked interest in the details of natural languages, for much the same reasons. He advocated the use of formal notations and methods in philosophy and science, and explained the relationship between formalised concepts and those of natural languages as "explication", a relationship too weak perhaps to allow that the formal theories provided analyses of the natural concepts."
I like that. We have Carnap's explications and Grice's explicatures.
And I'm reminded of Byron who referring to an exegesis of a literary critic of a specially obscure poem, he wrote, "His explication is fine; but I fear we may need an explication of his explication." (I owe the quote to J. L. Borges, who gave the Eliot Lectures at Harvard while Grice was delivering the William James lectures).
Joness:
"Because of [Carnap's] desire to formalise and his scientific orientation it seems to me that Carnap is closer to Turing than to Ryle or Grice [...]"
and perhaps associated to the movement, so popular in America for a time, of a 'unified science'...
Jones: "[A]nd I see no conflict between the views of Carnap and Turing. Carnap's relationship to Ryle and Grice is more difficult."
Indeed, especially in view of a sort of generalized anti-scientism prominent in post-war Oxford. Grice kept lecturing on the 'devil of scientism' in his "Method in philosophical psychology", but he must have found that his audience had changed! (Perhaps Haugeland, Dreyfus, and Searle, found a strong sympathy on these issues, though).
Jones:
"As a formalist [Carnap] lacked interest in the minutiae of natural languages, as a positivist one would expect him to be antagonistic to the metaphysical aspects of Ryle's thesis (nominalism is metaphysics for Carnap). What is the point of this long ramble?"
"Should rambles have a point?" This is a favourite question in one of my favourite books.
Edward Step.
Step E. (1930) Nature Rambles: an Introduction to Country-lore, (4 volumes) Frederick Warne & Co. Ltd., London & NY: 256 pp.
Jones concludes:
"Well, one thing which I think important is a point about varieties of analysis."
Or "Annals of Anaysis", as I prefer -- Travis's title for his LONG review of Grice's WoW -- Way of Words -- in "Philosophical Review"!
Jones:
"Analytic philosophers seem often exclusively concerned with the analysis of ordinary language, and may too readily assume that what other philosophers (or even non-philosophical analysts) are doing is the analysis of language."
Or worse, English!
I am often amused by the fact that Grice found Latin and Greek superior to English. In "Aspects of Reason" he is discussing psychological predicates and the clauses by which they are followed, and find that Greek and Latin (that he had learned at Clifton) allow for nuances that English doesn't. Example: the imperative mode (never mood!) -- the optative mode, the so-called 'subjunctive' mood. Why are they becoming archaic in English? True, they ARE archaic in the archaic Greek and Latin he learned at Clifton too!
(Grice was amused that of all things, this was the minutiae that Gellner and Bergmann cared to choose when criticisng the "Oxford" type of analysis -- "futilitarianism", Bergmann called it -- a sensitivity for English usage found only, Gellner and Grice agree, on those educated at public school and later one of what Grice (and many others) call the 'stone-wall' Oxbridge, never redbrick! Grice is amused by this because he knew Gellner was oversimplifying: of course you don't have to be a public school Oxbridge type to delight in this or that linguistic mannerism!)
Jones: "Turing and Carnap in different ways offer examples of work which may be misconstrued as concerned with the analysis of ordinary language. Turing may be misconstrued as giving a test for or an analysis of the meaning of the concepts of "thought" or of "intelligence" when his purpose was simply to argue that humans had no intellectual capacities which could not be realised in a machines"
- and he proved that! (I love that episode when he breaks his engagement with Ms. Clarke, played by Keira Knightley -- I should find her genial riposte -- or is it retort? -- in the screenplay)
Jones:
"Carnap can be construed as primarily concerned with the explication of terms in ordinary language, and it is the central thrust of Carus's book on Carnap and 20th Century thought that the notion of explication is the centrepiece of Carnap's philosophy."
As perhaps Grice's explicature ain't!
Jones:
"However, this flies in the face of what Carnap writes about his motivations and objectives. His principal aim was to apply the new methods he learned first from Frege to the advancement of science, and to progress Russell's conception of a scientific philosophy using formal methods.
In my view "explication" is merely Carnap's way of connecting his methods with ordinary language for the benefit of philosophers who would not otherwise understand it."
Good. I guess that Rorty would say that Carnap saw that there was a 'linguistic turn' in the air and that even HE would rather not ignore it!
Jones: "For many philosophers it seems that the only purpose of formal languages is to provide models of aspects of the semantics and logic of natural languages"
such as English. As if an English speaker cared as to what an Oxbridge (or other) has to say about what he (the English speaker) is allegedly IMPLICATING! (or cancelling, for that matter! -- all implicatures are otiosely cancellable!).
Jones:
"But just as one speaks a second language fluently only when thinking in that language rather than translating into it,"
or as my French teacher used to say, "DREAMING" in that language too. Perhaps she had read Malcom on "Dreaming".
Jones:
"proficiency in the application of formal languages results in their native use. A formal language is the best kind of language for a variety of tasks involving the analysis of some non-linguistic subject matter, and the role of natural languages in this process is ancillary. One begins with the formal model, and perhaps adds some informal annotation to help the reader see the point. The analysis yields no information about language. This kind of analysis, of problems or of scientific domains, is more important to Carnap than the analysis of language, and should not be confused with it.
Turing is one step further from the analysis of language, for his central purpose is not analytic at all, it is technological, he is talking about what kinds of machine will in the future be constructed."
Indeed. And apparently, his prognosis went wrong. For he was rightly writing in 1950, and talking about what would be achieved in 'fifty years from now'.
And if SAYGIN is right, what we are having is computer-generated conversations that don't stop from violating Grice's maxims and stuff!
Behaviourist, dispositional, functional
Roger Bishop Jones
JL and I had an exchange about the relationship between "behaviourist" and "dispositional" (I wanted to know the difference).
I was Googling today and found an account by Prior of the difference between behaviourism and functionalism which casts some light on this.
I've lost the Prior site, but no matter, there is a more complete account under "functionalism" by Janet Levin at SEP.
I propose here a little discussion of how Turing, Grice, Ryle and Carnap may be placed relative to the varieties of behaviourism and functionalism described by Levin and each other (dispositional appears in the definition of behaviourism).
At SEP under the heading "Antecedents of Functionalism" we find a section on the Turing test and a section on behaviourism. I discuss the latter first.
Two varieties of behaviourism, empirical and logical or analytic, are distinguished, and are considered precursors to corresponding variants of functionalism (which seek to remedy defects in the behaviourist theories).
Both of these behaviourisms seek to explain something in terms of behavioural dispositions (so, both the behaviourisms and the subsequent functionalisms are dispositional). The empirical behaviourist explains behaviour in that way, the logical behaviourist explains the meanings of mental concepts in that way (Malcom, Ryle and perhaps the later Wittgenstein are mentioned).
The principal difference between behaviourism and functionalism is that the former deny the reality of mental states and seek explanations of behaviour or language which are independent of mental states or concepts, whereas the latter insist on mental states and offer explanations of mental states or concepts which may involve other mental states or concepts. It sounds as if there is a metaphysical aspect here, which relates to Ryle's desire to refute Cartesian dualism, but there are more concrete differences as well. The functionalist allows himself to talk about mental states when giving an account of mental concepts, he does not have to give an account exclusively in terms of behaviours.
Functionalism comes in three varieties according to its origins. Different varieties come from early AI research (and therefore connect with Turing), and from the empirical (or "psycho-") and logical behaviourisms (the latter connecting with Ryle, the former being an empirical theory rather than a philosophical one or a philosophical theory about empirical scientific theories of mind).
The description of "machine state functionalism" given by Levin is I hope, not quite correct (it would otherwise reflect badly on Putnam), because she seems not to understand the difference between a finite state automaton and a turing machine (the difference is the tape, which is a big difference). If we recast her definition appropriately then Putnam's account of this kind of functionalism asserts that any creature with a mind "can be regarded as" (this seems very weak) a Turing machine and that its mental states are then to be identified with the states of the Turing machine (and that would have to be the state of the automaton and the content and position its tape, though Levin talks only of the state of the automaton).
I quote Levin for the nub of her description of the other two kinds of functionalism.
"What is distinctive about psycho-functionalism is its claim that mental states and processes are just those entities, with just those properties, postulated by the best scientific explanation of human behavior."
"the goal of analytic functionalism is to provide “topic-neutral” translations, or analyses, of our ordinary mental state terms or concepts"
So how do our four protagonists relate to these various kinds of behaviourism and functionalism?
This is my present impression.
Turing so far as I can see from "Computing Machinery and Intelligence" does not fit well into any of these schemes.
First of all, he is very clear that his test does not test for thinking, and he explicitly disavows any opinion about whether machines can think. I think the manner of his dismissal might be thought to implicate a similar attitude to other mental concepts.
Here is a salient quote:
"It will simplify matters for the reader if I explain first my own beliefs in the matter. Consider first the more accurate form of the question. I believe that in about fifty years' time it will be possible, to programme computers, with a storage capacity of about 109, to make them play the imitation game so well that an average interrogator will not have more than 70 per cent chance of making the right identification after five minutes of questioning. The original question, "Can machines think?" I believe to be too meaningless to deserve discussion."
He does not appear to be interested in analysis of the meaning of mental concepts, and therefore is neither an analytic behaviourist nor an analytic functionalist.
Furthermore, the above quote I believe gives the central purpose of his paper, which is to make a claim about what computers will be able to achieve at some point in the future. He not only lacks interest in the meaning of mental concepts (beyond what is unavoidable is describing his thesis), but also does not appear to be interested in scientific theories about the mind. This I think excludes him from being considered an empirical behaviourist or functionalist, at least as far as we can see from this paper (the paper does not exclude this,
though we might think his assertion that the "Can Machines Think?" is meaningless does exclude him from being an analytic behaviourist or functionalist).
Turing is closest to a "Machine state functionalist", not surprisingly since they were probably influenced by his work. But does he fit the description?
Does he think anything with a mind "can be regarded as" a Turing machine?
Possibly.
But this is not, on my reading, the thesis which his paper presents.
I believe he is asserting functional identity between minds and Turing machines (to each mind there is a corresponding Turing machine with which it is functionally identical), though he does not say that explicitly.
But "can be regarded as" I still think, though vague, a little too strong.
Let us now consider Grice, which I am ill qualified to do, but perhaps these remarks will provoke a better informed response from Speranza.
Grice seems to me certainly to be an analyst and to be interested in the meanings of mental concepts.
I doubt that he is any kind of behaviourist, but it seems to me that he might well be an analytic functionalist.
In relation to Turing, my impression is that there is little contact, neither agreement nor disagreement.
Insofar as Grice is interested in automata, I would imagine this to be concerned with the insights which might be gleaned from them into the nature of language or other philosophical problems.
Would he have any interest in predictions about what computers will be able to do at some point in the future?
Ryle I should perhaps have mentioned before Grice, because he preceded Grice and behaviourism preceded functionalism we may think of Ryle (as he is cited by Levin) as being some kind of behaviourist.
Because of his anti-dualistic zeal and his belief that some of our language (if perhaps only at the metalinguistic level) is tainted by dualism, it is hard to see his position as being purely analytic. He attributes category errors to certain kinds of ordinary discourse about mental concepts.
It seems to me that Ryle is engaged (in his own terms) in both descriptive and revisionary metaphysics, in analysing the metaphysical content and pathologies of language as it is, and in undertaking a profylactic metaphysical synthesis. His descriptive metaphysics reveals pathologies (category errors particularly) which his revisionary metaphysics seeks to repair.
What makes him seem a behaviourist is that his metaphysics is monistic, materialistic. Perhaps this is enough to call him an analytic behaviourist, but I am inclined to think that to crude a characterisation.
Between Ryle and Turing I see no connection, their ideas seem logically independent, neither supporting nor confuting each other, though possibly mutually sympathetic in a weaker sense.
What of Ryle and Grice?
Of our four protagonists here, these two are probably the closest to each other.
Insofar as Ryle is engaged in metaphysics, this would be of interest to Grice, though perhaps only the descriptive rather than the revisionary metaphysics.
Grice's ontological pragmatism would I imagine leave him poorly motivated to enter into a crusade against Cartesian dualism.
Functionalism is however very accommodating, it does not seem to exclude much, and so Grice might well be an analytic functionalist, the distinction between him and Ryle similar to that between an analytic functionalist and an analytic behaviourist.
I now come to Carnap, the scientifically oriented scourge of metaphysics.
The special features which Carnap brought in his anti-metaphysical fervour are of interest here.
Before Carnap we would expect a positivist to be also a phenomenalist, and therefore to have no truck with Cartesian dualism and to be close to analytical and psychological behaviourism.
Carnap's anti-metaphysics is novel (for a positivist) in being ontologically liberal and pragmatic rather than nominalistic. This is reflected in his linguistic pluralism, and so, though he worked primarily with ontologies in which there were no mental entities (phenomenal, physical, and theoretical languages), he would not have ruled them out on principle (that would violate his principle of tolerance). In consequence Carnap could not be a doctrinaire behaviourist, but would admit a behaviouristic scientific theory if it could by empirically confirmed.
He was concerned with scientific method, and I think it plausible that he would have been some kind of empirical or psycho- functionalist.
Carnap's conception of philosophy was as a kind of analysis, but like Turing, he lacked interest in the details of natural languages, for much the same reasons. He advocated the use of formal notations and methods in philosophy and science, and explained the relationship between formalised concepts and those of natural languages as "explication", a relationship too weak perhaps to allow that the formal theories provided analyses of the natural concepts.
Because of his desire to formalise and his scientific orientation it seems to me that Carnap is closer to Turing than to Ryle or Grice, and I see no conflict between the views of Carnap and Turing.
Carnap's relationship to Ryle and Grice is more difficult.
As a formalist he lacked interest in the minutiae of natural languages, as a positivist one would expect him to be antagonistic to the metaphysical aspects of Ryle's thesis (nominalism is metaphysics for Carnap).
What is the point of this long ramble?
Well one thing which I think important is a point about varieties of analysis.
Analytic philosophers seem often exclusively concerned with the analysis of ordinary language, and may too readily assume that what other philosophers (or even non-philosophical analysts) are doing is the analysis of language.
Turing and Carnap in different ways offer examples of work which may be misconstrued as concerned with the analysis of ordinary language.
Turing may be misconstrued as giving a test for or an analysis of the meaning of the concepts of "thought" or of "intelligence" when his purpose was simply to argue that humans had no intellectual capacities which could not be realised in a machines.
Carnap can be construed as primarily concerned with the explication of terms in ordinary language, and it is the central thrust of Carus' book on Carnap and 20th Century thought that the notion of explication is the centrepiece of Carnap's philosophy. However, this flies in the face of what Carnap writes about his motivations and objectives. His principal aim was to apply the new methods he learned first from Frege to the advancement of science, and to progress Russell's conception of a scientific philosophy using formal methods.
In my view "explication" is merely Carnap's way of connecting his methods with ordinary language for the benefit of philosophers who would not otherwise understand it.
For many philosophers it seems that the only purpose of formal languages is to provide models of aspects of the semantics and logic of natural languages.
But just as one speaks a second language fluently only when thinking in that language rather than translating into it, proficiency in the application of formal languages results in their native use. A formal language is the best kind of language for a variety of tasks involving the analysis of some non-linguistic subject matter, and the role of natural languages in this process is ancillary. One begin's with the formal model, and perhaps adds some informal annotation to help the reader see the point. The analysis yields
no information about language.
This kind of analysis, of problems or of scientific domains, is more important to Carnap than the analysis of language, and should not be confused with it.
Turing is one step further from the analysis of language, for his central purpose is not analytic at all, it is technological, he is talking about what kinds of machine will in the future be constructed.
Roger Jones
JL and I had an exchange about the relationship between "behaviourist" and "dispositional" (I wanted to know the difference).
I was Googling today and found an account by Prior of the difference between behaviourism and functionalism which casts some light on this.
I've lost the Prior site, but no matter, there is a more complete account under "functionalism" by Janet Levin at SEP.
I propose here a little discussion of how Turing, Grice, Ryle and Carnap may be placed relative to the varieties of behaviourism and functionalism described by Levin and each other (dispositional appears in the definition of behaviourism).
At SEP under the heading "Antecedents of Functionalism" we find a section on the Turing test and a section on behaviourism. I discuss the latter first.
Two varieties of behaviourism, empirical and logical or analytic, are distinguished, and are considered precursors to corresponding variants of functionalism (which seek to remedy defects in the behaviourist theories).
Both of these behaviourisms seek to explain something in terms of behavioural dispositions (so, both the behaviourisms and the subsequent functionalisms are dispositional). The empirical behaviourist explains behaviour in that way, the logical behaviourist explains the meanings of mental concepts in that way (Malcom, Ryle and perhaps the later Wittgenstein are mentioned).
The principal difference between behaviourism and functionalism is that the former deny the reality of mental states and seek explanations of behaviour or language which are independent of mental states or concepts, whereas the latter insist on mental states and offer explanations of mental states or concepts which may involve other mental states or concepts. It sounds as if there is a metaphysical aspect here, which relates to Ryle's desire to refute Cartesian dualism, but there are more concrete differences as well. The functionalist allows himself to talk about mental states when giving an account of mental concepts, he does not have to give an account exclusively in terms of behaviours.
Functionalism comes in three varieties according to its origins. Different varieties come from early AI research (and therefore connect with Turing), and from the empirical (or "psycho-") and logical behaviourisms (the latter connecting with Ryle, the former being an empirical theory rather than a philosophical one or a philosophical theory about empirical scientific theories of mind).
The description of "machine state functionalism" given by Levin is I hope, not quite correct (it would otherwise reflect badly on Putnam), because she seems not to understand the difference between a finite state automaton and a turing machine (the difference is the tape, which is a big difference). If we recast her definition appropriately then Putnam's account of this kind of functionalism asserts that any creature with a mind "can be regarded as" (this seems very weak) a Turing machine and that its mental states are then to be identified with the states of the Turing machine (and that would have to be the state of the automaton and the content and position its tape, though Levin talks only of the state of the automaton).
I quote Levin for the nub of her description of the other two kinds of functionalism.
"What is distinctive about psycho-functionalism is its claim that mental states and processes are just those entities, with just those properties, postulated by the best scientific explanation of human behavior."
"the goal of analytic functionalism is to provide “topic-neutral” translations, or analyses, of our ordinary mental state terms or concepts"
So how do our four protagonists relate to these various kinds of behaviourism and functionalism?
This is my present impression.
Turing so far as I can see from "Computing Machinery and Intelligence" does not fit well into any of these schemes.
First of all, he is very clear that his test does not test for thinking, and he explicitly disavows any opinion about whether machines can think. I think the manner of his dismissal might be thought to implicate a similar attitude to other mental concepts.
Here is a salient quote:
"It will simplify matters for the reader if I explain first my own beliefs in the matter. Consider first the more accurate form of the question. I believe that in about fifty years' time it will be possible, to programme computers, with a storage capacity of about 109, to make them play the imitation game so well that an average interrogator will not have more than 70 per cent chance of making the right identification after five minutes of questioning. The original question, "Can machines think?" I believe to be too meaningless to deserve discussion."
He does not appear to be interested in analysis of the meaning of mental concepts, and therefore is neither an analytic behaviourist nor an analytic functionalist.
Furthermore, the above quote I believe gives the central purpose of his paper, which is to make a claim about what computers will be able to achieve at some point in the future. He not only lacks interest in the meaning of mental concepts (beyond what is unavoidable is describing his thesis), but also does not appear to be interested in scientific theories about the mind. This I think excludes him from being considered an empirical behaviourist or functionalist, at least as far as we can see from this paper (the paper does not exclude this,
though we might think his assertion that the "Can Machines Think?" is meaningless does exclude him from being an analytic behaviourist or functionalist).
Turing is closest to a "Machine state functionalist", not surprisingly since they were probably influenced by his work. But does he fit the description?
Does he think anything with a mind "can be regarded as" a Turing machine?
Possibly.
But this is not, on my reading, the thesis which his paper presents.
I believe he is asserting functional identity between minds and Turing machines (to each mind there is a corresponding Turing machine with which it is functionally identical), though he does not say that explicitly.
But "can be regarded as" I still think, though vague, a little too strong.
Let us now consider Grice, which I am ill qualified to do, but perhaps these remarks will provoke a better informed response from Speranza.
Grice seems to me certainly to be an analyst and to be interested in the meanings of mental concepts.
I doubt that he is any kind of behaviourist, but it seems to me that he might well be an analytic functionalist.
In relation to Turing, my impression is that there is little contact, neither agreement nor disagreement.
Insofar as Grice is interested in automata, I would imagine this to be concerned with the insights which might be gleaned from them into the nature of language or other philosophical problems.
Would he have any interest in predictions about what computers will be able to do at some point in the future?
Ryle I should perhaps have mentioned before Grice, because he preceded Grice and behaviourism preceded functionalism we may think of Ryle (as he is cited by Levin) as being some kind of behaviourist.
Because of his anti-dualistic zeal and his belief that some of our language (if perhaps only at the metalinguistic level) is tainted by dualism, it is hard to see his position as being purely analytic. He attributes category errors to certain kinds of ordinary discourse about mental concepts.
It seems to me that Ryle is engaged (in his own terms) in both descriptive and revisionary metaphysics, in analysing the metaphysical content and pathologies of language as it is, and in undertaking a profylactic metaphysical synthesis. His descriptive metaphysics reveals pathologies (category errors particularly) which his revisionary metaphysics seeks to repair.
What makes him seem a behaviourist is that his metaphysics is monistic, materialistic. Perhaps this is enough to call him an analytic behaviourist, but I am inclined to think that to crude a characterisation.
Between Ryle and Turing I see no connection, their ideas seem logically independent, neither supporting nor confuting each other, though possibly mutually sympathetic in a weaker sense.
What of Ryle and Grice?
Of our four protagonists here, these two are probably the closest to each other.
Insofar as Ryle is engaged in metaphysics, this would be of interest to Grice, though perhaps only the descriptive rather than the revisionary metaphysics.
Grice's ontological pragmatism would I imagine leave him poorly motivated to enter into a crusade against Cartesian dualism.
Functionalism is however very accommodating, it does not seem to exclude much, and so Grice might well be an analytic functionalist, the distinction between him and Ryle similar to that between an analytic functionalist and an analytic behaviourist.
I now come to Carnap, the scientifically oriented scourge of metaphysics.
The special features which Carnap brought in his anti-metaphysical fervour are of interest here.
Before Carnap we would expect a positivist to be also a phenomenalist, and therefore to have no truck with Cartesian dualism and to be close to analytical and psychological behaviourism.
Carnap's anti-metaphysics is novel (for a positivist) in being ontologically liberal and pragmatic rather than nominalistic. This is reflected in his linguistic pluralism, and so, though he worked primarily with ontologies in which there were no mental entities (phenomenal, physical, and theoretical languages), he would not have ruled them out on principle (that would violate his principle of tolerance). In consequence Carnap could not be a doctrinaire behaviourist, but would admit a behaviouristic scientific theory if it could by empirically confirmed.
He was concerned with scientific method, and I think it plausible that he would have been some kind of empirical or psycho- functionalist.
Carnap's conception of philosophy was as a kind of analysis, but like Turing, he lacked interest in the details of natural languages, for much the same reasons. He advocated the use of formal notations and methods in philosophy and science, and explained the relationship between formalised concepts and those of natural languages as "explication", a relationship too weak perhaps to allow that the formal theories provided analyses of the natural concepts.
Because of his desire to formalise and his scientific orientation it seems to me that Carnap is closer to Turing than to Ryle or Grice, and I see no conflict between the views of Carnap and Turing.
Carnap's relationship to Ryle and Grice is more difficult.
As a formalist he lacked interest in the minutiae of natural languages, as a positivist one would expect him to be antagonistic to the metaphysical aspects of Ryle's thesis (nominalism is metaphysics for Carnap).
What is the point of this long ramble?
Well one thing which I think important is a point about varieties of analysis.
Analytic philosophers seem often exclusively concerned with the analysis of ordinary language, and may too readily assume that what other philosophers (or even non-philosophical analysts) are doing is the analysis of language.
Turing and Carnap in different ways offer examples of work which may be misconstrued as concerned with the analysis of ordinary language.
Turing may be misconstrued as giving a test for or an analysis of the meaning of the concepts of "thought" or of "intelligence" when his purpose was simply to argue that humans had no intellectual capacities which could not be realised in a machines.
Carnap can be construed as primarily concerned with the explication of terms in ordinary language, and it is the central thrust of Carus' book on Carnap and 20th Century thought that the notion of explication is the centrepiece of Carnap's philosophy. However, this flies in the face of what Carnap writes about his motivations and objectives. His principal aim was to apply the new methods he learned first from Frege to the advancement of science, and to progress Russell's conception of a scientific philosophy using formal methods.
In my view "explication" is merely Carnap's way of connecting his methods with ordinary language for the benefit of philosophers who would not otherwise understand it.
For many philosophers it seems that the only purpose of formal languages is to provide models of aspects of the semantics and logic of natural languages.
But just as one speaks a second language fluently only when thinking in that language rather than translating into it, proficiency in the application of formal languages results in their native use. A formal language is the best kind of language for a variety of tasks involving the analysis of some non-linguistic subject matter, and the role of natural languages in this process is ancillary. One begin's with the formal model, and perhaps adds some informal annotation to help the reader see the point. The analysis yields
no information about language.
This kind of analysis, of problems or of scientific domains, is more important to Carnap than the analysis of language, and should not be confused with it.
Turing is one step further from the analysis of language, for his central purpose is not analytic at all, it is technological, he is talking about what kinds of machine will in the future be constructed.
Roger Jones
SAYGIN, GRICE, TURING: The Implicature Game
Speranza
Jones, elsewhere: "Can you say more about the relevance of the cooperative principle?"
I think Saygin is noting that computer-generated 'conversational moves' can be tricky.
It's interesting that Turing speaks of 'games' (imitation game). So does Grice. I once counted all the references to these phrases by Grice in "Logic and Conversation"
-- 'conversational game'
-- 'conversational move'
and so on.
Now, SAYGIN seems to base his thing on the best known account of the "implicature" theory as per Essay 2 in Grice, WoW.
But, as we know, this is a specific format of the implicature theory that Grice formulated, in a 'popular' style, as it were, for his William James Lectures.
We have evidence that he was tutoring on implicature at Oxford in a perhaps more technical context, as part of a seminar for his students.
The differences seem to be that the William James version is centred around this idea that Grice is 'echoing Kant', and thus using
'conversational category'
informally. The categories being FOUR: quality, quantity, mode, and relation.
He does see that he needs like an overarching principle to organize the 'maxims' falling under these four categories. Hence his idea of the Cooperative Principle.
In the earlier lectures, he does speak of 'helpfulness', and co-ordinated activities. But, to my mind, in a freer spirit, he does not need to 'echo Kant', and thus we do not have any reference to these four rather 'fictional' categories of quality, quantity, relation, and mode.
Recall that for Kant, these four categories pertain to a different field: the analysis of propositions. Grice is playing with Kant, and using the well-known 'ontological' or 'cognitive' categories into what the calls 'conversational categories.
In the earlier seminar notes, he speaks of principles and desiderata, such as candour, and clarity.
The main idea is there, that there is helpfulness (the later technical 'cooperative principle') and desiderata ('maxims'?).
The earlier notes are not too specific about 'implicature', but he does use the expression.
The later William James lectures are specifically addressed to the idea of 'implicature', and in particular its application to 'logic'. Within logic, Grice is especially interested in refuting Strawson who had said a couple of simplistic things about the 'horseshoe'.
That's why in "Prolegomena", in WoW, Grice makes the effort to quote verbatim from Strawson's book, "Introduction to logical theory" -- the segment about how the horseshoe of the logician does NOT correspond to 'if'.
The second lecture is a general account of implicature.
The third lecture introduces the 'modified Ockham razor': there should NOT be two 'senses' of "if" (or any other item). Do not multiply sense of 'if' beyond necessity.
It's the fourth lecture that picks up Strawson's point. Grice later reprinted this lecture (1988 for the first time, when WoW went to press) as 'Indicative Conditionals'.
After that the remaining William James lectures are a 'conceptual analysis' of what it means to 'imply' as oppose to 'say', and how 'imply' can be seen as a variety of 'mean', on which Grice had proposed a rather specific thesis with his "Meaning" of 1948.
Saygin is interested in the mechanism that Grice calls 'exploitation'.
Also, Saygin is considered the more basic 'violation'.
How is a maxim violated?
In cooperative conversation between rational agents, a maxim is violated, when 'exploited'. The justification is the triggering of an 'implicature'.
Thus, if we use 'if', we may still stick to a truth-functional account of 'if' as the horse-shoe of the logician and argue that the 'implicature' of inferrability (that Strawson was interested in, and that he saw in the natural counterpart of the horseshoe) can be understood as an INTENTIONAL violation (or exploitation) of these desiderata, principles, and maxims of conversation.
Thus Grice can defend a truth-functional account of the connectives, and state that Strawson is making in mistake in ignoring the conversational factors that play into this alleged divergence between natural-language 'if' and the horseshoe.
Saygin generalizes the idea of a 'maxim violation', and seems to place the phenomenon as a mark of rationality: when the violation is perceived as intentional by the co-conversationalist, for the purpose of generating an implicature, it is justified.
Grice is tricky here. He seems to be saying that a maxim may be 'violated' (exploited) at the level of what is EXPLICITLY communicated (or said), but NOT at the level of what is IMPLICATED.
He may also say that while the maxim is violated intentionally (exploited), the overarching cooperative principle IS NOT.
The idea of having a general principle and more specific maxims is of course Kantian in spirit. But Kant is never too clear as to what his maxims are, and Grice will pick up the issue in his more technical seminars on Kant's ethical theory at Berkeley.
I don't think THIS Kantian side to Grice interests Saygin -- but the underlying point that Saygin, Grice, and Kant -- and why not Turing? -- may share pertains to to how this 'illustrates' how 'rationality' works in conversation.
Jones, elsewhere: "Can you say more about the relevance of the cooperative principle?"
I think Saygin is noting that computer-generated 'conversational moves' can be tricky.
It's interesting that Turing speaks of 'games' (imitation game). So does Grice. I once counted all the references to these phrases by Grice in "Logic and Conversation"
-- 'conversational game'
-- 'conversational move'
and so on.
Now, SAYGIN seems to base his thing on the best known account of the "implicature" theory as per Essay 2 in Grice, WoW.
But, as we know, this is a specific format of the implicature theory that Grice formulated, in a 'popular' style, as it were, for his William James Lectures.
We have evidence that he was tutoring on implicature at Oxford in a perhaps more technical context, as part of a seminar for his students.
The differences seem to be that the William James version is centred around this idea that Grice is 'echoing Kant', and thus using
'conversational category'
informally. The categories being FOUR: quality, quantity, mode, and relation.
He does see that he needs like an overarching principle to organize the 'maxims' falling under these four categories. Hence his idea of the Cooperative Principle.
In the earlier lectures, he does speak of 'helpfulness', and co-ordinated activities. But, to my mind, in a freer spirit, he does not need to 'echo Kant', and thus we do not have any reference to these four rather 'fictional' categories of quality, quantity, relation, and mode.
Recall that for Kant, these four categories pertain to a different field: the analysis of propositions. Grice is playing with Kant, and using the well-known 'ontological' or 'cognitive' categories into what the calls 'conversational categories.
In the earlier seminar notes, he speaks of principles and desiderata, such as candour, and clarity.
The main idea is there, that there is helpfulness (the later technical 'cooperative principle') and desiderata ('maxims'?).
The earlier notes are not too specific about 'implicature', but he does use the expression.
The later William James lectures are specifically addressed to the idea of 'implicature', and in particular its application to 'logic'. Within logic, Grice is especially interested in refuting Strawson who had said a couple of simplistic things about the 'horseshoe'.
That's why in "Prolegomena", in WoW, Grice makes the effort to quote verbatim from Strawson's book, "Introduction to logical theory" -- the segment about how the horseshoe of the logician does NOT correspond to 'if'.
The second lecture is a general account of implicature.
The third lecture introduces the 'modified Ockham razor': there should NOT be two 'senses' of "if" (or any other item). Do not multiply sense of 'if' beyond necessity.
It's the fourth lecture that picks up Strawson's point. Grice later reprinted this lecture (1988 for the first time, when WoW went to press) as 'Indicative Conditionals'.
After that the remaining William James lectures are a 'conceptual analysis' of what it means to 'imply' as oppose to 'say', and how 'imply' can be seen as a variety of 'mean', on which Grice had proposed a rather specific thesis with his "Meaning" of 1948.
Saygin is interested in the mechanism that Grice calls 'exploitation'.
Also, Saygin is considered the more basic 'violation'.
How is a maxim violated?
In cooperative conversation between rational agents, a maxim is violated, when 'exploited'. The justification is the triggering of an 'implicature'.
Thus, if we use 'if', we may still stick to a truth-functional account of 'if' as the horse-shoe of the logician and argue that the 'implicature' of inferrability (that Strawson was interested in, and that he saw in the natural counterpart of the horseshoe) can be understood as an INTENTIONAL violation (or exploitation) of these desiderata, principles, and maxims of conversation.
Thus Grice can defend a truth-functional account of the connectives, and state that Strawson is making in mistake in ignoring the conversational factors that play into this alleged divergence between natural-language 'if' and the horseshoe.
Saygin generalizes the idea of a 'maxim violation', and seems to place the phenomenon as a mark of rationality: when the violation is perceived as intentional by the co-conversationalist, for the purpose of generating an implicature, it is justified.
Grice is tricky here. He seems to be saying that a maxim may be 'violated' (exploited) at the level of what is EXPLICITLY communicated (or said), but NOT at the level of what is IMPLICATED.
He may also say that while the maxim is violated intentionally (exploited), the overarching cooperative principle IS NOT.
The idea of having a general principle and more specific maxims is of course Kantian in spirit. But Kant is never too clear as to what his maxims are, and Grice will pick up the issue in his more technical seminars on Kant's ethical theory at Berkeley.
I don't think THIS Kantian side to Grice interests Saygin -- but the underlying point that Saygin, Grice, and Kant -- and why not Turing? -- may share pertains to to how this 'illustrates' how 'rationality' works in conversation.
Ayse Pinar Saygin, Herbert Paul Grice, Alan Mathison Turing -- The Implicature Game
Speranza
This looks like a good link.
TURING TEST AND CONVERSATION Ayse Pinar Saygin
www.cs.bilkent.edu.tr/~sekreter/.../July7-1999.htm...
Traduci questa pagina
Hai visitato questa pagina in data 29/01/15
Turing and Grice in context: "Hello, world!"
Speranza
In commentary elsewhere (THIS CLUB -- post on Turing and Grice on rationality -- quoting Saygin), R. B. Jones writes:
"As to Turing's work it might be useful to add that his work leading to the Universal Turing Machine was his way of solving Hilbert's Entscheidungsproblem (decision problem) which he did by exhibiting a problem which is algorithmically unsolvable. The notion of algorithm was made precise for this purpose by the machines we now call Turing machines. The Universal Turing machine (which corresponds to a programmable computer with unbounded memory) was part of the description of the problem which Turing showed to be algorithmically UNsolvable, the halting problem. Turing showed that if a Turing machine could tell whether any other Turing machine halted, then so could one which would halt only if supplied with a description of a machine which did not halt, and a contradiction could be derived by considering what that machine would do when supplied (on its tape) a description of itself. This paper was published in 1946, and made Turing's name as a logician, placing in the same ballpark as Goedel in stature as a logician. Of course Turing had broader interests than Goedel, and like his contemporary Von Neumann was very interested in the development of computing machinery, for which and for his ideas about AI he is now more widely known. Turing and Von Neumann are both in some respects similar to Leibniz."
Thanks. I see that Wikipedia has an entry on 'the halting problem', which I append below.
Cheers.
In computability theory, the halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running or continue to run forever.
Alan Turing proved in 1936 that a general algorithm to solve the halting problem for all possible program-input pairs cannot exist.
A key part of the proof was a mathematical definition of a computer and program, which became known as a Turing machine; the halting problem is undecidable over Turing machines.
It is one of the first examples of a decision problem.
Jack Copeland attributes the term "halting problem" to Martin Davis.
The halting problem is a decision problem about properties of computer programs on a fixed Turing-complete model of computation, i.e. all programs that can be written in some given programming language that is general enough to be equivalent to a Turing machine.
The problem is to determine, given a program and an input to the program, whether the program will eventually halt when run with that input. In this abstract framework, there are no resource limitations on the amount of memory or time required for the program's execution; it can take arbitrarily long, and use arbitrarily much storage space, before halting. The question is simply whether the given program will ever halt on a particular input.
For example, in pseudocode, the program:
while (true) continue
does not halt; rather, it goes on forever in an infinite loop. On the other hand, the program
print "Hello, world!"
does halt.
While deciding whether these programs halt is simple, more complex programs prove problematic.
One approach to the problem might be to run the program for some number of steps and check if it halts. But if the program does not halt, it is unknown whether the program will eventually halt or run forever.
Turing proved no algorithm can exist which will always correctly decide whether, for a given arbitrary program and its input, the program halts when run with that input; the essence of Turing's proof is that any such algorithm can be made to contradict itself, and therefore cannot be correct.
Importance and consequences[edit]
The halting problem is historically important because it was one of the first problems to be proved undecidable. (Turing's proof went to press in May 1936, whereas Alonzo Church's proof of the undecidability of a problem in the lambda calculus had already been published in April 1936.) Subsequently, many other undecidable problems have been described; the typical method of proving a problem to be undecidable is with the technique of reduction. To do this, it is sufficient to show that if a solution to the new problem were found, it could be used to decide an undecidable problem by transforming instances of the undecidable problem into instances of the new problem. Since we already know that no method can decide the old problem, no method can decide the new problem either. Often the new problem is reduced to solving the halting problem. (Note: the same technique is used to demonstrate that a problem is NP complete, only in this case, rather than demonstrating that there is no solution, it demonstrates there is no polynomial time solution, assuming P ≠ NP).
For example, one such consequence of the halting problem's undecidability is that there cannot be a general algorithm that decides whether a given statement about natural numbers is true or not. The reason for this is that the proposition stating that a certain program will halt given a certain input can be converted into an equivalent statement about natural numbers. If we had an algorithm that could solve every statement about natural numbers, it could certainly solve this one; but that would determine whether the original program halts, which is impossible, since the halting problem is undecidable.
Rice's theorem generalizes the theorem that the halting problem is unsolvable.
It states that for any non-trivial property, there is no general decision procedure that, for all programs, decides whether the partial function implemented by the input program has that property. (A partial function is a function which may not always produce a result, and so is used to model programs, which can either produce results or fail to halt.) For example, the property "halt for the input 0" is undecidable. Here, "non-trivial" means that the set of partial functions that satisfy the property is neither the empty set nor the set of all partial functions. For example, "halts or fails to halt on input 0" is clearly true of all partial functions, so it is a trivial property, and can be decided by an algorithm that simply reports "true." Also, note that this theorem holds only for properties of the partial function implemented by the program; Rice's Theorem does not apply to properties of the program itself. For example, "halt on input 0 within 100 steps" is not a property of the partial function that is implemented by the program—it is a property of the program implementing the partial function and is very much decidable.
Gregory Chaitin has defined a halting probability, represented by the symbol Ω, a type of real number that informally is said to represent the probability that a randomly produced program halts. These numbers have the same Turing degree as the halting problem. It is a normal and transcendental number which can be defined but cannot be completely computed. This means one can prove that there is no algorithm which produces the digits of Ω, although its first few digits can be calculated in simple cases.
While Turing's proof shows that there can be no general method or algorithm to determine whether algorithms halt, individual instances of that problem may very well be susceptible to attack.
Given a specific algorithm, one can often show that it must halt for any input, and in fact computer scientists often do just that as part of a correctness proof. But each proof has to be developed specifically for the algorithm at hand; there is no mechanical, general way to determine whether algorithms on a Turing machine halt. However, there are some heuristics that can be used in an automated fashion to attempt to construct a proof, which succeed frequently on typical programs. This field of research is known as automated termination analysis.
Since the negative answer to the halting problem shows that there are problems that cannot be solved by a Turing machine, the Church–Turing thesis limits what can be accomplished by any machine that implements effective methods. However, not all machines conceivable to human imagination are subject to the Church–Turing thesis (e.g. oracle machines). It is an open question whether there can be actual deterministic physical processes that, in the long run, elude simulation by a Turing machine, and in particular whether any such hypothetical process could usefully be harnessed in the form of a calculating machine (a hypercomputer) that could solve the halting problem for a Turing machine amongst other things. It is also an open question whether any such unknown physical processes are involved in the working of the human brain, and whether humans can solve the halting problem (Copeland 2004, p. 15).
The conventional representation of decision problems is the set of objects possessing the property in question.
The halting set
K := { (i, x) | program i halts when run on input x}
represents the halting problem.
This set is recursively enumerable, which means there is a computable function that lists all of the pairs (i, x) it contains.[2] However, the complement of this set is not recursively enumerable.[2]
There are many equivalent formulations of the halting problem; any set whose Turing degree equals that of the halting problem is such a formulation. Examples of such sets include:
{ i | program i eventually halts when run with input 0 }
{ i | there is an input x such that program i eventually halts when run with input x }.
The proof shows there is no total computable function that decides whether an arbitrary program i halts on arbitrary input x; that is, the following function h is not computable (Penrose 1990, p. 57–63):
Here program i refers to the i th program in an enumeration of all the programs of a fixed Turing-complete model of computation.
f(i,j)i
123456
j1100101
2000100
3010101
4100100
5000111
6110010
f(i,i)100110
g(i)U00UU0
Possible values for a total computable function f arranged in a 2D array. The orange cells are the diagonal. The values of f(i,i) and g(i) are shown at the bottom; U indicates that the function g is undefined for a particular input value.The proof proceeds by directly establishing that every total computable function with two arguments differs from the required function h. To this end, given any total computable binary function f, the following partial function g is also computable by some program e:
The verification that g is computable relies on the following constructs (or their equivalents):
computable subprograms (the program that computes f is a subprogram in program e),
duplication of values (program e computes the inputs i,i for f from the input i for g),
conditional branching (program e selects between two results depending on the value it computes for f(i,i)),
not producing a defined result (for example, by looping forever),
returning a value of 0.
The following pseudocode illustrates a straightforward way to compute g:
procedure compute_g(i):
if f(i,i) == 0 then
return 0
else
loop forever
Because g is partial computable, there must be a program e that computes g, by the assumption that the model of computation is Turing-complete. This program is one of all the programs on which the halting function h is defined. The next step of the proof shows that h(e,e) will not have the same value as f(e,e).
It follows from the definition of g that exactly one of the following two cases must hold:
f(e,e) = 0 and so g(e) = 0. In this case h(e,e) = 1, because program e halts on input e.
f(e,e) ≠ 0 and so g(e) is undefined. In this case h(e,e) = 0, because program e does not halt on input e.
In either case, f cannot be the same function as h. Because f was an arbitrary total computable function with two arguments, all such functions must differ from h.
This proof is analogous to Cantor's diagonal argument. One may visualize a two-dimensional array with one column and one row for each natural number, as indicated in the table above. The value of f(i,j) is placed at column i, row j. Because f is assumed to be a total computable function, any element of the array can be calculated using f. The construction of the function g can be visualized using the main diagonal of this array. If the array has a 0 at position (i,i), then g(i) is 0. Otherwise, g(i) is undefined. The contradiction comes from the fact that there is some column e of the array corresponding to g itself. Now assume f was the halting function h, if g(e) is defined ( g(e) = 0 in this case ), g(e) halts so f(e,e) = 1. But g(e) = 0 only when f(e,e) = 0, contradicting f(e,e) = 1. Similarly, if g(e) is not defined, then halting function f(e,e) = 0, which leads to g(e) = 0 under g's construction. This contradicts the assumption that g(e) not being defined. In both cases contradiction arises. Therefore any arbitrary function f cannot be halting function h.
The undecidability of the halting problem also follows from the fact that Kolmogorov complexity is not computable. If the halting problem were decidable, it would be possible to construct a program that generated programs of increasing length, running those that halt and comparing their final outputs with a string parameter until one matched (which must happen eventually, as any string can be generated by a program that contains it as data and just lists it); the length of the matching generated program would then be the Kolmogorov complexity of the parameter, as the terminating generated program must be the shortest (or shortest equal) such program.[3]
The difficulty in the halting problem lies in the requirement that the decision procedure must work for all programs and inputs. A particular program either halts on a given input or does not halt. Consider one algorithm that always answers "halts" and another that always answers "doesn't halt". For any specific program and input, one of these two algorithms answers correctly, even though nobody may know which one.
There are programs (interpreters) that simulate the execution of whatever source code they are given. Such programs can demonstrate that a program does halt if this is the case: the interpreter itself will eventually halt its simulation, which shows that the original program halted. However, an interpreter will not halt if its input program does not halt, so this approach cannot solve the halting problem as stated. It does not successfully answer "doesn't halt" for programs that do not halt.
The halting problem is theoretically decidable for linear bounded automata (LBAs) or deterministic machines with finite memory. A machine with finite memory has a finite number of states, and thus any deterministic program on it must eventually either halt or repeat a previous state:
...any finite-state machine, if left completely to itself, will fall eventually into a perfectly periodic repetitive pattern. The duration of this repeating pattern cannot exceed the number of internal states of the machine... (italics in original, Minsky 1967, p. 24)
Minsky warns us, however, that machines such as computers with e.g., a million small parts, each with two states, will have at least 21,000,000 possible states:
This is a 1 followed by about three hundred thousand zeroes ... Even if such a machine were to operate at the frequencies of cosmic rays, the aeons of galactic evolution would be as nothing compared to the time of a journey through such a cycle (Minsky 1967 p. 25):
Minsky exhorts the reader to be suspicious—although a machine may be finite, and finite automata "have a number of theoretical limitations":
...the magnitudes involved should lead one to suspect that theorems and arguments based chiefly on the mere finiteness [of] the state diagram may not carry a great deal of significance. (Minsky p. 25)
It can also be decided automatically whether a nondeterministic machine with finite memory halts on none of, some of, or all of the possible sequences of nondeterministic decisions, by enumerating states after each possible decision.
In his original proof Turing formalized the concept of algorithm by introducing Turing machines.
However, the result is in no way specific to them; it applies equally to any other model of computation that is equivalent in its computational power to Turing machines, such as Markov algorithms, Lambda calculus, Post systems, register machines, or tag systems.
What is important is that the formalization allows a straightforward mapping of algorithms to some data type that the algorithm can operate upon. For example, if the formalism lets algorithms define functions over strings (such as Turing machines) then there should be a mapping of these algorithms to strings, and if the formalism lets algorithms define functions over natural numbers (such as computable functions) then there should be a mapping of algorithms to natural numbers. The mapping to strings is usually the most straightforward, but strings over an alphabet with n characters can also be mapped to numbers by interpreting them as numbers in an n-ary numeral system.
The concepts raised by Gödel's incompleteness theorems are very similar to those raised by the halting problem, and the proofs are quite similar.
In fact, a weaker form of the First Incompleteness Theorem is an easy consequence of the undecidability of the halting problem. This weaker form differs from the standard statement of the incompleteness theorem by asserting that a complete, consistent and sound axiomatization of all statements about natural numbers is unachievable. The "sound" part is the weakening: it means that we require the axiomatic system in question to prove only true statements about natural numbers (it's very important to observe that the statement of the standard form of Gödel's First Incompleteness Theorem is completely unconcerned with the question of truth, and only concerns formal provability).
The weaker form of the theorem can be proven from the undecidability of the halting problem as follows. Assume that we have a consistent and complete axiomatization of all true first-order logic statements about natural numbers. Then we can build an algorithm that enumerates all these statements. This means that there is an algorithm N(n) that, given a natural number n, computes a true first-order logic statement about natural numbers such that, for all the true statements, there is at least one n such that N(n) yields that statement. Now suppose we want to decide if the algorithm with representation a halts on input i. By using Kleene's T predicate, we can express the statement "a halts on input i" as a statement H(a, i) in the language of arithmetic. Since the axiomatization is complete it follows that either there is an n such that N(n) = H(a, i) or there is an n' such that N(n') = ¬ H(a, i). So if we iterate over all n until we either find H(a, i) or its negation, we will always halt. This means that this gives us an algorithm to decide the halting problem. Since we know that there cannot be such an algorithm, it follows that the assumption that there is a consistent and complete axiomatization of all true first-order logic statements about natural numbers must be false.
There are many programs that either return a correct answer to the halting problem or do not return an answer at all. If it were possible to decide whether any given program gives only correct answers, one might hope to collect a large number of such programs and run them in parallel and determine whether any programs halt. Curiously, deciding whether a program is a partial halting solver (PHS) is as hard as the halting problem itself.
Suppose it's possible to decide whether any given program is a partial halting solver. Then there exists a partial halting solver recognizer, PHSR, guaranteed to terminate with an answer. Construct a program H:
input a program P
X := "input Q. if Q = P output 'halts' else loop forever"
run PHSR with X as input
By construction, program H is also guaranteed to terminate with an answer. If PHSR recognizes the constructed program X as a partial halting solver, that means that P, the only input for which X produces a result, halts. If PHSR fails to recognize X, then it must be because P does not halt. Therefore H can decide whether an arbitrary program P halts; it solves the halting problem. Since this is impossible, then the program PHSR could not have existed as supposed. Therefore, it's not possible to decide whether any given program is a partial halting solver.
Further information: History of algorithms
1900: David Hilbert poses his "23 questions" (now known as Hilbert's problems) at the Second International Congress of Mathematicians in Paris. "Of these, the second was that of proving the consistency of the 'Peano axioms' on which, as he had shown, the rigour of mathematics depended". (Hodges p. 83, Davis' commentary in Davis, 1965, p. 108)
1920–1921: Emil Post explores the halting problem for tag systems, regarding it as a candidate for unsolvability. (Absolutely unsolvable problems and relatively undecidable propositions – account of an anticipation, in Davis, 1965, pp. 340–433.) Its unsolvability was not established until much later, by Marvin Minsky (1967).
1928: Hilbert recasts his 'Second Problem' at the Bologna International Congress. (Reid pp. 188–189) Hodges claims he posed three questions: i.e. #1: Was mathematics complete? #2: Was mathematics consistent? #3: Was mathematics decidable? (Hodges p. 91). The third question is known as the Entscheidungsproblem (Decision Problem). (Hodges p. 91, Penrose p. 34)
1930: Kurt Gödel announces a proof as an answer to the first two of Hilbert's 1928 questions [cf Reid p. 198]. "At first he [Hilbert] was only angry and frustrated, but then he began to try to deal constructively with the problem... Gödel himself felt—and expressed the thought in his paper—that his work did not contradict Hilbert's formalistic point of view" (Reid p. 199)
1931: Gödel publishes "On Formally Undecidable Propositions of Principia Mathematica and Related Systems I", (reprinted in Davis, 1965, p. 5ff)
19 April 1935: Alonzo Church publishes "An Unsolvable Problem of Elementary Number Theory", wherein he identifies what it means for a function to be effectively calculable. Such a function will have an algorithm, and "...the fact that the algorithm has terminated becomes effectively known ..." (Davis, 1965, p. 100)
1936: Church publishes the first proof that the Entscheidungsproblem is unsolvable. (A Note on the Entscheidungsproblem, reprinted in Davis, 1965, p. 110.)
7 October 1936: Emil Post's paper "Finite Combinatory Processes. Formulation I" is received. Post adds to his "process" an instruction "(C) Stop". He called such a process "type 1 ... if the process it determines terminates for each specific problem." (Davis, 1965, p. 289ff)
1937: Alan Turing's paper On Computable Numbers With an Application to the Entscheidungsproblem reaches print in January 1937 (reprinted in Davis, 1965, p. 115). Turing's proof departs from calculation by recursive functions and introduces the notion of computation by machine. Stephen Kleene (1952) refers to this as one of the "first examples of decision problems proved unsolvable".
1939: J. Barkley Rosser observes the essential equivalence of "effective method" defined by Gödel, Church, and Turing (Rosser in Davis, 1965, p. 273, "Informal Exposition of Proofs of Gödel's Theorem and Church's Theorem")
1943: In a paper, Stephen Kleene states that "In setting up a complete algorithmic theory, what we do is describe a procedure ... which procedure necessarily terminates and in such manner that from the outcome we can read a definite answer, 'Yes' or 'No,' to the question, 'Is the predicate value true?'."
1952: Kleene (1952) Chapter XIII ("Computable Functions") includes a discussion of the unsolvability of the halting problem for Turing machines and reformulates it in terms of machines that "eventually stop", i.e. halt: "... there is no algorithm for deciding whether any given machine, when started from any given situation, eventually stops." (Kleene (1952) p. 382)
1952: "Martin Davis thinks it likely that he first used the term 'halting problem' in a series of lectures that he gave at the Control Systems Laboratory at the University of Illinois in 1952 (letter from Davis to Copeland, 12 December 2001)." (Footnote 61 in Copeland (2004) pp. 40ff)
Avoiding the halting problem[edit]
In many practical situations, programmers try to avoid infinite loops—they want every subroutine to finish (halt). In particular, in hard real-time computing, programmers attempt to write subroutines that are not only guaranteed to finish (halt), but are guaranteed to finish before the given deadline.
Sometimes these programmers use some general-purpose (Turing-complete) programming language, but attempt to write in a restricted style—such as MISRA C—that makes it easy to prove that the resulting subroutines finish before the given deadline.
Other times these programmers apply the rule of least power—they deliberately use a computer language that is not quite fully Turing-complete, often a language that guarantees that all subroutines are guaranteed to finish, such as Coq.
See also: Busy beaver, Generic-case complexity, Geoffrey K. Pullum, Gödel's incompleteness theorem, Kolmogorov complexity, P versus NP problem, Termination analysis, Worst-case execution time
Notes: In none of his work did Turing use the word "halting" or "termination". Turing's biographer Hodges does not have the word "halting" or words "halting problem" in his index. The earliest known use of the words "halting problem" is in a proof by Davis (1958, p. 70–71):
"Theorem 2.2 There exists a Turing machine whose halting problem is recursively unsolvable.
"A related problem is the printing problem for a simple Turing machine Z with respect to a symbol Si".
Davis adds no attribution for his proof, so one infers that it is original with him. But Davis has pointed out that a statement of the proof exists informally in Kleene (1952, p. 382). Copeland (2004, p 40) states that:
"The halting problem was so named (and it appears, first stated) by Martin Davis [cf Copeland footnote 61]... (It is often said that Turing stated and proved the halting theorem in 'On Computable Numbers', but strictly this is not true)."
^ Jump up to: a b Moore, Cristopher; Mertens, Stephan (2011), The Nature of Computation, Oxford University Press, pp. 236–237, ISBN 9780191620805 .
Jump up ^ Stated without proof in: "Course notes for Data Compression - Kolmogorov complexity", 2005, P.B. Miltersen, p.7.
References:
Alan Turing, On computable numbers, with an application to the Entscheidungsproblem, Proceedings of the London Mathematical Society, Series 2, Volume 42 (1937), pp 230–265, doi:10.1112/plms/s2-42.1.230. — Alan Turing, On Computable Numbers, with an Application to the Entscheidungsproblem. A Correction, Proceedings of the London Mathematical Society, Series 2, Volume 43 (1938), pp 544–546, doi:10.1112/plms/s2-43.6.544 . Free online version of both parts This is the epochal paper where Turing defines Turing machines, formulates the halting problem, and shows that it (as well as the Entscheidungsproblem) is unsolvable.
Sipser, Michael (2006). "Section 4.2: The Halting Problem". Introduction to the Theory of Computation (Second Edition ed.). PWS Publishing. pp. 173–182. ISBN 0-534-94728-X.
c2:HaltingProblem
B. Jack Copeland ed. (2004), The Essential Turing: Seminal Writings in Computing, Logic, Philosophy, Artificial Intelligence, and Artificial Life plus The Secrets of Enigma, Clarendon Press (Oxford University Press), Oxford UK, ISBN 0-19-825079-7.
Davis, Martin (1965). The Undecidable, Basic Papers on Undecidable Propositions, Unsolvable Problems And Computable Functions. New York: Raven Press. . Turing's paper is #3 in this volume. Papers include those by Godel, Church, Rosser, Kleene, and Post.
Davis, Martin (1958). Computability and Unsolvability. New York: McGraw-Hill. .
Alfred North Whitehead and Bertrand Russell, Principia Mathematica to *56, Cambridge at the University Press, 1962. Re: the problem of paradoxes, the authors discuss the problem of a set not be an object in any of its "determining functions", in particular "Introduction, Chap. 1 p. 24 "...difficulties which arise in formal logic", and Chap. 2.I. "The Vicious-Circle Principle" p. 37ff, and Chap. 2.VIII. "The Contradictions" p. 60ff.
Martin Davis, "What is a computation", in Mathematics Today, Lynn Arthur Steen, Vintage Books (Random House), 1980. A wonderful little paper, perhaps the best ever written about Turing Machines for the non-specialist. Davis reduces the Turing Machine to a far-simpler model based on Post's model of a computation. Discusses Chaitin proof. Includes little biographies of Emil Post, Julia Robinson.
Marvin Minsky, Computation, Finite and Infinite Machines, Prentice-Hall, Inc., N.J., 1967. See chapter 8, Section 8.2 "The Unsolvability of the Halting Problem." Excellent, i.e. readable, sometimes fun. A classic.
Roger Penrose, The Emperor's New Mind: Concerning computers, Minds and the Laws of Physics, Oxford University Press, Oxford England, 1990 (with corrections). Cf: Chapter 2, "Algorithms and Turing Machines". An over-complicated presentation (see Davis's paper for a better model), but a thorough presentation of Turing machines and the halting problem, and Church's Lambda Calculus.
John Hopcroft and Jeffrey Ullman, Introduction to Automata Theory, Languages and Computation, Addison-Wesley, Reading Mass, 1979. See Chapter 7 "Turing Machines." A book centered around the machine-interpretation of "languages", NP-Completeness, etc.
Andrew Hodges, Alan Turing: The Enigma, Simon and Schuster, New York. Cf Chapter "The Spirit of Truth" for a history leading to, and a discussion of, his proof.
Constance Reid, Hilbert, Copernicus: Springer-Verlag, New York, 1996 (first published 1970). Fascinating history of German mathematics and physics from 1880s through 1930s. Hundreds of names familiar to mathematicians, physicists and engineers appear in its pages. Perhaps marred by no overt references and few footnotes: Reid states her sources were numerous interviews with those who personally knew Hilbert, and Hilbert's letters and papers.
Edward Beltrami, What is Random? Chance and order in mathematics and life, Copernicus: Springer-Verlag, New York, 1999. Nice, gentle read for the mathematically inclined non-specialist, puts tougher stuff at the end. Has a Turing-machine model in it. Discusses the Chaitin contributions.
Ernest Nagel and James R. Newman, Godel’s Proof, New York University Press, 1958. Wonderful writing about a very difficult subject. For the mathematically inclined non-specialist. Discusses Gentzen's proof on pages 96–97 and footnotes. Appendices discuss the Peano Axioms briefly, gently introduce readers to formal logic.
Taylor Booth, Sequential Machines and Automata Theory, Wiley, New York, 1967. Cf Chapter 9, Turing Machines. Difficult book, meant for electrical engineers and technical specialists. Discusses recursion, partial-recursion with reference to Turing Machines, halting problem. Has a Turing Machine model in it. References at end of Chapter 9 catch most of the older books (i.e. 1952 until 1967 including authors Martin Davis, F. C. Hennie, H. Hermes, S. C. Kleene, M. Minsky, T. Rado) and various technical papers. See note under Busy-Beaver Programs.
Busy Beaver Programs are described in Scientific American, August 1984, also March 1985 p. 23. A reference in Booth attributes them to Rado, T.(1962), On non-computable functions, Bell Systems Tech. J. 41. Booth also defines Rado's Busy Beaver Problem in problems 3, 4, 5, 6 of Chapter 9, p. 396.
David Bolter, Turing’s Man: Western Culture in the Computer Age, The University of North Carolina Press, Chapel Hill, 1984. For the general reader. May be dated. Has yet another (very simple) Turing Machine model in it.
Stephen Kleene, Introduction to Metamathematics, North-Holland, 1952. Chapter XIII ("Computable Functions") includes a discussion of the unsolvability of the halting problem for Turing machines. In a departure from Turing's terminology of circle-free nonhalting machines, Kleene refers instead to machines that "stop", i.e. halt.
Logical Limitations to Machine Ethics, with Consequences to Lethal Autonomous Weapons - paper discussed in: Does the Halting Problem Mean No Moral Robots?
External links[edit]
Scooping the loop snooper - a poetic proof of undecidability of the halting problem
animated movie - an animation explaining the proof of the undecidability of the halting problem
A 2-Minute Proof of the 2nd-Most Important Theorem of the 2nd Millennium - a proof in only 13 lines
Categories: Theory of computation, Computability theory, Mathematical problems.
In commentary elsewhere (THIS CLUB -- post on Turing and Grice on rationality -- quoting Saygin), R. B. Jones writes:
"As to Turing's work it might be useful to add that his work leading to the Universal Turing Machine was his way of solving Hilbert's Entscheidungsproblem (decision problem) which he did by exhibiting a problem which is algorithmically unsolvable. The notion of algorithm was made precise for this purpose by the machines we now call Turing machines. The Universal Turing machine (which corresponds to a programmable computer with unbounded memory) was part of the description of the problem which Turing showed to be algorithmically UNsolvable, the halting problem. Turing showed that if a Turing machine could tell whether any other Turing machine halted, then so could one which would halt only if supplied with a description of a machine which did not halt, and a contradiction could be derived by considering what that machine would do when supplied (on its tape) a description of itself. This paper was published in 1946, and made Turing's name as a logician, placing in the same ballpark as Goedel in stature as a logician. Of course Turing had broader interests than Goedel, and like his contemporary Von Neumann was very interested in the development of computing machinery, for which and for his ideas about AI he is now more widely known. Turing and Von Neumann are both in some respects similar to Leibniz."
Thanks. I see that Wikipedia has an entry on 'the halting problem', which I append below.
Cheers.
In computability theory, the halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running or continue to run forever.
Alan Turing proved in 1936 that a general algorithm to solve the halting problem for all possible program-input pairs cannot exist.
A key part of the proof was a mathematical definition of a computer and program, which became known as a Turing machine; the halting problem is undecidable over Turing machines.
It is one of the first examples of a decision problem.
Jack Copeland attributes the term "halting problem" to Martin Davis.
The halting problem is a decision problem about properties of computer programs on a fixed Turing-complete model of computation, i.e. all programs that can be written in some given programming language that is general enough to be equivalent to a Turing machine.
The problem is to determine, given a program and an input to the program, whether the program will eventually halt when run with that input. In this abstract framework, there are no resource limitations on the amount of memory or time required for the program's execution; it can take arbitrarily long, and use arbitrarily much storage space, before halting. The question is simply whether the given program will ever halt on a particular input.
For example, in pseudocode, the program:
while (true) continue
does not halt; rather, it goes on forever in an infinite loop. On the other hand, the program
print "Hello, world!"
does halt.
While deciding whether these programs halt is simple, more complex programs prove problematic.
One approach to the problem might be to run the program for some number of steps and check if it halts. But if the program does not halt, it is unknown whether the program will eventually halt or run forever.
Turing proved no algorithm can exist which will always correctly decide whether, for a given arbitrary program and its input, the program halts when run with that input; the essence of Turing's proof is that any such algorithm can be made to contradict itself, and therefore cannot be correct.
Importance and consequences[edit]
The halting problem is historically important because it was one of the first problems to be proved undecidable. (Turing's proof went to press in May 1936, whereas Alonzo Church's proof of the undecidability of a problem in the lambda calculus had already been published in April 1936.) Subsequently, many other undecidable problems have been described; the typical method of proving a problem to be undecidable is with the technique of reduction. To do this, it is sufficient to show that if a solution to the new problem were found, it could be used to decide an undecidable problem by transforming instances of the undecidable problem into instances of the new problem. Since we already know that no method can decide the old problem, no method can decide the new problem either. Often the new problem is reduced to solving the halting problem. (Note: the same technique is used to demonstrate that a problem is NP complete, only in this case, rather than demonstrating that there is no solution, it demonstrates there is no polynomial time solution, assuming P ≠ NP).
For example, one such consequence of the halting problem's undecidability is that there cannot be a general algorithm that decides whether a given statement about natural numbers is true or not. The reason for this is that the proposition stating that a certain program will halt given a certain input can be converted into an equivalent statement about natural numbers. If we had an algorithm that could solve every statement about natural numbers, it could certainly solve this one; but that would determine whether the original program halts, which is impossible, since the halting problem is undecidable.
Rice's theorem generalizes the theorem that the halting problem is unsolvable.
It states that for any non-trivial property, there is no general decision procedure that, for all programs, decides whether the partial function implemented by the input program has that property. (A partial function is a function which may not always produce a result, and so is used to model programs, which can either produce results or fail to halt.) For example, the property "halt for the input 0" is undecidable. Here, "non-trivial" means that the set of partial functions that satisfy the property is neither the empty set nor the set of all partial functions. For example, "halts or fails to halt on input 0" is clearly true of all partial functions, so it is a trivial property, and can be decided by an algorithm that simply reports "true." Also, note that this theorem holds only for properties of the partial function implemented by the program; Rice's Theorem does not apply to properties of the program itself. For example, "halt on input 0 within 100 steps" is not a property of the partial function that is implemented by the program—it is a property of the program implementing the partial function and is very much decidable.
Gregory Chaitin has defined a halting probability, represented by the symbol Ω, a type of real number that informally is said to represent the probability that a randomly produced program halts. These numbers have the same Turing degree as the halting problem. It is a normal and transcendental number which can be defined but cannot be completely computed. This means one can prove that there is no algorithm which produces the digits of Ω, although its first few digits can be calculated in simple cases.
While Turing's proof shows that there can be no general method or algorithm to determine whether algorithms halt, individual instances of that problem may very well be susceptible to attack.
Given a specific algorithm, one can often show that it must halt for any input, and in fact computer scientists often do just that as part of a correctness proof. But each proof has to be developed specifically for the algorithm at hand; there is no mechanical, general way to determine whether algorithms on a Turing machine halt. However, there are some heuristics that can be used in an automated fashion to attempt to construct a proof, which succeed frequently on typical programs. This field of research is known as automated termination analysis.
Since the negative answer to the halting problem shows that there are problems that cannot be solved by a Turing machine, the Church–Turing thesis limits what can be accomplished by any machine that implements effective methods. However, not all machines conceivable to human imagination are subject to the Church–Turing thesis (e.g. oracle machines). It is an open question whether there can be actual deterministic physical processes that, in the long run, elude simulation by a Turing machine, and in particular whether any such hypothetical process could usefully be harnessed in the form of a calculating machine (a hypercomputer) that could solve the halting problem for a Turing machine amongst other things. It is also an open question whether any such unknown physical processes are involved in the working of the human brain, and whether humans can solve the halting problem (Copeland 2004, p. 15).
The conventional representation of decision problems is the set of objects possessing the property in question.
The halting set
K := { (i, x) | program i halts when run on input x}
represents the halting problem.
This set is recursively enumerable, which means there is a computable function that lists all of the pairs (i, x) it contains.[2] However, the complement of this set is not recursively enumerable.[2]
There are many equivalent formulations of the halting problem; any set whose Turing degree equals that of the halting problem is such a formulation. Examples of such sets include:
{ i | program i eventually halts when run with input 0 }
{ i | there is an input x such that program i eventually halts when run with input x }.
The proof shows there is no total computable function that decides whether an arbitrary program i halts on arbitrary input x; that is, the following function h is not computable (Penrose 1990, p. 57–63):
Here program i refers to the i th program in an enumeration of all the programs of a fixed Turing-complete model of computation.
f(i,j)i
123456
j1100101
2000100
3010101
4100100
5000111
6110010
f(i,i)100110
g(i)U00UU0
Possible values for a total computable function f arranged in a 2D array. The orange cells are the diagonal. The values of f(i,i) and g(i) are shown at the bottom; U indicates that the function g is undefined for a particular input value.The proof proceeds by directly establishing that every total computable function with two arguments differs from the required function h. To this end, given any total computable binary function f, the following partial function g is also computable by some program e:
The verification that g is computable relies on the following constructs (or their equivalents):
computable subprograms (the program that computes f is a subprogram in program e),
duplication of values (program e computes the inputs i,i for f from the input i for g),
conditional branching (program e selects between two results depending on the value it computes for f(i,i)),
not producing a defined result (for example, by looping forever),
returning a value of 0.
The following pseudocode illustrates a straightforward way to compute g:
procedure compute_g(i):
if f(i,i) == 0 then
return 0
else
loop forever
Because g is partial computable, there must be a program e that computes g, by the assumption that the model of computation is Turing-complete. This program is one of all the programs on which the halting function h is defined. The next step of the proof shows that h(e,e) will not have the same value as f(e,e).
It follows from the definition of g that exactly one of the following two cases must hold:
f(e,e) = 0 and so g(e) = 0. In this case h(e,e) = 1, because program e halts on input e.
f(e,e) ≠ 0 and so g(e) is undefined. In this case h(e,e) = 0, because program e does not halt on input e.
In either case, f cannot be the same function as h. Because f was an arbitrary total computable function with two arguments, all such functions must differ from h.
This proof is analogous to Cantor's diagonal argument. One may visualize a two-dimensional array with one column and one row for each natural number, as indicated in the table above. The value of f(i,j) is placed at column i, row j. Because f is assumed to be a total computable function, any element of the array can be calculated using f. The construction of the function g can be visualized using the main diagonal of this array. If the array has a 0 at position (i,i), then g(i) is 0. Otherwise, g(i) is undefined. The contradiction comes from the fact that there is some column e of the array corresponding to g itself. Now assume f was the halting function h, if g(e) is defined ( g(e) = 0 in this case ), g(e) halts so f(e,e) = 1. But g(e) = 0 only when f(e,e) = 0, contradicting f(e,e) = 1. Similarly, if g(e) is not defined, then halting function f(e,e) = 0, which leads to g(e) = 0 under g's construction. This contradicts the assumption that g(e) not being defined. In both cases contradiction arises. Therefore any arbitrary function f cannot be halting function h.
The undecidability of the halting problem also follows from the fact that Kolmogorov complexity is not computable. If the halting problem were decidable, it would be possible to construct a program that generated programs of increasing length, running those that halt and comparing their final outputs with a string parameter until one matched (which must happen eventually, as any string can be generated by a program that contains it as data and just lists it); the length of the matching generated program would then be the Kolmogorov complexity of the parameter, as the terminating generated program must be the shortest (or shortest equal) such program.[3]
The difficulty in the halting problem lies in the requirement that the decision procedure must work for all programs and inputs. A particular program either halts on a given input or does not halt. Consider one algorithm that always answers "halts" and another that always answers "doesn't halt". For any specific program and input, one of these two algorithms answers correctly, even though nobody may know which one.
There are programs (interpreters) that simulate the execution of whatever source code they are given. Such programs can demonstrate that a program does halt if this is the case: the interpreter itself will eventually halt its simulation, which shows that the original program halted. However, an interpreter will not halt if its input program does not halt, so this approach cannot solve the halting problem as stated. It does not successfully answer "doesn't halt" for programs that do not halt.
The halting problem is theoretically decidable for linear bounded automata (LBAs) or deterministic machines with finite memory. A machine with finite memory has a finite number of states, and thus any deterministic program on it must eventually either halt or repeat a previous state:
...any finite-state machine, if left completely to itself, will fall eventually into a perfectly periodic repetitive pattern. The duration of this repeating pattern cannot exceed the number of internal states of the machine... (italics in original, Minsky 1967, p. 24)
Minsky warns us, however, that machines such as computers with e.g., a million small parts, each with two states, will have at least 21,000,000 possible states:
This is a 1 followed by about three hundred thousand zeroes ... Even if such a machine were to operate at the frequencies of cosmic rays, the aeons of galactic evolution would be as nothing compared to the time of a journey through such a cycle (Minsky 1967 p. 25):
Minsky exhorts the reader to be suspicious—although a machine may be finite, and finite automata "have a number of theoretical limitations":
...the magnitudes involved should lead one to suspect that theorems and arguments based chiefly on the mere finiteness [of] the state diagram may not carry a great deal of significance. (Minsky p. 25)
It can also be decided automatically whether a nondeterministic machine with finite memory halts on none of, some of, or all of the possible sequences of nondeterministic decisions, by enumerating states after each possible decision.
In his original proof Turing formalized the concept of algorithm by introducing Turing machines.
However, the result is in no way specific to them; it applies equally to any other model of computation that is equivalent in its computational power to Turing machines, such as Markov algorithms, Lambda calculus, Post systems, register machines, or tag systems.
What is important is that the formalization allows a straightforward mapping of algorithms to some data type that the algorithm can operate upon. For example, if the formalism lets algorithms define functions over strings (such as Turing machines) then there should be a mapping of these algorithms to strings, and if the formalism lets algorithms define functions over natural numbers (such as computable functions) then there should be a mapping of algorithms to natural numbers. The mapping to strings is usually the most straightforward, but strings over an alphabet with n characters can also be mapped to numbers by interpreting them as numbers in an n-ary numeral system.
The concepts raised by Gödel's incompleteness theorems are very similar to those raised by the halting problem, and the proofs are quite similar.
In fact, a weaker form of the First Incompleteness Theorem is an easy consequence of the undecidability of the halting problem. This weaker form differs from the standard statement of the incompleteness theorem by asserting that a complete, consistent and sound axiomatization of all statements about natural numbers is unachievable. The "sound" part is the weakening: it means that we require the axiomatic system in question to prove only true statements about natural numbers (it's very important to observe that the statement of the standard form of Gödel's First Incompleteness Theorem is completely unconcerned with the question of truth, and only concerns formal provability).
The weaker form of the theorem can be proven from the undecidability of the halting problem as follows. Assume that we have a consistent and complete axiomatization of all true first-order logic statements about natural numbers. Then we can build an algorithm that enumerates all these statements. This means that there is an algorithm N(n) that, given a natural number n, computes a true first-order logic statement about natural numbers such that, for all the true statements, there is at least one n such that N(n) yields that statement. Now suppose we want to decide if the algorithm with representation a halts on input i. By using Kleene's T predicate, we can express the statement "a halts on input i" as a statement H(a, i) in the language of arithmetic. Since the axiomatization is complete it follows that either there is an n such that N(n) = H(a, i) or there is an n' such that N(n') = ¬ H(a, i). So if we iterate over all n until we either find H(a, i) or its negation, we will always halt. This means that this gives us an algorithm to decide the halting problem. Since we know that there cannot be such an algorithm, it follows that the assumption that there is a consistent and complete axiomatization of all true first-order logic statements about natural numbers must be false.
There are many programs that either return a correct answer to the halting problem or do not return an answer at all. If it were possible to decide whether any given program gives only correct answers, one might hope to collect a large number of such programs and run them in parallel and determine whether any programs halt. Curiously, deciding whether a program is a partial halting solver (PHS) is as hard as the halting problem itself.
Suppose it's possible to decide whether any given program is a partial halting solver. Then there exists a partial halting solver recognizer, PHSR, guaranteed to terminate with an answer. Construct a program H:
input a program P
X := "input Q. if Q = P output 'halts' else loop forever"
run PHSR with X as input
By construction, program H is also guaranteed to terminate with an answer. If PHSR recognizes the constructed program X as a partial halting solver, that means that P, the only input for which X produces a result, halts. If PHSR fails to recognize X, then it must be because P does not halt. Therefore H can decide whether an arbitrary program P halts; it solves the halting problem. Since this is impossible, then the program PHSR could not have existed as supposed. Therefore, it's not possible to decide whether any given program is a partial halting solver.
Further information: History of algorithms
1900: David Hilbert poses his "23 questions" (now known as Hilbert's problems) at the Second International Congress of Mathematicians in Paris. "Of these, the second was that of proving the consistency of the 'Peano axioms' on which, as he had shown, the rigour of mathematics depended". (Hodges p. 83, Davis' commentary in Davis, 1965, p. 108)
1920–1921: Emil Post explores the halting problem for tag systems, regarding it as a candidate for unsolvability. (Absolutely unsolvable problems and relatively undecidable propositions – account of an anticipation, in Davis, 1965, pp. 340–433.) Its unsolvability was not established until much later, by Marvin Minsky (1967).
1928: Hilbert recasts his 'Second Problem' at the Bologna International Congress. (Reid pp. 188–189) Hodges claims he posed three questions: i.e. #1: Was mathematics complete? #2: Was mathematics consistent? #3: Was mathematics decidable? (Hodges p. 91). The third question is known as the Entscheidungsproblem (Decision Problem). (Hodges p. 91, Penrose p. 34)
1930: Kurt Gödel announces a proof as an answer to the first two of Hilbert's 1928 questions [cf Reid p. 198]. "At first he [Hilbert] was only angry and frustrated, but then he began to try to deal constructively with the problem... Gödel himself felt—and expressed the thought in his paper—that his work did not contradict Hilbert's formalistic point of view" (Reid p. 199)
1931: Gödel publishes "On Formally Undecidable Propositions of Principia Mathematica and Related Systems I", (reprinted in Davis, 1965, p. 5ff)
19 April 1935: Alonzo Church publishes "An Unsolvable Problem of Elementary Number Theory", wherein he identifies what it means for a function to be effectively calculable. Such a function will have an algorithm, and "...the fact that the algorithm has terminated becomes effectively known ..." (Davis, 1965, p. 100)
1936: Church publishes the first proof that the Entscheidungsproblem is unsolvable. (A Note on the Entscheidungsproblem, reprinted in Davis, 1965, p. 110.)
7 October 1936: Emil Post's paper "Finite Combinatory Processes. Formulation I" is received. Post adds to his "process" an instruction "(C) Stop". He called such a process "type 1 ... if the process it determines terminates for each specific problem." (Davis, 1965, p. 289ff)
1937: Alan Turing's paper On Computable Numbers With an Application to the Entscheidungsproblem reaches print in January 1937 (reprinted in Davis, 1965, p. 115). Turing's proof departs from calculation by recursive functions and introduces the notion of computation by machine. Stephen Kleene (1952) refers to this as one of the "first examples of decision problems proved unsolvable".
1939: J. Barkley Rosser observes the essential equivalence of "effective method" defined by Gödel, Church, and Turing (Rosser in Davis, 1965, p. 273, "Informal Exposition of Proofs of Gödel's Theorem and Church's Theorem")
1943: In a paper, Stephen Kleene states that "In setting up a complete algorithmic theory, what we do is describe a procedure ... which procedure necessarily terminates and in such manner that from the outcome we can read a definite answer, 'Yes' or 'No,' to the question, 'Is the predicate value true?'."
1952: Kleene (1952) Chapter XIII ("Computable Functions") includes a discussion of the unsolvability of the halting problem for Turing machines and reformulates it in terms of machines that "eventually stop", i.e. halt: "... there is no algorithm for deciding whether any given machine, when started from any given situation, eventually stops." (Kleene (1952) p. 382)
1952: "Martin Davis thinks it likely that he first used the term 'halting problem' in a series of lectures that he gave at the Control Systems Laboratory at the University of Illinois in 1952 (letter from Davis to Copeland, 12 December 2001)." (Footnote 61 in Copeland (2004) pp. 40ff)
Avoiding the halting problem[edit]
In many practical situations, programmers try to avoid infinite loops—they want every subroutine to finish (halt). In particular, in hard real-time computing, programmers attempt to write subroutines that are not only guaranteed to finish (halt), but are guaranteed to finish before the given deadline.
Sometimes these programmers use some general-purpose (Turing-complete) programming language, but attempt to write in a restricted style—such as MISRA C—that makes it easy to prove that the resulting subroutines finish before the given deadline.
Other times these programmers apply the rule of least power—they deliberately use a computer language that is not quite fully Turing-complete, often a language that guarantees that all subroutines are guaranteed to finish, such as Coq.
See also: Busy beaver, Generic-case complexity, Geoffrey K. Pullum, Gödel's incompleteness theorem, Kolmogorov complexity, P versus NP problem, Termination analysis, Worst-case execution time
Notes: In none of his work did Turing use the word "halting" or "termination". Turing's biographer Hodges does not have the word "halting" or words "halting problem" in his index. The earliest known use of the words "halting problem" is in a proof by Davis (1958, p. 70–71):
"Theorem 2.2 There exists a Turing machine whose halting problem is recursively unsolvable.
"A related problem is the printing problem for a simple Turing machine Z with respect to a symbol Si".
Davis adds no attribution for his proof, so one infers that it is original with him. But Davis has pointed out that a statement of the proof exists informally in Kleene (1952, p. 382). Copeland (2004, p 40) states that:
"The halting problem was so named (and it appears, first stated) by Martin Davis [cf Copeland footnote 61]... (It is often said that Turing stated and proved the halting theorem in 'On Computable Numbers', but strictly this is not true)."
^ Jump up to: a b Moore, Cristopher; Mertens, Stephan (2011), The Nature of Computation, Oxford University Press, pp. 236–237, ISBN 9780191620805 .
Jump up ^ Stated without proof in: "Course notes for Data Compression - Kolmogorov complexity", 2005, P.B. Miltersen, p.7.
References:
Alan Turing, On computable numbers, with an application to the Entscheidungsproblem, Proceedings of the London Mathematical Society, Series 2, Volume 42 (1937), pp 230–265, doi:10.1112/plms/s2-42.1.230. — Alan Turing, On Computable Numbers, with an Application to the Entscheidungsproblem. A Correction, Proceedings of the London Mathematical Society, Series 2, Volume 43 (1938), pp 544–546, doi:10.1112/plms/s2-43.6.544 . Free online version of both parts This is the epochal paper where Turing defines Turing machines, formulates the halting problem, and shows that it (as well as the Entscheidungsproblem) is unsolvable.
Sipser, Michael (2006). "Section 4.2: The Halting Problem". Introduction to the Theory of Computation (Second Edition ed.). PWS Publishing. pp. 173–182. ISBN 0-534-94728-X.
c2:HaltingProblem
B. Jack Copeland ed. (2004), The Essential Turing: Seminal Writings in Computing, Logic, Philosophy, Artificial Intelligence, and Artificial Life plus The Secrets of Enigma, Clarendon Press (Oxford University Press), Oxford UK, ISBN 0-19-825079-7.
Davis, Martin (1965). The Undecidable, Basic Papers on Undecidable Propositions, Unsolvable Problems And Computable Functions. New York: Raven Press. . Turing's paper is #3 in this volume. Papers include those by Godel, Church, Rosser, Kleene, and Post.
Davis, Martin (1958). Computability and Unsolvability. New York: McGraw-Hill. .
Alfred North Whitehead and Bertrand Russell, Principia Mathematica to *56, Cambridge at the University Press, 1962. Re: the problem of paradoxes, the authors discuss the problem of a set not be an object in any of its "determining functions", in particular "Introduction, Chap. 1 p. 24 "...difficulties which arise in formal logic", and Chap. 2.I. "The Vicious-Circle Principle" p. 37ff, and Chap. 2.VIII. "The Contradictions" p. 60ff.
Martin Davis, "What is a computation", in Mathematics Today, Lynn Arthur Steen, Vintage Books (Random House), 1980. A wonderful little paper, perhaps the best ever written about Turing Machines for the non-specialist. Davis reduces the Turing Machine to a far-simpler model based on Post's model of a computation. Discusses Chaitin proof. Includes little biographies of Emil Post, Julia Robinson.
Marvin Minsky, Computation, Finite and Infinite Machines, Prentice-Hall, Inc., N.J., 1967. See chapter 8, Section 8.2 "The Unsolvability of the Halting Problem." Excellent, i.e. readable, sometimes fun. A classic.
Roger Penrose, The Emperor's New Mind: Concerning computers, Minds and the Laws of Physics, Oxford University Press, Oxford England, 1990 (with corrections). Cf: Chapter 2, "Algorithms and Turing Machines". An over-complicated presentation (see Davis's paper for a better model), but a thorough presentation of Turing machines and the halting problem, and Church's Lambda Calculus.
John Hopcroft and Jeffrey Ullman, Introduction to Automata Theory, Languages and Computation, Addison-Wesley, Reading Mass, 1979. See Chapter 7 "Turing Machines." A book centered around the machine-interpretation of "languages", NP-Completeness, etc.
Andrew Hodges, Alan Turing: The Enigma, Simon and Schuster, New York. Cf Chapter "The Spirit of Truth" for a history leading to, and a discussion of, his proof.
Constance Reid, Hilbert, Copernicus: Springer-Verlag, New York, 1996 (first published 1970). Fascinating history of German mathematics and physics from 1880s through 1930s. Hundreds of names familiar to mathematicians, physicists and engineers appear in its pages. Perhaps marred by no overt references and few footnotes: Reid states her sources were numerous interviews with those who personally knew Hilbert, and Hilbert's letters and papers.
Edward Beltrami, What is Random? Chance and order in mathematics and life, Copernicus: Springer-Verlag, New York, 1999. Nice, gentle read for the mathematically inclined non-specialist, puts tougher stuff at the end. Has a Turing-machine model in it. Discusses the Chaitin contributions.
Ernest Nagel and James R. Newman, Godel’s Proof, New York University Press, 1958. Wonderful writing about a very difficult subject. For the mathematically inclined non-specialist. Discusses Gentzen's proof on pages 96–97 and footnotes. Appendices discuss the Peano Axioms briefly, gently introduce readers to formal logic.
Taylor Booth, Sequential Machines and Automata Theory, Wiley, New York, 1967. Cf Chapter 9, Turing Machines. Difficult book, meant for electrical engineers and technical specialists. Discusses recursion, partial-recursion with reference to Turing Machines, halting problem. Has a Turing Machine model in it. References at end of Chapter 9 catch most of the older books (i.e. 1952 until 1967 including authors Martin Davis, F. C. Hennie, H. Hermes, S. C. Kleene, M. Minsky, T. Rado) and various technical papers. See note under Busy-Beaver Programs.
Busy Beaver Programs are described in Scientific American, August 1984, also March 1985 p. 23. A reference in Booth attributes them to Rado, T.(1962), On non-computable functions, Bell Systems Tech. J. 41. Booth also defines Rado's Busy Beaver Problem in problems 3, 4, 5, 6 of Chapter 9, p. 396.
David Bolter, Turing’s Man: Western Culture in the Computer Age, The University of North Carolina Press, Chapel Hill, 1984. For the general reader. May be dated. Has yet another (very simple) Turing Machine model in it.
Stephen Kleene, Introduction to Metamathematics, North-Holland, 1952. Chapter XIII ("Computable Functions") includes a discussion of the unsolvability of the halting problem for Turing machines. In a departure from Turing's terminology of circle-free nonhalting machines, Kleene refers instead to machines that "stop", i.e. halt.
Logical Limitations to Machine Ethics, with Consequences to Lethal Autonomous Weapons - paper discussed in: Does the Halting Problem Mean No Moral Robots?
External links[edit]
Scooping the loop snooper - a poetic proof of undecidability of the halting problem
animated movie - an animation explaining the proof of the undecidability of the halting problem
A 2-Minute Proof of the 2nd-Most Important Theorem of the 2nd Millennium - a proof in only 13 lines
Categories: Theory of computation, Computability theory, Mathematical problems.
Subscribe to:
Posts (Atom)
Posts
