Brandom’s Sufficiency Claims

Posted in Philosophy, Review, Semantics, Things that might be true by nathanielforde

Introduction: Characterising Semantic Content

The fundamental semantic unit on Brandom’s picture of semantics is that of the vocabulary. Opposed to traditional accounts of semantics which seek to analyse of the meaning of statements by breaking-down the semantic structures into discrete semantic units, Brandom allows (in his Between Saying and Doing) that vocabularies exist as self-sustaining structures, that do not admit such absolute decomposition. In support of the view he points to the failure of the logicist program in the philosophy of mathematics, where the robust vocabulary of mathematics cannot be semantically equated with statements expressible in purely logical vocabulary.

He further defends the general claim that the traditional project of semantic analysis is misguided by Sellarsian arguments against the myth of the given. Any candidate analysis will involve a decomposition of the whole structure into some primitive semantic units in the base vocabulary. The traditional empiricist program would seek to analyse all semantic understanding in terms of understanding primitive observational reports. So assuming that some form of empiricism is true, then some base observational reports are semantically autonomous of the broader vocabulary. The broader vocabulary depends for its semantic cogency on the empiricist’s autonomous base, in terms of which the it is to be analysed. However, for any candidate base vocabulary we can argue that we cannot be deemed to understand the semantic primitives unless we know how they are to be practically deployed within the network of our broader vocabulary. For example, assume the empiricist wants a reduction of our knowledge into a base phenomenalist observational vocabulary. How can we be considered to understand the claim that: $x \text{ is red}$ if we do not accept that this commits us (by inferential connection) to the claim that $x \text{ is not blue}?$ We cannot. The argument generalises for any reductive programme of semantic analysis, since semantic understanding is to be demonstrated by practical fluency with the semantic primitives in question and fluency is a holistic notion relative to the broader vocabulary. Hence the proper study of semantics is not exhausted by the process of analysis; crucially we can see that semantic content of our primitive terms (i.e. what we understand when we understand the meanings of terms) is at least in part conferred upon them by their role in a wider inferentially mediated setting.

On this understanding the meaning of any syntactic constructions are to be understood relative to the knowledge of a broader vocabulary, and we demonstrate the understanding of a vocabulary by our ability to enter into certain kinds of practices. In mathematics, for instance, we can be said to know the meaning of the term “proof” only when we inferentially trace the path from our assumptions to the statement we set out to prove and subsequently react appropriately to the statement of a proof completion $\dashv.$ It would be a semantic error to continuing drawing deductions after articulating a valid proof. This kind of practical ability which we expect of any users of our vocabulary has the effect of delimiting the conditions under which a term is being meaningfully used. In this manner Brandom argues that pragmatics contributes to the semantics of our vocabulary.

He further notes that where we have access to meta-vocabulary $V^{M}$ which describes exactly how demonstrating facility with a set of practices $P_{V}$ is sufficient to demonstrate a semantic understanding of the vocabulary $V$ , the meta-vocabulary will be able to express why such practices are apt to constrain the meaning of our vocabulary. He depicts the relationship as follows:

The thought is that for any particular vocabulary $V$ there is a set of practices which when enacted are deemed $PV$ -sufficient to indicate mastery of the vocabulary, such that any meta-language $V^{M}$ will be able to describe (specify) those actions which indicate competence. A fully expressive meta language results from a kind of composition function which recognises the conditions of practical competence as a sufficient condition for determining semantic content of $V$ and articulates the rules for deployment of a $VP$ -sufficient description to perfectly specify those practices pertinent for the evaluation of competency with vocabulary for $V$ . These for Brandom are the basic meaning-use relations, and for each particular vocabulary-in-use there is a process by which we can recursively generate the appropriate meta-language. To do so we will show below how each mapping between practices and vocabularies is taken to preserve analogous categorical structures which can be recovered (one from another) by a chain of equivalence proofs, at each stage.

Intuitive Sellarsian Examples

To illustrate the types of considerations this set up allows, we examine another Sellarsian argument. Namely, the claim that the “looks- $\phi$ ” vocabulary presupposes (i.e. must be able to express) the “is- $\phi$ ” vocabulary in so far as the pragmatic ability to discern appearance from actuality assumes the ability to identify the actual.

Again we denote the composition relation by the dashed arrow, but the point is clear, since the expression of perceptual modalities requires the ability to practically distinguish objects by sight accurately. It is a necessary condition of such an ability that we are able to identify things in their actual condition, which is a ability sufficient to confer meaning on existential and identity claims. Hence, talk of appearance amounts to the withholding of the existential claim, and only by composing our abilities can we generate a suitably expressive language to capture the perceptual modalities. Similarly, the argument we sketched above, that there is no autonomous observational vocabulary from which we build our semantics relies on the idea that observational expression assumes a practical capacity that in turn presupposes the inferential capacity (which is at least sufficient) for an appropriately broad semantic understanding, contrary to the supposed semantic autonomy of observational reports. Only by composing the two abilities can we determine a language sufficient to articulate the conditions under which observational reports are meaningful.

Recall that the semantic understanding of the claim “x is red” requires the ability to not equate the object x with any blue object. In particular we must be able to wield an inferential capacity which gives the lie to the idea that we understand color observations independently of anything else.

Santa-Speak and Speaking about Santa-Speak

Now for a brief digression.

Santa laughs and he laughs heartily. We can build a machine which describes how Santa laughs, and it can be used to establish whether any program generating a laughter track appropriately simulates Santa’s laugh. The following example over and above the previous cases is of central significance, not just for its relative clarity but also because of how the setting has a connection to computational linguistics. The basic idea is that we take a set $\{ a, h, ... \}$ of syntactic primitives and allow various composition operations or rules as described by a machine. In particular, consider the specification of a non-deterministic finite state automata which articulates (prints) how Santa laughs. There is an initial state and two intermediary states. The fourth state is an end state so there are no actions specified.

The rules are such that for any legitimate string of inputs Santa always laughs a string $(h, ...!)$ , with a random variation, of $(ha) \text{ or } (ho)$ being produced at state two. After which he might begin to chuckle anew, or end with a hearty exclamation. For any finite string of inputs the purpose of the machine is to determine whether it is a legitimate string. It will reject any string as illegitimate if it yields a premature halt.

Relating Automata to Meaning Use Diagrams

The notion of producing a legitimate string is analogous to the notion of competent linguistic practice. In effect the rules of syntactic construction put forward in the state-table are a normative constraint on how deploy Santa’s alphabet $\{a, h, o, ! \}$ in the way it is “meaningful” for Santa. The following diagram gives the right structure:

The ”meta-language” of the state-table (above) describes the practices appropriate for the proper syntactic representation of Santa’s laugh. The point is that if we can describe this kind of practical performance constraint we can specify the pre-conditions and post-conditions appropriate to render certain utterances “meaningful” or at least syntactically correct. One fine example of this trend is the manner in which recursive languages can be specified in a category free language, which in turn is demonstrably understood by an ability to deploy the differential response patterns of an appropriate push-down automata. Again the picture is as follows:

We shall now sketch the details that show this relation to describe a valid theorem.

Context Free Grammars

First recall that a context free grammar is a phase structure grammar $G = (N, T, P, S)$ where $N$ is the set of a non-terminal (complex) symbols, $T$ is the set of terminal (atomic) symbols, $P$ is the set of production rules and $S$ is the start symbol a member of $N$ . For our phase structure grammar to be a context free grammar, we need to further specify that if $x \rightarrow y$ is a production rule for G, then $x \in N, y \in (N \cup T)^{*}$ . This is just to say that any non-terminal string can be transformed into any constructable string whatsoever, even the empty string. The language generated by $G$ is denoted:

$L(G) = \{ x | x \in T^{*} \text{ and } S \Rightarrow^{*} x \}$

where $\Rightarrow^{*}$ defines the “derivation” relation we have in the language by applications of the production rules in $i$ steps where $i \geq 0.$ So the language is composed of a set of strings generated by manipulations of the start string; the legitimate manipulations are determined by a set of production rules. For example if we specify the production rules of $G$ as follows: $\text{ (1) } S \rightarrow AA, \text{ (2) } A \rightarrow AAA|bA|Ab|a$ , then our grammar is category free, and any language generated will be a category free language. If you’re familiar with basic logical languages you can think of the production rules as decomposition operations in a tableau proof e.g. $(\phi \wedge \psi)\vee (\tau \wedge \psi)$ is produced from, or decomposes to $(\phi \wedge \psi)$ or $(\tau \wedge \psi)$ . The production rule might be $C \rightarrow AB$

This point should illustrate how adherence to (and recognition of) these production rules is taken to be sufficient for an understanding of the language; more radically, Brandom wants to say that the practice of these rules confers legitimacy on strings created in the language. Like the Santa example above, we can create a machine to test whether any string is “grammatical” i.e. legitimate, on the basis of the definition of $G$ .

You, me and Pushdown Automata

So who understands these languages? Or better said, what behaviour is indicative of this understanding, and who enacts it? Pushdown automata are machines with a virtual memory, like the Santa-speak finite state machine, but augmented with a memory stack.

Definition: Pushdown automata: are sextuples ( $Q, \Pi, \Gamma, \delta, q_{0}, F$ ) where $Q$ is the set of finite machine states, $\Pi$ is the input alphabet and $\Gamma$ is the stack alphabet representative of the machine’s memory. We let $q_{0}$ be the initial machine states and $F \subseteq Q$ is the set of final states or terminal nodes. The crucial feature of each machine is the transition function $\delta: Q \times (\Pi \cup \{\epsilon\}) \times (\Gamma \cup \{\epsilon\}) \mapsto Q \times (\Gamma \cup \{\epsilon\})$

The thought is that a machine takes inputs of an ordered triple in the form the active machine state, memory and a given string read from left to right $< [ x ], y, z, w ... >$ , and then operates according to the specifications of the transition function which induces a new machine state and an updated memory, receptive for the novel string instructions $< [y], z, w ... >$ . After each transition an element of the input string is popped out of the memory stack, and a novel element pushed into the stack. This definition leaves it an open question as to whether the transition function is ultimately deterministic or non-deterministic.

So now the idea is to show that for every context free grammar $G$ there is a pushdown automata which operates to test for accordance to the parse/production rules essential to $G$ . In this manner any string input can be tested by the PDA to determine whether the string is a legitimate element of $L(G)$ . The manner in which we show this is possible is to first define the language for a machine $M$ as the set of strings $L(M)$ accepted by $M$ , and then show that this set of strings is the same as the set of strings legitimately produced by derivations in $G.$ An accepted string is defined as one which when input into the PDA ensures that the machine comes to a halt (final state) with an empty memory stack i.e. that the string is entirely parsed string. It has exhausted its “problem string”. To facilitate the proof consider the following lemma.

Lemma The Greibach Normal Form of a context free grammar $G$ is such that all the rules of production have one of the following forms:

$A \rightarrow aA_{1}A_{2} ...A_{n}$
$A \rightarrow a$
$S \rightarrow \epsilon$

where $a \in \Pi$ and $A_{i} \in N - \{S\} \text{ for } i = 1, 2, ... n.$

There is an algorithm for converting all context free grammars $G$ into an equivalent Greibach Normal Form grammars $G^{'}$ . Consider a schematic example of how we can change the rules of a grammar without impacting the language generated by that grammar. Suppose that we have a production rule of the form $A \rightarrow uBz \in P$ , then we can remove this rule and replace it with $A \rightarrow uw_{1}z | uw_{2}z| .... |uw_{n}z \in P^{'}$ , where $B \rightarrow w_{1} | w_{2} | .... |w_{n}$ were the productions rules for $B \in P.$ It is then straightforward to show that any $\Rightarrow^{*}$ derivation made with the rules $P$ can be established by using the rules $P^{'}.$ In this fashion we replace the rules of the grammar $G$ to establish the grammar $G^{'}$ in Griebach normal form. The proof of the existence of the algorithm for the general case is done by induction, but the details aren’t terribly instructive. The point is that we can put any set of production rules into a form that aids parsing. If you’re inclined to think that something similar is involved in human cognition you can think of this as an efficiency measure to aid our focus on the particulars, where for every complex utterance we first isolate the “subject” of the statement and subsequently process the relations.

Theorem: For every CFG which generates $L(G)$ , there is a PDA such that $L(G) = L(M)$

Proof Let $G = (N, T, P, S)$ be a context free grammar in Griebach normal form that generates $L$ . An extended PDA $M$ with start state $q_{0}$ is defined by:

$Q_{M} = \{q_{0}, q_{1} \}$
$\Pi_{M} = T$
$\Gamma_{M}$ $= N - \{S\}$
$F_{M} = \{q_{1} \}$

and we define the transition function as follows:

(1) $\delta(q_{0}, a, \epsilon) = \{[q_{1}, w ] \text{ : } S \rightarrow aw \in P \}$

(2) $\delta(q_{1}, a, A) = \{ [q_{1}, w] \text{ : } A \rightarrow aw \in P \text{ and } A \in N - \{S\} \}$

(3) $\delta(q_{0}, \epsilon, \epsilon) = \{ [q_{1}, \epsilon] \} \text{ if } S \rightarrow \epsilon \in P$

These are sufficient because of the insistence on the Greibach normal form. The $\delta$ function ensures that each transition updates the memory stack of the push-down automata so that the PDA will cycle through the non-terminal variables $A_{1}... A_{n}$ until it halts, so long as there is an input string in accordance with the grammar of $G$ . The transition function is undefined otherwise i.e. it would fail to process ungrammatical strings. We shall now show that for any computation $[q_{0}, u, \epsilon] \vdash [q_{1} \epsilon, w]$ , there is a derivation $S \Rightarrow^{*} uw$ with $u \in \Pi_{M}^{+}$ and $w \in N^{*}$

Our base case is the one step computation, and an application of the rule of the form $S \rightarrow aw$ ensures that this case holds.

IH For all $n-1$ -step computations of strings $uw$ we can find a derivation $S \Rightarrow_{n-1} uw$ such that $uw \in L(G)$

Now for the $n-th$ step, we take a computation $[q_{0}, u, \epsilon ] \vdash^{n} [q_{1}, \epsilon, w]$ with $u = va \in \Pi$ and $w = w_{1}w_{2} \in N^{+}$ , which can be rewritten:

$[q_{0}, va, \epsilon] \vdash^{n-1} [q_{1}, a, Aw_{2}] \vdash [q_{1}, \epsilon, w_{1}w_{2}]$

By the inductive hypothesis and the Greibach production rules we have it that there is an $\Rightarrow^{n}$ derivation such that: $S \Rightarrow^{n-1} vAw_{2} \Rightarrow vaw_{1}w_{2} = uw$ . The case where the computation proceeds from the initial state by the application of the third transition rule, is handled similarly. Hence any positive length string $u$ is derivable in $G$ if there is a computation that processes $u$ without prematurely halting.

This shows that $L(M) \subseteq L(G)$ , the other direction is analogous and proven by Sudkamp. This completes the proof. $\dashv$

To see that the language $L(M)$ is recursively enumerable we need only observe that for any PDA we can describe a two-stack Turing machine that is equivalent to it. This theorem can also be found in Sudkamp’s Languages and Machines. As such, any CFG dictates a PDA and all PDAs generate recursively constructible languages. It is in this sense that context free grammars are said to be sufficient to specify the functions of recursive languages and so serve as a normative meta-language for describing the syntactic construction rules of a given recursively enumerable language. In this way Brandom argues for the categorical relations between patterns languages and patterns of performance.

Automata, Differential Response and Algorithmic Elaboration

So we know that functional capacity with the procedures enacted by a PDA is sufficient to generate a veneer of competence with a recursive language. If all of this is beginning to sound like an agonisingly exact rendition of the Turing Test, rest assured that Brandom has something more in mind. Linguistic competence is only one criteria is any test for sapience. He writes:

The issue is whether whatever capacities constitute sapience, whatever practices or abilities it involves, admit of such a substantive practical algorithmic decomposition. If we think of sapience as consisting in the capacity to deploy a vocabulary, so as being what the Turing test is a test for, then since we are thinking of sapience as a kind of symbol use, the target practices-or-abilities will also involve symbols. But this is an entirely separate, in principal independent, commitment. That is why […] classical symbolic AI-functionalism is merely one species of the broader genus of algorithmic practical elaboration AI-functionalism, and the central issues are mislocated if we focus on the symbolic nature of thought rather than the substantive practical algorithmic analyzability of whatever practices-or-abilities are sufficient for sapience. (BSaDpg 77)

This is pregnant passage, but the key take away is that the conditions of sapience are unspecified, but taken to be specifiable by means of algorithmic action. Plausibly the conditions involve more than linguistic competence, but can nevertheless be described as certain kind of differential response to an array of stimuli a la Quine; where the input strings can be thought of as composed of as various information streams, and the transition functions are modeled on features of our cognitive processing. The view of AI-functionalism at the heart of this story is premised on the idea that certain algorithmically specifiable computer languages are apt to serve as pragmatic meta-vocabularies for our natural languages. As such, any pattern of differential response we care to mention can be specified algorithmically, if it can be discussed in natural language at all. Hence, whatever the future course of scientific discovery, so long as the conditions of sapience can be artificially implemented and described in natural language, we can develop an algorithmic elaboration of patterns of the differential response involved. So there is, in principal, no bar for the development of artificial intelligence, if we can come to understand what in fact makes us tick.

Before considering the wider ramifications of this view we shall examine (in the next post) a detailed example of an algorithmic elaboration of the abilities and practices deemed to be pragmatically sufficient to warrant ascriptions of linguistic competence. This will be paradigmatic for the broader stripe of “competency” claims Brandom needs to make if he is to isolate the conditions of sapience algorithmically.

23Apr2014

Personal Identity and Existential Quantification

Posted in Metaphysics, Philosophy, Semantics, Things that might be true by nathanielforde

We’ll begin with a brief survey of a problem raised by Derek Parfit about the nature of personal identity, then we move swiftly to consider whether such problems can motivate a plurality of distinct existential quantifiers and orders of explanation.

The question of personal identity begins with a thought experiment. Imagine teleportation technology exists such that entry into a teleportation pod involves the slow destruction of your physical body (through radiation poisoning) and the (immediate) reconstruction of an identical healthy body within another pod at the destination. The process is such that upon reconstruction, the individual at the destination has retained all of your physical and mental characteristics, they have your memories, instincts, attributes and desires. The question remains; are you dead and cloned or alive and arrived?

Two Criteria of Personal Identity

The first criterion we shall examine is the notion that identity is determined by physical continuity. The intuition is best compounded by insight that a white billiard ball can undergo a cosmetic change by being painting red. Another comment on cosmetic alterations gives the lie to idea that any significant change has occurred. You can put lipstick a pig, but it remains a pig regardless. This image is somewhat more visceral, but the same idea underwrites both scenarios. That said, there are some complications in the case of personal identity. If your identity is fully and only determined by your physical constitution, then is there a point of physical change which would constitute a shift in personal identity? Suppose that your beliefs, desires, memories and intentions are fully fixed by an arrangement of brain states, then can brain damage impact the existence of your person-hood? Parfit glosses these concerns as follows:

What is necessary [for personal identity] is not the continued existence of the whole body, but (1) the continued existence of enough of the brain to be the brain of a living person. X today is one and the same person as Y at some point in time if and only if (2) enough of Y’s brain continued to exist, and is now X’s brain and (3) this physical continuity has not taken a “branching” form. (4) Personal identity over time just consists in the holding of facts (2) and (3).

We say an object’s continuity takes a branching form if the same physical continuity can be ascribed to more than one object. For instance if at some point an object is disassembled and then later two objects are assembled physically identical to initial object. Hence if we take physical continuity in this sense as a measure of personal identity then the teleportation thought experiment involves little more than death and cloning, without a preservation of personal identity. The same physical continuity can be ascribed to myself and my clone for the brief time in which we exist simultaneously.

If instead we look to the psychological criterion of personal identity things are a little more subtle. Here the idea that is personal identity involve a certain kind of psychological connectedness over time. Again you might think brain damage is a concern where amnesia could sufficiently devastate the concepts of self, desires and belief in such a way as to entirely destabilize the psychological connectedness for an individual between two points $t_{1}$ and $t_{2}$ . So construed the core issue is that of the stability of a psychological connectedness over time. The loss of such connectedness is arguably recoverable if the condition impacting your sense of self, belief and desires is medically induced. In a very real sense you can take time off from yourself if you’re prepared to indulge in sufficiently mind altering drugs.

Distinguish between your sense of self yesterday and the sense of self you had when four, and so note that we need to distinguish the strength of the relation for psychological connectedness. Let’s define a notion of psychological continuity in terms of overlapping links of strong psychological connectedness. Whatever the locus of our sense of self, there are experiences which cause the generation of such a feeling, that nevertheless diminishes over time. So with this in mind Parfit puts forward the following suggestion:

There is a psychological continuity if and only if there are overlapping chains of strong connectedness. X today is one and the same person as Y at some past time if and only if (1) X is psychologically continuous with Y, (2) this continuity has the right kind of cause, (3) it has not taken a “branching” form. Personal identity just holds in satisfying (1) – (3).

The “right kind of cause” is deliberately ambiguous since the explanation of subjective self experience is not yet well understood in terms of the physical neuro-chemical description of psychological states. For discussion see here. The physical criterion ensures that there is no such thing as personhood over and above physical continuity, while the psychological criterion is more ontologically generous, but both of these characterizations are to be considered provisional as we will come to reconsider the importance of non-branching continuity. For the moment, note that the psychological criterion allows that there is such a thing as personhood for particular individuals in absence of physical continuity if the psychological state transfers over teleportation. This gels well with legal description of individuals within a state body who are ascribed rights after physical death and incineration. But is there something fanciful and needlessly metaphysical about such a view? Are persons merely a necessary fiction motivated to supply lawyers with clients?

Fundamentality: Restricted or Generic Quantification

Traditional existential claims have been considered univocal. There is (it’s often assumed) very little ambiguity attached to existential claims. However, if we accept that persons exist over and above their physical instantiation, then there seems to be a distinction between the claim that $\exists x F(x)$ where $F : = F_{1} \wedge F_{2} .... \wedge F_{n}$ is a complex descriptive predicate circumscribing the location and physical continuity of the individual over time, and the claim that $\exists x P(x)$ where $P$ is the “…is a person” predicate. Now since the quantifier ranges over a given domain, we ought to consider the components of that domain. In particular, we ought to consider whether the domain of quantification contains persons fundamentally , or whether personhood is some kind of abstraction over and above observations of kinds of continuity amongst more primitive physical/psychological states?

On the assumption that existential claims are univocal, then the contention that persons exist is exactly the claim $\exists x Px$ . However, if we wish to distinguish between the physical ontological primitives and persons, then personhood can be identified with a property described in physical terms akin to the claim that $\exists P \forall x (Fx \rightarrow Px)$ , but this arguably reverses the order of definition. We might instead accept the existence of persons and seek to explain their occurrence.

If we start with primitive restricted quantifiers and the assumption that existence claims are polysemous, then we make sense of the idea that claims about the existence of God and the existence of the Pope involve distinct considerations of proof and evidence. With this in mind you might want to distinguish between the generic existential quantifier which covers both God and his mouthpiece; $\exists x, y (x = g \wedge Pope(y))$ and the restricted quantifiers for abstractions and concrete entities: $\Big( \exists x_{abs}(x = g) \wedge \exists y_{conc} (Pope(y)) \Big)$ . Further fine grained distinctions could be made, if for instance you wanted to mark the difference between legal and mathematical abstractions or biological and chemical entities. On a purely semantic understanding the generic quantifier can be as readily understood as the disjunction of the more restricted quantifiers or the restricted quantifiers can be understood (unsurprisingly) as the restriction of the generic quantifier. But if we allow that the restricted quantifiers are ontologically more primitive such that we have $\exists x_{person} (x = y) \Leftrightarrow \exists x (x = y \wedge Py)$ as ontologically basic and semantically uncontested then it is a discovery that there exists a property definitive of person hood i.e. that $\exists F, \forall x_{person} (Px \leftrightarrow Fx).$ Minimally I take it that this approach better fits with the natural ontological attitude.

The vocabulary in which $F$ is defined can be more or less ontologically primitive than the “personhood”-vocabulary. The desire to streamline our ontological concerns would involve subsuming (by means of structurally relating) the entities of the higher-order ontologies within the class of entities definable in terms of ontological primitives. We currently have a structure something like the following:

In this map I have supplied a tentative categorization of the relations between some existential domains; linking the physical and psychological domains with the quantum level, and allowing the domain of persons to arise from characterisations in both the more primitive domains. The general point is that if we can define the property $F$ in terms of physical and relational predicates describable in the vocabulary of physics and neuro-chemistry then we have established a translation manual between the two domains of ontological concern. But many such translation manuals can be defined. For instance, instead of defining a person in terms of their physical constitution and continuity, we might seek to define a person in terms of their moral responsibilities in domain where individual rights, obligations and moral actors exist. The instinct to reconcile two such domains is common because we seek simplicity, but reconciliation is not necessarily possible. Some questions naturally arise: Do we need reconciliation? Is there an infinite plurality of nested ontological quantifiers? Can we reduce each claim in some ontological domain $D$ into equivalent claims in another ontological domains $D^{*}$ perhaps more primitive? How are the ontological domains ordered? Is there any partial overlap between domains that would make existential claims directly ambiguous? Are some ontological domains simply mutually exclusive? Should this incompatibility trouble us?

A Case for Univocal Existential Quantification

But before considering these questions you might object that our notion of a plurality of quantifiers is entirely bankrupt! One such argument from Peter van Inwagen purports to show that existence must be univocal. The main premise of the argument is that the notion of existence is related to number, and the argument stems from the fact that number is univocal. To see this first consider how an existential claim relating to a particular entity is just the assertion that the number of said entities is positive. Now compare the number of gods and the number of round squares. The number is identical since none exist. More positively, the number of horses is not zero, is equivalent to the claim that horses exist. In other words, define a predicate $N_{H}(x, 0) := ((N(x) = m \wedge H(x)) \wedge m \neq 0)$ , then:

$\exists x (H(x)) \leftrightarrow N_{H}(x, 0)$

Hence, by translation and the fact that numeric statements are not ambiguous the notion of existence cannot be polysemous. This argument is based on the view that extensional equivalence underwrites all semantics. However, if we argue that the polysemous nature of the existential quantifier depends on an intensional variance, then no such conclusion follows. However such a route undermines the idea of de re ontology we are engaged in. Nevertheless, we do not need to be concerned by the argument, because we can tolerate the idea that the notion of existence comes in the form of generic and restricted quantifiers, where the domain of the restricted quantifier is a proper subclass of the domain of the generic existential quantifier. The behavior of the semantics for $\exists$ will not change, but the open question for any candidate ontological domain which falls under a restricted quantifier $\exists_{???}$ , is whether this domain can be fitted into our best theory of world. Does the ontological structure of a theory in which $\exists_{???}$ is included, carve the world at the joints? If not, are there more pragmatic reasons for maintaining the theory with its current ontological baggage?

No matter how we would seek to define personhood we need to invoke the existence of a property, such that the second order quantifier is appropriately indexed to a base vocabulary in which our candidate definition is expressible. So assuming there is a good candidate expressed in terms of psychological/physical continuity, we would have something like: $\exists F_{psy/phy} \forall x_{persons} ( Px \leftrightarrow Fx)$ . The challenge is to discover the existence of $F$ and thereby clarify the structure in which the ontological domains are ordered. Until such a time as the structure has been delineated what cause have we to assume the character of such an ordering will ultimately see personhood defined in terms of a psychological or physical continuity? The broader moral is that the semantics for “existence” can be seen to evolve with the structure of available theory, the semantics for the generic $\exists$ is as liberal as the disjunction of its sub-domains allows.*

Permissive Ontologies?

While our characterization of the discipline of ontology might seem to be overly permissive, we shall show that the concern for internal consistency is as pertinent as ever, thus providing a restriction on the plurality of entities admitted by our best theory. Staying with the subject of personhood we consider an argument against cartesian dualism and the ontology of separately existing mental entities.

The idea is that there is a unified subject of experience, a distinct entity – the referent for every use of the term “I”. This entity is who I am but exists over and above my physical instantiation. How can we argue for the existence of such a creature? The standard Cartesian argument that “I think therefore I am” is less than decisive since the possibility of thought presupposes the existence of a thinker, but not the character of the thinking agent. Even if the subjective unity of experience, the coherence of appearance in each instance allowed us to identify ourselves as the subject of that experience, we could not ensure that this subject of experience continued to exist moment after moment. The sense of self which accompanies the immediate experience does not imply the persistence of the subject of experience. At best we are aware of the psychological continuity in terms of our memories of our attitudes and desires over time. Hence the Cartesian subject is an extraneous somewhat poorly motivated ontological posit.

Worse Descartes’ cogito observation at best illustrates that thinking occurs, but it is only a contingent fact that we ascribe thoughts to thinkers. Strictly speaking we could eliminate talk of thinkers is if we could locate thoughts in an impersonal level of description, such as brain activity. Consider Parfit’s reincarnation argument. If a Japanese woman had verifiable memories of her life as a Celtic warrior, then we should distinguish between beliefs as carriers of memories in a brain, and beliefs proper, perhaps as ideas in the mind of a Cartesian subject. The reincarnation possibility would provide evidence for the existence of the Cartesian subject, but it depends on the viability of verifying the reincarnation possibility. Similar remarks apply to cases of brain damage which should (given all we know about memory retainment) wipe the memories from the mind of an individual but for some reason as yet undiscovered do not. Both these possibilities are implausible and the latter points, at worst, only to a gap in our knowledge of the brain, not the need for Cartesian dualism.

So what then does the term “I” refer to? Does the term have extension in the domain of the $\exists.$ quantifier? The simple answer is yes, if the domain contains a restriction for the class of persons. The answer is a little more complicated if we do not allow this simplification. Nagel, for instance, takes the extension of the term “I” to be exactly the brain of each individual. But we can consider a kind of Kantian argument that the notion of personhood is indispensable to our conception/knowledge of the world. Everything we know about about the world is filtered or mediated via our position in the world i.e. specified in relation to the type of entity we take ourselves to be. Hence any knowledge we have of the world is impossible without the supposition of personal identity. The premises of this argument are more extensive than we have space to elaborate, but for brevity’s sake consider the role of thought experiment in experiment design and the manner in which possibility of personal observation guides thought experiment and therefore the process of scientific rigor. Scientific discovery works and is of value, and since the assumption of persons is indispensable to scientific discovery then it is of value. Such reasoning persuasively underwrites the posit of persons, but it says nothing of their identity conditions.

Identity Conditions and Reductive Explanations

Quine’s doctrine of “no entity without identity” might be thought to apply here. So we should consider whether the physical and psychological criterions of personhood run afoul of certain counterexamples. We consider an argument by Williams to show that the continuity criteria are defeasible, and then argue that that this is no bar to ontological commitment.

Consider the idea that I enter into an experiment where a mad scientist (i) manipulates my memories successively with an increasing range of changes and (ii) exposes me to a constant stream of brutal and agonising pain. With each change of memory we observe that there is an interruption (of an increasing degree) to my psychological continuity, however the continuation of my pain seems to promote the intuition that “I” remain suffering. Like the Sorites paradox this leads from plausible premises to an absurd conclusion. No matter that disparity between my memories of who I am before I enter the experiment and who I am afterwards, we must conclude I am the same person who began the experiment. This is absurd, since by suitably extensive manipulation of my memories I can come to believe anything about my past, desires and ambitions. The idea coming out of this thought experiment is that the degree of psychological connectedness over moments varies with the “features” manipulated and the notion of which “features” are preserved is central to estimates of personal identity. In particular this is about the strength of feeling versus the import of “core” memories for establishment of personal identity. Hence in any estimate over whether “I” survive the scientist’s manipulations we might want to draw a line; ranking how the intensity and duration of my pain versus the importance of some “crucial” sense of self-identity based on memory, fits into a categorical description of who I am. This line is unavoidably arbitrary.

Questions about whether I survive can be asked at any stage in the process of the scientist’s manipulations, and not all stages will have a definite answer. But given the importance that the role of personal identity has in our conception of the world we cannot tolerate such agnosticism, hence Williams argues we are better off accepting that the referent of the term “I” is simply the brain of that individual, then no matter the range of psychology disparity at least we can answer the question positively. I survive the experiment; I am “a changed man” but ultimately the same person. However, the Sorites line of argument applies equally to this physical criterion. Imagine a science fiction case where we apply a Theseus’ ship scenario by swapping out my body parts 1% at a time while maintaining the constant sense of pain. William’s absurd conclusion follows again. Hence we cannot simply take refuge in the notion that the brain is to be identified with our personhood. The sum of arguments seems to suggest that there is no fixed criterion of personal identity. Do you then follow Quine and claim there are no such entities? Or revert to Cartesian metaphysics?

Neither, we reject Quine’s doctrine and deny the Cartesian cosmos. We accept a form of reductionism where personhood supervenes on the physical and psychological facts and we allow that changes in the latter amounts to changes in the former, but feel no need to overly specify what particularities constitute our personhood at any particular moment. Contextual considerations about the phenomenal experience of self (and indeed other) will be our best guide to determine the weight of the particular psychological or physical features on which personal identity supervenes. We are ontologically generous but ultimately undogmatic in self description. Similarly we could generalize this view and say that personhood is property of objects that can be seen to supervene on a host of more primitive conditions e.g. say $\exists M \forall x (Person(x) \leftrightarrow M(x))$ , where M is the property of being a moral agent, we could allow a reductive analysis of personhood in terms of moral agency. In this instance the right kind of continuity would be the history of the individual’s moral action and inaction. In this way I reject the idea that personal identity is suitably defined by straightforward physicalist reductions, and allow that personal identity can evolve in various ways. For Parfit personal identity is tied to the relation R of psychological/physical continuity, but I simply allow the key notion is the reduction applied and the reference of the term “I” is contextually individuated by the relation of reduction we appeal to in each scenario. We motivate a generous interpretation of $\exists$ by means of pragmatic considerations about the point of such an ontological posit, in the role of various explanatory projects.

Why Identity is not what Matters

Identity doesn’t matter because it’s never been fixed anyway; physical/psychological continuity tolerate interruption and change.To see this reconsider the teleportation thought experiment re-jigged.

Instead of materializing at one location, let there be two pods in which two individuals appear both psychologically continuous with me but in different scenic locales. As before, the initial traveller dies from massive radiation exposure but my psychological concerns continue unabated in the two agents $a_{1}, a_{2}$ physically identical. Now if Identity matters then it is crucial that we are able to say (a) if I survived and (b) whether I am $a_{1}$ or $a_{2}?$ The defender of the claim that identity matters will be hard pressed to pick (b) whether I survived as either $a_{1}$ or $a_{2}$ and such an inability casts doubt on (a) whether I survived at all. But since it is possible that psychological continuity can be (mildly) interrupted without impacting our attributions of personal identity, this fictional scenario of division poses a genuine problem for the identity theorist. For the reductionist, the question of my survival is vacuous. All that can be said is what the thought experiment describes; my physical and psychological state of existence ended, and then continued anew albeit doubly instantiated. We know all that happened. The identity theorist seems to hanker like the Cartesian dualist for a bigger answer, an essential character trait preserved over only the true “me” – but this is a misplaced metaphysical instinct.

You might object that this doubling of “self” does not fit the logic of an identity relation, so there is a structural flaw in the thought experiment. It is no longer about personal identity but personal “possession”. In the scenario I can be seen as a virus inhabiting bodies not my own. Or put another way, the relation of identity should be one to one, so as to disallow branching instances of psychological continuity. Parfit responds, that if this concern is valid then the one to one feature of the personal identity relation must add something significant to the notion of personal identity over and above the instantiation of “mere” continuity. In this respect we could try to imagine possible scenarios wherein we place my two dopplegangers, and a third clone created by a teleportation device which only copies one instance of who I am (i.e. ensures that the relation is one to one). Given their identical psychological and physical traits each of the three is modally and behaviorally indistinguishable from the other, so what has the insistence on a one to one relation achieved? Nothing. Our constantly novel subjective experience preserves enough of our past concerns and traits to establish the strong connectedness and continuity that the attribution of personal identity aims to pick out. Nothing more need be added.

Identity does not matter because death by teleportation is not qualitatively different from ordinary survival. At worst it’s like a short nap. If you can be recognized (and recognize yourself) before and after bed, by any criteria whatsoever, then the same is true of teleportation. This is in a effect a concession that the relation of personal identity is founded on a non-strict, or contingent and evolving series of reductive self-interpretations.

Conclusions: What does matter?

Parfit’s breadth of thought on this topic is vast and we’ve only really glossed the crucial arguments. That said, this is a fair presentation of the argumentation, and I take it to have established the idea that the (1) persons are not Cartesian egos, (2) the existence of persons is a well motivated existential posit, (3) the existential claims can be defended by the establishment of particular supervenience relations which trace the evolution of appropriate features. Or put more formally we could say that the intensional semantics for “I” picks out at each context, one of a class of candidate reductions, (4) the domain of $\exists$ is best seen to be evolving in so far as the semantics of “existence” will not be settled until everything dies, (5) the attempts to undermine the variety of reductionist cases by arguments for the determinacy of identity are insufficient, hence do not pose a problem for our tolerance of multiple explanatory relations.

It remains to suggest (6) that there are practical reasons for maintaining an ontology rich with indistinct persons. Unfortunately, the scope of these considerations are vast and depend upon details of moral theories. It will suffice for the moment that these arguments for the existence and specific character of persons liberates us from a conception of selves which have an inordinate focus on the importance for self-concern. For instance, moral theories of self-interest are placed on a much weaker footing since the interests of each person is not necessarily preserved over future and successive stages of the individual agents involved. We will return to consider the details of developing these concerns in a later post. An alternative argument (7) for this characterization of persons is that the role of explanation can be expanded to incorporate multiple reductive relations which track different properties as appropriate to the type of personal identity we wish to track. This is more faithful to the variety of explanatory projects which seek to use the notion of persons as fundamental. For instance, the explanation of personal responsibility is best sought by incorporating the expectation of free action in the psychological/moral characterisation of that person, whereas the explanation of innocence by reason of insanity might better appeal to the causal/deterministic characterisation of the person as the locus of certain inviolate physical processes. The ontological structure we have articulated allows us to incorporate this flexibility and does so in a principled manner sympathetic to the projects of Parfit and McDaniels.

* Our discussion of the existential quantification is deeply indebted to Kris McDaniel’s paper on “Ways of Being” in the Metametaphysics collection

10Mar2014

Abstract Models of Computation

Posted in Logic, Mathematics, Modality, Philosophy, Semantics, Things that are true by nathanielforde

Abstract Machines

Following our earlier discussion of recursive functions we will now describe an abstract machine and how to code an abstract machine in such a way that we can simulate any machine-action on the natural numbers in terms of recursive functions.

A function, you will recall, requires an input and an output. This is the core observation since whenever an abstract machine is seen to simulate the patterns of output/input we describe as recursive functions, then our result follows. Informally we describe a abstract machine as operating on a string with an input $x$ , effecting a series of read, write actions to end with the output value of $f(x)$ thereby simulating the mathematical function naturally described by $f$ .

Traditionally we represent the different machine states $q_{i}$ for all $i \in S$ , where $S$ is the set of available machine states. The actions performed by the machine is determined by the machine state and the scanned square, but how you might ask does a scanned square contain sufficient information to direct the machine’s action?

To overcome this apparent informational deficiency, we avail of a technique called coding. This is described here, but very shortly, the idea is to take the string inputs in the computational language as codes for more complicated instructions which can be discovered by decoding the string input. Each machine state $q_{i}$ has a limited range of actions to perform as determined by the type of coded instruction it observes at any point on the string. Note that as each machine state “decodes” the string entry it is performing a recursive function. So if we can specify machine states that only perform actions which are similarly recursive functions, then the machine will be fully described with a sequence of recursive operations. That’s the intuition behind our next result.

We now proceed to (i) elaborate a machine language and the types of actions to be performed, then (ii) we show how each machine procedure can be coded, and finally (iii) that this model of computation can be characterised by recursive functions.

URM: The Machine Language

Our model of computation is based on the notion of Register Machines of Shepherdson and Sturgis. Specifically we use the notion of an unbounded register machine (URM) which takes variables of unbounded capacity from the natural numbers. Our alphabet is composed as follows:

$\leftarrow , + , \dot{-} , : , X , 0, 1, 2, 3, 4, 5, 6, 7, 8, 9$ if, else, goto, stop

We use the notion of iterative composition to enumerate infinite variables as required. So for instance a variable set:

$Var = \{ X1, X11, X111 .....X11111...1_{n} \}$

can be listed to ensure that each n-ary function has the appropriate number of inputs. For convenience however, we will follow Tourlakis and abstract over this representation to just write lowercase bold face variables $\textbf{x, y, z, ...etc }$ . Each of these variables can be set to have have values in the natural numbers, and it is in this manner that we expect our machine to operate on a string of variables. Once the appropriate variables have been “initialized” then our program can begin. Which programs you ask?

The beauty of this result stems in part from the sheer simplicity of the basic computational programs: We take five basic programs as follows: Let $L$ serve as the label for the appropriate machine state.

$L : \textbf{ x } \leftarrow a$
$L : \textbf{ x } \leftarrow \textbf{ x } + 1$
$L : \textbf{ x } \leftarrow \textbf{ x } \dot{-} 1$
$L :$ stop
$L :$ if $\textbf{ x } \leftarrow 0$ goto $q_{m}$ else goto $q_{n}$

So the idea here is that each machine state will enact an algorithm composed of a series of these operations, on a step by step basis with each step labeled $q_{1}, q_{2}, q_{3}, ...etc$ until either the program stops, or a new program begins because we have switched machine states. A machine state is a program which enacts an algorithm on particular initialised variables.

The first three functions are fairly self explanatory assignment functions, the fourth couldn’t be more simple. The fifth allows us to jump steps forward and backwards in a sequence so long as neither $q_{m}, q_{n}$ exceed $q_{t}$ the program for the stop command. In traditional Turing machines the add and proper subtraction functions could be simulated by erasing and printing additional numbers onto the input/output tape so as to alter the number coded, for instance, in Wang’s binary notation. The current method is more perspicuous and less arduous to depict.

URM: Coding the Machine

The process of coding an instruction for a machine is akin to the work of a compiler/interpreter. This is a program that takes strings of input in the syntax of our programming language, where each string encodes an instruction that once the machine “reads” the string it enacts the instruction directed.

On this understanding, we say that a computation begins when we initialise a set of variables in any sentence string, and then enact the coded instruction, until the computation ends as we have moved from an input $\textbf{ x }$ to the final state $\textbf{ f(x) }$ , the result of applying $f$ to $x$ . Given this stricture our compiler must be able to (1) identify the machine state and (2) read the instruction string and (3) know to act accordingly. As such each code will contain the input variable, the output value, the machine state and a value for the action their combination requires. We set up a coding schema as follows: Allow that $X1^{i}$ is an abbreviation for X followed by $i$ many $1s$ , then…

$L : X1^{i} \leftarrow a$ has the code $< 1*L*i*a>$
$L : X1^{i} \leftarrow x+1$ has the code $<2*L*i>$
$L : X1^{i} \leftarrow x \dot{-} 1$ has the code $<3*L*i>$
if $L : X1^{i} = 0$ goto $q_{i}$ else goto $q_{j}$ has the code $<4* L * i * q_{m}* q_{n} >$
$L :$ stop has the code $<5*L>$

So clearly we can see that each type of instruction string is categorized numerically by the first digit in the code string while we render the instruction unique by clearly delineating which step $( L )$ in the program the instruction defines, and the precise change ( $X1^{i}$ ± 1) the particular function impacts on the dependent variable. This coding allows us to represent instructions as numerical objects, thereby allowing them to be expressed in the language of first order arithmetic. The process is called the arithmetization of register machines. This allows us to define the existence of any URM machine in the language of recursive functions. We now make a slight digression regarding the expressivity of recursive functions.

The Expressivity of Recursive Functions

You may recall from here that we defined the class of recursive functions $\mathbb{R}$ as those primitive recursive functions $\mathbb{PR}$ closed under the operations of unbounded search. We now consider another definition which allows us to illustrate the relation between formal logic and recursion theory. Better, it allows us to set the scene for how definability in first order logic corresponds to enumerability of a recursive function.

Consider the notion of a characteristic function $\chi_{R}$ for a given first order definable relation $R$ , we say that the characteristic function works like a test for membership of the class $R$ for any $( \overrightarrow{x})$ in our first order universe when it returns true if $R$ holds of $( \overrightarrow{x})$ and false otherwise. So the characteristic function for the set of even numbers involves testing which of the natural numbers is divisible by two, where the characteristic function will return 1 if the number is even and o otherwise.

Now it’s plain to see that if the relation $R$ admits definition in terms of primitive recursive (recursive) functions then the function $\chi_{R}$ is also primitive recursive (recursive), because the test for membership is simply a result of a constant function composed with the sequence of p.r (recursive) functions used to define $R$ . Similarly, vice versa if $R$ is p.r (recursive) then so too is the characteristic function $\chi_{R}$ . Now, there is some technical work to be done regarding the definition of substitution over recursive functions, but the details are not very enlightening so we’ll skip them here. Assume such a substitution operation exists and note that the operation is itself recursive, then we can show that p.r. (recursive) predicates are closed under (i) the Boolean operations (ii) bounded search.

To show that $\mathbb{PR}$ is closed under negation, note that if $R(\overrightarrow{x}) \in \mathbb{PR}$ then we have $\chi_{R}$ , then $\chi_{\neg R} \in \mathbb{PR}$ since $\chi_{\neg R} = \lambda(\overrightarrow{x}).1\dot{-} \chi_{R}(\overrightarrow{x})$ which is in the set $\mathbb{PR}$ because proper subtraction and substitution are defined primitively recursively giving us $\lambda xy.x \dot{-} y \in \mathbb{PR}$

To show that $\mathbb{PR}$ is closed under disjunction simply assume $R(\overrightarrow{x}) Q(\overrightarrow{x}) \in \mathbb{PR}$ , then pick $\lambda \overrightarrow{x}, \overrightarrow{y}.\chi_{R \vee Q}(\overrightarrow{x}, \overrightarrow{y})$ as defined: $\chi_{R \vee Q}$ $\Leftrightarrow \text{ if } R(\overrightarrow{x}) \text{ then } 1, \text{ else } \chi_{Q}(\overrightarrow{y})$ , which is clearly in $\mathbb{PR}$ as desired.

To show that $\mathbb{PR}$ is closed under bounded search it suffices to show that we may define such search using the recursion theorem. We want to show that $\exists y_{y < z} (R(z, \overrightarrow{x}))$ . Assume $R(y, \overrightarrow{x}) \in \mathbb{PR}$ and let $Q(z, \overrightarrow{x}) : = \exists y_{< z}(R(y, \overrightarrow{x})$ , then the idea is to define a search which seeks “upward” towards z to determine at which point the relation $R(y, \overrightarrow{x})$ holds? We define the recursion equation as follows: First not that $Q(0, \overrightarrow{x})$ is always false since 0 is not strictly greater than any natural number. So…

$\chi_{Q}(0, \overrightarrow{x}) = 0$

$\chi_{Q}(z+1, \overrightarrow{x}) = \chi_{Q}(z, \overrightarrow{x}) \vee \chi_{R}(z, \overrightarrow{x})$

This completes the proof and demonstrates the expressivity of recursion theory in terms of first order classical languages. Now we return to our URM machines and show how each machine can be defined in terms of recursive functions in the first order language of arithmetic.

The First Order Definition of a URM

In this definition we liberally use shorthand notation for first order symbols where we feel it aids readability and we draw upon the decoding definitions for Godel coding discussed here. The idea is to express the arithmetized version of a URM machine as a sequence of instructions encoded as described above. Let z be the code of a URM machine and observe that:

$URM(z) \Leftrightarrow Seq(z) \wedge (z)_{lth(z) \dot{-}1} = <5, lth(z) > ...$ Penultimate Step encodes a halt …

$... \wedge \forall(i)_{< lth(z)}( i \neq lth(z)\dot{-} 1 \rightarrow ((z)_{i})_{0} \neq 5) ...$ None but the penultimate step encodes halts}

$....\wedge \forall L_{< lth(z)}$ $\Big[ (Seq((z)_{L}) \wedge ...$ Every program is the result of a sequence of actions, and…

$...\Big( \exists i, a \leq (z)_{L} = <1, L+1, i + 1, a > \vee ...$ Either L initialises variables, switches to L+1 or…

$... \exists i_{ \leq z} \Big( ((z)_{L} = <2, L+1, i+1 >)$ $\vee ((z)_{L} = <3, L+1, i+1 > )...$ it adds or subtracts 1, switches to L+1 …

$... \vee ( \exists q_{m}, q_{n})_{<lth(z)}(z)_{L}$ $= <4, L+1, i+1, q_{m+1}, q_{n+1} > \Big) \Big) \Big]$ … or changes program within the parameters of the halting condition.

Hence every URM program is first order definable, and so definable in terms of recursive functions since each disjunct can be captured in terms of characteristic functions or p.r relations. This complete the characterisation of a machine as desired.

The Definition of Computation

There is a little more work to be done in that now we have a machine. For instance in some cases we may want to only compute certain functions on particular selective candidate variables. So we would have to run a machine on a series of inputs and expect a certain kind of output when that “right” candidate is found. This requires that we use the notion unbounded search rendering all such URM machines recursive machines. Let $URM_{1}(z)$ denote the code of the abstract machine with one free variable. In short, we want to define a first order relation like:

$\mu x( URM_{1}(z) \wedge (R(x, w) \wedge COMP(z, x) = y))$

where x is the least input such that satisfies our specific condition. The details for defining COMP are a little messy but not unintuitive, the main work involves defining a “yield” relation between input and output states of any machine. In any case we shall leave the details out for the moment noting only that there is a famous theorem of Kleene that all such computations can be described in “normal form” as requiring only a single use of $\mu$ -recursion. We shall prove this another time. The key point of interest is that we have shown that all abstract machines can be expressed as recursive functions.

Completing the Squeezing Argument for Intuitive Algorithms

So far we have seen that (a) each recursive function can be thought of as effecting an intuitive step-wise algorithm and that (b) every abstract machine can simulated as a recursive function. Kleene further compounds this result by showing that any computation performed by an abstract machine is at most an instance of a recursive function. In fact this holds in the other direction too, every recursive function can be defined and then computed on an abstract machine . Think here about how to capture the primitive recursive functions in the syntax of URMs with loops, and assignment functions! The proof is by induction on the complexity of recursive functions, there is neat example of this in Peter Smith’s book on Godel’s incompleteness theorems.

But the real question is whether each intuitive algorithm can be computed by an abstract machine? If we can show that every intuitive algorithm can be performed by an abstract machine that would complete the circle. Thereby establishing the structure of a squeezing argument. First order logic would do the rest, so unless you’re some kind of logical deviant this should be persuasive. We consider the value of deviancy in the next post.

Aspiring PI

"An orgy of abstract informality" – reader review

Category Archives: Semantics