Church's Thesis asserts that the only numeric functions that can be calculated by effective means are the recursive ones, which are the same, extensionally, as the Turing-computable numeric functions. The Abstract State Machine Theorem states that every classical algorithm is behaviorally equivalent to an abstract state machine. This theorem presupposes three natural postulates about algorithmic computation. Here, we show that augmenting those postulates with an additional requirement regarding basic operations gives a natural axiomatization of computability and a proof of Church's (...) Thesis, as Gödel and others suggested may be possible. In a similar way, but with a different set of basic operations, one can prove Turing's Thesis, characterizing the effective string functions, and--in particular--the effectively-computable functions on string representations of numbers. (shrink)

In Honour of John Crossley’s 85th Birthday.

Tagmemic theory as a semiotic theory can be used to analyze multiple systems of logic and to assess their strengths and weaknesses. This analysis constitutes an application of semiotics and also a contribution to understanding of the nature of logic within the context of human meaning. Each system of logic is best adapted to represent one portion of human rationality. Acknowledging this correlation between systems and their targets helps explain the usefulness of more than one system. Among these systems, the (...) two-valued system of classical logic takes its place. All the systems of logic can be incorporated into a complex mathematical model that has a place for each system and that represents a larger whole in human reasoning. The model can represent why tight formal systems of logic can be applied in some contexts with great success, but in other contexts are not directly applicable. The result suggests that human reasoning is innately richer than any one formal system of logic. (shrink)

La thèse de Church-Turing stipule que toute fonction calculable est calculable par une machine de Turing. En distinguant, à la suite de nombreux auteurs, une forme algorithmique de la thèse de Church-Turing portant sur les fonctions calculables par un algorithme d’une forme empirique de cette même thèse, portant sur les fonctions calculables par une machine, il devient possible de poser une nouvelle question : les limites empiriques du calcul sont-elles identiques aux limites des algorithmes ? Ou existe-t-il un moyen empirique (...) d’effectuer un calcul qu’aucun algorithme ne permet d’effectuer ? Je montrerai ici la pertinence philosophique de cette question. Elle interroge la capacité de processus symboliques comme les calculs à simuler certains processus empiriques. Elle permet également d’étudier le statut épistémologique des calculs réalisés par des machines. S’il existait une fonction calculable par une machine sans être calculable par un algorithme, il existerait un problème mathématique qui serait soluble par un dispositif empirique, sans être soluble par aucune méthode mathématique a priori. (shrink)

La thèse de Church-Turing stipule que toute fonction calculable est calculable par une machine de Turing. En distinguant, à la suite de nombreux auteurs, une forme algorithmique de la thèse de Church-Turing portant sur les fonctions calculables par un algorithme d’une forme empirique de cette même thèse, portant sur les fonctions calculables par une machine, il devient possible de poser une nouvelle question : les limites empiriques du calcul sont-elles identiques aux limites des algorithmes? Ou existe-t-il un moyen empirique d’effectuer (...) un calcul qu’aucun algorithme ne permet d’effectuer? Je montrerai ici la pertinence philosophique de cette question. Elle interroge la capacité de processus symboliques comme les calculs à simuler certains processus empiriques. Elle permet également d’étudier le statut épistémologique des calculs réalisés par des machines. S’il existait une fonction calculable par une machine sans être calculable par un algorithme, il existerait un problème mathématique qui serait soluble par un dispositif empirique, sans être soluble par aucune méthode mathématique a priori. (shrink)

The algorithm, a building block of computer science, is defined from an intuitive and pragmatic point of view, through a methodological lens of philosophy rather than that of formal computation. The treatment extracts properties of abstraction, control, structure, finiteness, effective mechanism, and imperativity, and intentional aspects of goal and preconditions. The focus on the algorithm as a robust conceptual object obviates issues of correctness and minimality. Neither the articulation of an algorithm nor the dynamic process constitute the algorithm itself. Analysis (...) for implications in computer science and philosophy reveals unexpected results, new questions, and new perspectives on current questions, including the relationship between our informally construed algorithms and Turing machines. Exploration in terms of current computational and philosophical thinking invites further developments. (shrink)

Alonzo Church (1903–1995) was a renowned mathematical logician, philosophical logician, philosopher, teacher and editor. He was one of the founders of the discipline of mathematical logic as it developed after Cantor, Frege and Russell. He was also one of the principal founders of the Association for Symbolic Logic and the Journal of Symbolic Logic. The list of his students, mathematical and philosophical, is striking as it contains the names of renowned logicians and philosophers. In this article, we focus primarily on (...) Church’s philosophical contributions. (For an account of his life and academic history see the Introduction to The Collected Works of Alonzo Church (2019).) However, we also discuss his mathematical results when it is desirable to do so in order to pursue a philosophical issue. (shrink)