I made a diagram of this, based on Sider’s Logic for philosophy. An orange arrow from sytems S to system S’ means anything that is provable (and hence valid) in S is provable (and valid) in S’. I don’t add lables to the orange arrows since their meanings are clear. A green arrow from axiom schema to another says that the second schema is provable from the first in a particular system which I label.

Tripler ses dons

Les dons à des organismes d’intérêt général ouvrent droit à une réduction d’impôt au taux de 66%, dans la limite de 20% du revenu imposable. Cette réduction permet donc de tripler ses dons. En effet, si je souhaite dépenser 1000€ en donnant, je peux donner 3000€, et l’administration fiscale me rembourse 3000 * 0.66=2000€ sous forme de réduction d’impôt. Ce régime fiscal du don est extrêmement généreux: à titre de comparaison, la législation britannique du “Gift Aid” permet d’augmenter ses dons de 25% au lieu de 200% pour la France!

Persche 2009

Depuis l’arrêt Persche 2009, aucun état européen ne peut refuser une déduction fiscale au motif que le bénéficiaire du don n’est pas établi dans cet état. La cour a en effet établi que la déductibilité fiscale de dons transfrontaliers relève de la libre circulation de capitaux garantie par le droit communautaire.

Cependant, la France à pris plusieurs années à mettre en pratique cet arrêt.

L’ancienne déclaration de revenus (jusqu’au millésime 2013)

Dans le formulaire 2042 “Déclaration des revenus 2012”, seule la case “Dons à des organismes établis en France” apparaît. Il n’y a aucun moyen simple de demander la réduction d’impôt pourtant garantie par Persche 2009.

Pourtant, la version en vigueur du 7 mai 2012 au 1 janvier 2014 de l’article 200 du code général des impôts est en accord avec Persche 2009. Le numéro 4 bis indique:

Ouvrent également droit à la réduction d’impôt les dons et versements effectués au profit d’organismes agréés dans les conditions prévues à l’article 1649 nonies dont le siège est situé dans un État membre de l’Union européenne ou dans un autre État partie à l’accord sur l’Espace économique européen ayant conclu avec la France une convention d’assistance administrative en vue de lutter contre la fraude et l’évasion fiscales. L’agrément est accordé lorsque l’organisme poursuit des objectifs et présente des caractéristiques similaires aux organismes dont le siège est situé en France répondant aux conditions fixées par le présent article.

Lorsque les dons et versements ont été effectués au profit d’un organisme non agréé dont le siège est situé dans un État membre de l’Union européenne ou dans un autre État partie à l’accord sur l’Espace économique européen ayant conclu avec la France une convention d’assistance administrative en vue de lutter contre la fraude et l’évasion fiscales, la réduction d’impôt obtenue fait l’objet d’une reprise, sauf lorsque le contribuable a produit dans le délai de dépôt de déclaration les pièces justificatives attestant que cet organisme poursuit des objectifs et présente des caractéristiques similaires aux organismes dont le siège est situé en France répondant aux conditions fixées par le présent article.

La demande d’agrément, régie par l’arrêté NOR EFIE1100179A du 28 février 2011 était une procédure très lourde pour les organismes. Malgré mes tentatives en été 2015, aucune des ONG recommandées par GiveWell ou Giving What We Can n’ont souhaité entamer cette procédure.

Si l’organisme n’est pas agréé, c’est le contribuable qui doit joindre à sa déclaration “les pièces justificatives attestant que cet organisme poursuit des objectifs et présente des caractéristiques similaires aux organismes” Français. Au delà de la discrépance entre le formulaire 2042 et l’article 200, il n’est qui plus est pas spécifié quelles pièces justificatives sont à apporter.

La dispense de justificatifs

A partir du 1er janvier 2014, le contribuable n’a plus à fournir de justificatifs de ses dons. Il a seulement à les produire en cas de contrôle fiscal. L’article 4 bis précise dès la version du 1er Janvier 2014:

Lorsque les dons et versements ont été effectués au profit d’un organisme non agréé dont le siège est situé dans un État membre de l’Union européenne ou dans un autre État partie à l’accord sur l’Espace économique européen ayant conclu avec la France une convention d’assistance administrative en vue de lutter contre la fraude et l’évasion fiscales, la réduction d’impôt obtenue fait l’objet d’une reprise, sauf si le contribuable produit, à la demande de l’administration fiscale, les pièces justificatives attestant que cet organisme poursuit des objectifs et présente des caractéristiques similaires aux organismes dont le siège est situé en France répondant aux conditions fixées par le présent article.

La case 7VC

Par ailleurs, depuis le formulaire 2042 C millésime 2014, il existe une nouvelle case 7VC, relative aux dons versés à des organismes d’intérêt général établis dans un État européen. (Depuis 2017, la case 7VC se trouve désormais dans le formulaire 2042 RICI (au lieu de 2042 C), mais reste autrement inchangée.)

Conclusion

La dispense de justificatifs est un changement sans grande importance pour les dons à des organismes Français, puisque ces justificatifs (reçus fiscaux) sont en général donnés automatiquement par l’organisme. Mais dans le cas d’un organisme européen non agréé, le changement revêt une importance plus grande. La justification attestant que cet organisme est similaire aux organismes français d’intérêt général est en effet non seulement plus onéreuse à fournir, de surcroît ses modalités ne sont pas précisément spécifiées.

C’est donc seulement en rare cas de contrôle fiscal qu’il faudra justifier de cette similitude entre organisme européen et organismes français. En cas de contrôle, je suppose que ce serait à l’administration fiscale de préciser quels documents suffiraient à établir cette similitude. Cela ne devrait pas être difficile puisque les organismes européens plébiscités par l’altruisme efficace sont clairement d’intérêt général. En cas de doute, vous pouvez me contacter pour en discuter.

La création de la case 7VC est par ailleurs rassurante car elle met le formulaire d’impôt en conformité avec l’article 200.

Transnational giving Europe

Il est possible de faire un don à l’Against Malaria Foundation via le réseau Transnational Giving Europe; l’on recoit alors automatiquement un reçu fiscal. Mais les frais s’élèvent à 5% de la somme donnée pour un don de moins de 100 000 euros.

a computing machine is really a logic machine. Its circuits embody the distilled insights of a remarkable collection of logicians, developed over centuries.

— Martin Davis (2000)

This is part of my series on success stories in philosophy. See this page for an explanation of the project and links to other items in the series. I also have a related discussion of conceptual analysis here

Contents

1. The intuitive notion of effective calculability
2. The Church-Turing analysis of computability
3. Computability theory applied
   1. The halting problem
   2. Further applications in mathamtics
   3. The modern computer
4. Epilogue: the long reach of the algorithm

The analysis of computability is one of the few examples in history of a non-trivial conceptual analysis that has consensus support. Some might want to quibble that computer science or mathematics rather than philosophy deserves the credit for it. I’m not interested in which artificial faction of academy should lay claim to the spoils of war. The search for, proposal of, and eventual vindication of a formalisation of an everyday concept is philosophical in method, that is my point. If you wish to conclude from this that computer scientists produce better philosophy than philosophers, so be it.

To us living today, the formal idea of an algorithm is so commonsensical that it can he hard to imagine a worldview lacking this precise concept. Yet less a than a century ago, that was exactly the world people like Turing, Gödel, Russel, Hilbert, and everybody else was living in.

The notion of algorithm, of course, is so general that people have been using them for thousands of years. The use of tally marks to count sheep is a form of algorithm. The sieve of Eratosthenes, an algorithm for finding all prime number up to a given limit, was developed in ancient Greece. The success story is therefore not the development of algorithms, but the understand and formalisation of the concept itself. This improved understanding helped dissolve some confusions.

The intuitive notion of effective calculability

Soare 1996:

In 1642 the French mathematician and scientist, Blaise Pascal, invented an adding machine which may be the first digital calculator.

Wikipedia:

In 1673, Gottfried Leibniz demonstrated a digital mechanical calculator, called the Stepped Reckoner. […] It could:

• add or subtract an 8-digit number to / from a 16-digit number
• multiply two 8-digit numbers to get a 16-digit result
• divide a 16-digit number by an 8-digit divisor

These primitive calculating devices show that people in the 17th century had to have some inuitive notion of “that which can be calculated by a machine” or by a “mindless process” or “without leaps of insight”. They were, at the very least, an existence proof, showing that addition and subtraction could be performed by such a process.

Wikipedia also tells us:

Before the precise definition of computable function, mathematicians often used the informal term effectively calculable to describe functions that are computable by paper-and-pencil methods.

And:

In 1935 Turing and everyone else used the term “computer” for an idealized human calculating with extra material such as pencil and paper, or a desk calculator, a meaning very different from the use of the word today.

The Church-Turing analysis of computability

Stanford has a nice and concise explanation:

In the 1930s, well before there were computers, various mathematicians from around the world invented precise, independent definitions of what it means to be computable. Alonzo Church defined the Lambda calculus, Kurt Gödel defined Recursive functions, Stephen Kleene defined Formal systems, Markov defined what became known as Markov algorithms, Emil Post and Alan Turing defined abstract machines now known as Post machines and Turing machines.

Surprisingly, all of these models are exactly equivalent: anything computable in the lambda calculus is computable by a Turing machine and similarly for any other pairs of the above computational systems. After this was proved, Church expressed the belief that the intuitive notion of “computable in principle” is identical to the above precise notions. This belief, now called the “Church-Turing Thesis”, is uniformly accepted by mathematicians.

Computability theory applied

I take Turing’s (and his contemporaries’) philosophical contribution to be the conceptual analysis of “computable” as “computable by a Turing machine”, i.e. the assertion of the Church-Turing Thesis. As we will often see in this series, once we have a formalism, we can go to town and start proving things left and right about the formal object. What was once a topic of speculation becomes amenable to mathematics. (For much more on this topics, see my other post on why good philosophy often looks like mathematics.) Here are some examples.

The halting problem

Given Pascal’s and Leibnitz’s machines, one might have thought it natural that any function (set $F​$ of ordered pairs such that if $\langle a,b \rangle \in F​$ and $\langle a,c \rangle \in F​$ then $b=c​$ ) which can be precisely specified can be computed in the inuitive sense. But Turing showed that this is not true. For example, the halting problem is not computable; and the Entscheidungsproblem (Turing’s original motivation for developing his formalism) cannot be solved.

Further applications in mathamtics

Here are some lists of examples of non-computable functions:

• An example of an easy to understand undecidable problem — Mathematics StackExchange
• Non-computable but easily described arithmetical functions — MathOverflow
• What are the most attractive Turing undecidable problems in mathematics? — MathOverflow

There is an analogy here, by the way, to the previous success story: many people thought it natural that any continuous function must be differentiable, the discovery of a function that is everywhere continuous and nowhere differentiable seemed problematic, and the formalisation of the concept of continuity solved the problem.

The modern computer

The greatest practical impact of Turing’s discoveries was to lay the conceptual ground for the development of modern computers. (Wikipedia has a good summary of the history of computing.)

In his 1936 paper On Computable Numbers, with an Application to the Entscheidungsproblem, once armed with his new formalism, Turing immediately proves an interesting result: the general notion of “computable by some turing machine” can itself be expressed in terms of Turing machines. In particular, a Universal Turing Machine, is a Turing Machine that can simulate an arbitrary Turing machine on arbitrary input.¹

This was the first proof that there could be a “universal” programmable machine, capable of computing anything that we know how to compute, when given the recipe. Sometimes in history, as in the case of heavier-than-air flying machines, infamously pronounced impossible by Lord Kelvin, the proof is in the pudding. With the computer, the proof preceded the pudding by several decades.

Jack Copeland (The Essential Turing, 2004, p.21f) writes:

In the years immediately following the Second World War, the Hungarian-American logician and mathematician John von Neumann—one of the most important and influential figures of twentieth-century mathematics—made the concept of the stored-programme digital computer widely known, through his writings and his charismatic public addresses […] It was during Turing’s time at Princeton that von Neumann became familiar with the ideas in ‘On Computable Numbers’. He was to become intrigued with Turing’s concept of a universal computing machine. […] The Los Alamos physicist Stanley Frankel […] has recorded von Neumann’s view of the importance of ‘On Computable Numbers’:

I know that in or about 1943 or ’44 von Neumann was well aware of the fundamental importance of Turing’s paper of 1936 ‘On computable numbers . . .’, which describes in principle the ‘Universal Computer’ of which every modern computer […] is a realization. […] Many people have acclaimed von Neumann as the ‘father of the computer’ (in a modern sense of the term) but I am sure that he would never have made that mistake himself. He might well be called the midwife, perhaps, but he firmly emphasized to me, and to others I am sure, that the fundamental conception is owing to Turing—insofar as not anticipated by Babbage, Lovelace, and others. In my view von Neumann’s essential role was in making the world aware of these fundamental concepts introduced by Turing […].

Epilogue: the long reach of the algorithm

The following is an example of progress in philosophy which, while quite clear-cut in my view, hasn’t achieved consensus in the discipline, so I wouldn’t count it as a success story quite yet. It also has more to do with the development of advanced computers and subsequent philosophical work than with the conceptual analysis of computability. But Turing, as the father of the algorithm, does deserve a nod of acknowledgement for it, so I included it here.

Peter Millican an excellent, concise summary of the point (Turing Lectures, HT16, University of Oxford):

Information processing, and informationally sensitive processes, can be understood in terms of symbolic inputs and outputs, governed by explicit and automatic processes. So information processing need not presuppose an “understanding” mind, and it therefore becomes possible in principle to have processes that involved sophisticated information processing without conscious purpose, in much the same way as Darwin brought us sophisticated adaptation without intentional design.

On the idea of natural selection as an algorithm, see Dennett.