Decidability in argumentation semantics

Abstract

Much of the formal study of algorithmic concerns with respect to semantics for abstract argumentation frameworks has focused on the issue of computational complexity. In contrast matters regarding computability have been largely neglected. Recent trends in semantics have, however, started to concentrate not so much on the formulation of novel semantics but more on identifying common properties: for example, from basic ideas such as conflict-freeness through to quite sophisticated ideas such as serializability.

The aim of this paper is to look at the implications these more recent studies have for computability rather than computational complexity.

1. Introduction

Computational complexity, the focus of most formal work on algorithmic matters as these affect traditional semantics within abstract argumentation frameworks, see e.g. Dvorak and Dunne [3], addresses questions of limits on efficient solution methods. In this focus there is, usually unstated, an assumption that some form of solution method, i.e. algorithm, actually is possible. A far more fundamental concern, however, is that of computability: whether a given problem is capable of algorithmic solutions at all. Recently there has been an increasing interest in treatments of semantics through analysis of generic principle. Such work has its origins in Baroni and Giacomin [1]. In this, the central interest is not so much what makes a novel semantics distinct (and arguably useful) from previously proposed forms but rather on identifying features that all reasonable semantics ought to have in common. This approach raises a very general question: suppose we have some effective mechanism by which a semantics can be described, what is it possible in this case to say about recognising such properties computationally? The aim of the current paper is first formally to define this problem and then to establish some basic computational properties.

In some respects considering, in the context of abstract argumentation frameworks, questions such as “Is it possible to solve this problem (by an algorithm)?” rather than “Is it possible to solve this problem efficiently?” may seem strange. There are, however, good reasons for doing so. We can first note the historical significance of such questions: computability (or, as it is also referred to, recursive function theory) predates the first programmable computers by several decades: the question “Can this be solved algorithmically?” has a much longer history than its counterpart “Can this be solved by an efficient algorithm?”. Even if one accepts its historical importance, the possibility of unsolvable questions arising in the specific instance of argumentation frameworks seems unlikely and examples almost surely highly contrived and artificial: defined not so much as having a “real context” but more simply to demonstrate a point. Argumentation frameworks are directed graphs and treated, in all but a small body of work, as finite structures; in practical settings this finite aspect is always present. So if we are only concerned with the computational features of single finite objects then unsolvability is not a consideration: given a finite graph, an interpretable question about that graph’s properties (e.g. from “How many edges?” through to “What is the longest simple path between two nodes?”) we can always answer the question by an algorithmic method (albeit sometimes a rather lengthy one).

In summary, if questions of effective (as opposed to efficient) methods are going to arise, these will not be at the level of individual frameworks. Argumentation, however, has moved on from the realm of issues which can be related to a purely finite framework context. From its initial proposal, we have the concept of argument semantics as subsets of finite sets satisfying particular criteria. Here, again, we are still in a finite environment: semantics are sets of subsets, some subsets will meet the criteria and others will fail to do so. The core question becomes whether a given set meets the criteria with respect to a given framework. If this, the verification problem is computable then general issues of algorithmic solution do not arise since every question can be resolved, at worst, by explicit enumeration and piecemeal review of every subset. It is, of course, conceivable that “semantics” may be formulated in which such “list and check” methods would fail since the verification problem is itself undecidable. Yet, while imaginable as a mathematical conceit, it is hard to think of any such “semantics” arising in practice. Frameworks do not yield unsolvable questions, (practical) semantics (properties of frameworks), also fail to yield such problems. It is when we move one level higher, as is demonstrated in the present paper, and look at properties of semantics that computability becomes a non-trivial issue. Properties of classes of semantics (from the “principle based” proposal of Baroni and Giacomin [1] onwards) have proven to be an important simplification in shifting interest from a justification of novel approaches through “other proposals can’t do this” to “this approach has all of the benefits of earlier ideas and it can do this”. The principle-based analysis offers a subtle but significant direction in which novel semantics are treated. It is in this move from frameworks to properties of frameworks to properties of properties of frameworks that non-computability arises. One might ask, being aware of this issue, why computability should matter: mathematicians, after all, continue their efforts despite the implications of Gödel’s work. To be aware of the possibility of non-computability may avoid efforts to automate that which provably cannot be automated: for example, we cannot develop an algorithm that given a description of a semantics will determine whether that semantics respects the conflict-freeness principle.

The shifting from frameworks and semantics to properties of semantics does, however, raise one issue: how do we represent a property e.g. conflict-freeness in computational terms. Frameworks are directed graphs and their semantics, according to the criteria used, simply subsets of their arguments. Now it is certainly possible to enumerate all frameworks and their corresponding, say conflict-free sets. In studying computational properties of principles we need to capture an infinite range of possibilities by a finite form. The mechanisms that are needed to do so are, ultimately, those that lead to questions such as “Does this semantics σ respect this principle π?” being incapable of algorithmic solution.

The consequences of viewing properties of semantics from a computational perspective go further than basic uncomputability. If we consider the classical undecidable computational problem, The Halting Problem of Turing [7], which considers if encodings of programs will come to a halt on a given input, although undecidable in the sense that no algorithm exists which is guaranteed always to give a correct response in a finite time, there is at least a “partial decision method”: one which will recognise all positive instances. This is simply to simulate the program on its given input and report accept should this simulation end. For the classification of semantics we do not even have such partial decision methods: there is no effective algorithm guaranteed to recognise all positive (or all negative) instances. In formal language while cases such as The Halting Problem are recursively enumerable (although not recursive) natural semantic properties such as conflict-freeness fail even to be recursively enumerable.

We give preliminary background in Section 2. We assume the reader has some acquaintance with the concept of Model of Computation as captured by, among others, Turing Machines, Post Machines etc. Excellent introductory background concerning these may be found in Hopcroft, Motwani and Ullman [4] with more advanced discussion in Hopcroft and Ullman [5].

In Section 3 we present one method of encoding an argument framework and collection of subsets of its argument as a finite length binary sequence. Results are given in Section 5 and Section 6 with conclusions in Section 7.

2. Preliminaries

Definition 1 (Dung [2]).

An argumentation framework (af) is a pair $\mathrm{(}\mathcal{X}\mathrm{,}\mathcal{A}\mathrm{)}$ where $\mathcal{X}$ is a finite set of entities, called arguments, and $\mathcal{A}$ a binary relation on $\mathcal{X}$ . For any $\mathit{p}\mathrm{,}\mathit{q}\in \mathcal{X}$ we say that p attacks q if $⟨\mathit{p}\mathrm{,}\mathit{q}⟩\in \mathcal{A}$ .

We use the shorthand $\mathcal{H}$ for an arbitrary framework $\mathrm{(}\mathcal{X}\mathrm{,}\mathcal{A}\mathrm{)}$ where the argument and attack set are implicit.

Definition 2.

Let $\mathcal{H}$ be an argumentation framework, $\mathit{x}\in \mathcal{X}$ and $\mathit{S}\subseteq \mathcal{X}$ . We define ${\{\mathit{x}\}}^{+}$ as $\{\mathit{y}\in \mathcal{X}|\mathit{x}\text{ attacks }\mathit{y}\}$ , ${\{\mathit{x}\}}^{-}$ as $\{\mathit{y}\in \mathcal{X}|\mathit{y}\text{ attacks }\mathit{x}\}$ , ${\mathit{S}}^{+}$ as $\cup \{{\{\mathit{x}\}}^{+}|\mathit{x}\in \mathcal{X}\}$ , and ${\mathit{S}}^{-}$ as $\cup \{{\{\mathit{x}\}}^{-}|\mathit{x}\in \mathcal{X}\}$ . The set S is said to be conflict-free if $\mathit{S}\cap {\mathit{S}}^{+}=\varnothing$ . A set S is said to defend x iff ${\{\mathit{x}\}}^{-}\subseteq {\mathit{S}}^{+}$ . The characteristic function $\mathcal{F}:2^{\mathcal{X}}\to 2^{\mathcal{X}}$ is defined as $\mathcal{F}\mathrm{(}\mathit{S}\mathrm{)}=\{\mathit{x}|\mathit{S}\text{ defends }\mathit{x}\}$ .

Definition 3.

Let $\mathcal{H}$ be an argumentation framework. A subset S of $\mathcal{X}$ is said to be:

an admissible set if S is conflict-free and $\mathit{S}\subseteq \mathcal{F}\mathrm{(}\mathit{S}\mathrm{)}$

a complete extension if S is conflict-free and $\mathit{S}=\mathcal{F}\mathrm{(}\mathit{S}\mathrm{)}$

a grounded extension if S is the smallest (w.r.t. ⊆) complete extension

a preferred extension if S is a maximal (w.r.t. ⊆) complete extension

For σ an arbitrary semantics (e.g. conflict-free, preferred, complete) the notation $\mathit{\sigma }\mathrm{(}\mathcal{H}\mathrm{)}$ describes $$\begin{array}{c}\mathit{\sigma }\mathrm{(}\mathcal{H}\mathrm{)}=\{\mathit{S}\subseteq \mathcal{X}:\mathit{S}\text{ satisfies the constraints specified by }\mathit{\sigma }\}\end{array}$$

It will be helpful to use the shorthand ${\mathit{E}}_{\mathit{\sigma }}\mathrm{(}\mathcal{H}\mathrm{,}\mathbb{S}\mathrm{)}$ with $\mathbb{S}\subseteq 2^{\mathcal{X}}$ for the predicate which takes the value ⊤ whenever $\mathbb{S}=\mathit{\sigma }\mathrm{(}\mathcal{H}\mathrm{)}$ . It is well known (as shown in Dung’s original paper [2]) that for any af, $\mathcal{H}$ , $$\begin{array}{c}pr\mathrm{(}\mathcal{H}\mathrm{)}\subseteq adm\mathrm{(}\mathcal{H}\mathrm{)}\subseteq cf\mathrm{(}\mathcal{H}\mathrm{)}\end{array}$$

A number of general principles for argumentation semantics have been presented in Baroni and Giacomin [1]. Among these are

A semantics σ respects τ if $$\begin{array}{c}\forall \mathcal{H}\mathit{S}\in \mathit{\sigma }\mathrm{(}\mathcal{H}\mathrm{)}\Rightarrow \mathit{S}\in \mathit{\tau }\mathrm{(}\mathcal{H}\mathrm{)}\end{array}$$

We also have (in addition to the concept “a semantics σ respects a semantics τ”) that of a semantics σ respecting a principle π. For example, σ respects reinstatement if $$\begin{array}{c}\forall \mathcal{H}\mathit{S}\in \mathit{\sigma }\mathrm{(}\mathcal{H}\mathrm{)}\text{ if }\forall \mathit{y}\in {\{\mathit{x}\}}^{-}\text{ it holds that }\mathit{y}\in {\mathit{S}}^{+}\text{ then }\mathit{x}\in \mathit{S}\end{array}$$

Definition 4.

An alphabet, Σ is a finite set of symbols, ${\mathrm{\Sigma }}^{\ast }$ denotes the set of all finite length sequences of symbols (words) from Σ (including ε the empty word). A language, L over Σ is a subset of ${\mathrm{\Sigma }}^{\ast }$ . The complement of a language L, denoted $\mathrm{coL}$ , is the language ${\mathrm{\Sigma }}^{\ast }\setminus \mathit{L}$ . A language is recursively enumerable (r.e.) (also called partially decidable) if there is a program, M, taking as an input $\mathit{w}\in {\mathrm{\Sigma }}^{\ast }$ and which halts and accepts w whenever $\mathit{w}\in \mathit{L}$ . A language is recursive (or decidable) if both L and $\mathrm{coL}$ are r.e.

Since we may encode Turing Machine programs, M, as words $\mathit{\chi }\mathrm{(}\mathit{M}\mathrm{)}\in {\{0\mathrm{,}1\}}^{\ast }$ (see for example, Hopcroft and Ullman [5, pp. 181–2]) we can define the set of all r.e. languages by $$\begin{array}{c}\mathrm{RE}=\{\mathit{\chi }\mathrm{(}\mathit{M}\mathrm{)}:\mathit{M}\text{ is a Turing machine program}\}\end{array}$$ For a given program, M taking inputs from ${\{0\mathrm{,}1\}}^{\ast }$ , $\mathit{L}\mathrm{(}\mathit{M}\mathrm{)}$ is the subset of ${\{0\mathrm{,}1\}}^{\ast }$ on which M will halt and report accept.

We can introduce the concept of property of a language simply via the set of Turing machine programs that accept languages with the property. That is if Π is some property (e.g. empty, infinite, contains only odd length words, etc) then $\mathrm{\Pi }\subseteq \mathrm{RE}$ .

3. Encodings in binary and their consequences

A device which we make extensive use of can be summarised in the following terms: we have a set of objects, $\mathbb{O}$ ; we wish, uniquely, to describe these as words over $\{0\mathrm{,}1\}$ . Since we can order the words in ${\{0\mathrm{,}1\}}^{\ast }$ (e.g. use standard lexicographic ordering and the convention $0\prec 1$ ) we can use such an ordering precisely to define “the first object in $\mathbb{O}$ ”, “the second object in $\mathbb{O}$ ” and generally the k’th object in $\mathbb{O}$ : go through the words in ${\{0\mathrm{,}1\}}^{\ast }$ in order, the first such word that describes a valid encoding will define the “first” object. In general the k’th word discovered that defines a valid encoding will be the k’th object. We thus have total functions over $\mathbb{N}$ and $\mathbb{O}$ : $$\begin{array}{l}{\mathrm{enc}}^{\mathbb{O}}:\mathbb{O}\to \mathbb{N};{\mathrm{dec}}^{\mathbb{O}}:\mathbb{N}\to \mathbb{O}\\ {enc}^{\mathbb{O}}\mathrm{(}\mathit{\omega }\mathrm{)}=\mathit{k}\text{with}{dec}^{\mathbb{O}}\mathrm{(}\mathit{k}\mathrm{)}=\mathit{\omega }\\ {dec}^{\mathbb{O}}\mathrm{(}\mathit{k}\mathrm{)}={\mathit{\omega }}_{\mathit{k}}\in \mathbb{O}\text{the encoding of }{\mathit{\omega }}_{\mathit{k}}\text{ in }{\{0\mathrm{,}1\}}^{\ast }\text{ is the }\mathit{k}\text{’th valid coding word in the ordering}\end{array}$$ Notice that, $$\begin{array}{c}{dec}^{\mathbb{O}}\mathrm{(}{enc}^{\mathbb{O}}\mathrm{(}\mathit{\omega }\mathrm{)}\mathrm{)}=\mathit{\omega };{enc}^{\mathbb{O}}\mathrm{(}{dec}^{\mathbb{O}}\mathrm{(}\mathit{k}\mathrm{)}\mathrm{)}=\mathit{k}\end{array}$$ Such schemes allow us to treat properties of structures as functions over $\mathbb{N}$ .

As a simple example, consider the set $$\begin{array}{c}\mathrm{EP}=\{\mathrm{(}\mathit{p}\mathrm{,}\mathit{q}\mathrm{)}:\text{Both }\mathit{p}\text{ and }\mathit{q}\text{ are even Natural numbers}\}\end{array}$$ So that, $$\begin{array}{c}\mathrm{EP}=\{\mathrm{(}2\mathrm{,}2\mathrm{)}\mathrm{,}\mathrm{(}2\mathrm{,}4\mathrm{)}\mathrm{,}\mathrm{(}4\mathrm{,}2\mathrm{)}\mathrm{,}\mathrm{(}2\mathrm{,}6\mathrm{)}\mathrm{,}\mathrm{(}4\mathrm{,}4\mathrm{)}\mathrm{,}\mathrm{(}6\mathrm{,}2\mathrm{)}\mathrm{,}\mathrm{(}2\mathrm{,}8\mathrm{)}\mathrm{,}\mathrm{(}4\mathrm{,}6\mathrm{)}\mathrm{,}\mathrm{(}6\mathrm{,}4\mathrm{)}\mathrm{,}\mathrm{(}8\mathrm{,}2\mathrm{)}\mathrm{,}\dots \}\end{array}$$ We can write $\mathrm{(}\mathit{p}\mathrm{,}\mathit{q}\mathrm{)}\in \mathrm{EP}$ as $0^{\mathit{p}}{10}^{\mathit{q}}$ and hence ${enc}^{\mathrm{EP}}\mathrm{(}\mathrm{(}2\mathrm{,}2\mathrm{)}\mathrm{)}=1$ since 00100 is the first word (in lexicographic order) that encodes an element of $\mathrm{EP}$ . Similarly ${dec}^{\mathrm{EP}}\mathrm{(}6\mathrm{)}=000000100$ , i.e. the pair $\mathrm{(}6\mathrm{,}2\mathrm{)}\in \mathrm{EP}$

3.1. Argument frameworks $\mathcal{H}$

Since the names of arguments are unimportant it is only needed to describe the number of these. If $|\mathcal{X}|=\mathit{n}$ , then $\mathcal{X}$ is described by the word $1^{\mathit{n}}$ (i.e. a sequence of n 1s). This is followed by 00 to indicate that the next section of the encoding describes $\mathcal{A}$ . An attack $⟨{\mathit{x}}_{\mathit{i}}\mathrm{,}{\mathit{x}}_{\mathit{j}}⟩$ is an ordered pair with $1⩽\mathit{i}\mathrm{,}\mathit{j}⩽\mathit{n}$ , hence we can encode such as $1^{\mathit{i}}{01}^{\mathit{j}}$ separating distinct attacks with the sequence 00 and using the sequence 000 to indicate the end.

For example the af, $$\begin{array}{c}\mathrm{(}\{{\mathit{x}}_1\mathrm{,}{\mathit{x}}_2\mathrm{,}{\mathit{x}}_3\}\mathrm{,}\{⟨{\mathit{x}}_1\mathrm{,}{\mathit{x}}_2⟩\mathrm{,}⟨{\mathit{x}}_2\mathrm{,}{\mathit{x}}_3⟩\mathrm{,}⟨{\mathit{x}}_2\mathrm{,}{\mathit{x}}_1⟩\mathrm{,}⟨{\mathit{x}}_3\mathrm{,}{\mathit{x}}_1⟩\left\}\mathrm{\right)}\end{array}$$ would be coded as 111001011001101110011010011101000.

In order to ensure uniqueness attacks are described with increasing order of source and increasing order of target for attacks with the same source.

3.2. Frameworks and sets of subsets of arguments, $\mathrm{(}\mathcal{H}\mathrm{,}\mathbb{S}\mathrm{)}$ with $\mathbb{S}\subseteq 2^{\mathcal{X}}$

Let $\mathbb{A}$ denote the set of all objects $\mathrm{(}\mathcal{H}\mathrm{,}\mathbb{S}\mathrm{)}$ with $\mathbb{S}\subseteq 2^{\mathcal{X}}$ .

We have the scheme used for afs above. Noting that $\mathbb{S}$ is a list of some set of subsets of $\mathcal{X}$ . Following the 000 indicating the final attack in $\mathcal{A}$ for $\{{\mathit{x}}_{{\mathit{i}}_1}\mathrm{,}{\mathit{x}}_{{\mathit{i}}_2}\mathrm{,}\dots \mathrm{,}{\mathit{x}}_{{\mathit{i}}_{\mathit{k}}}\}$ an arbitrary set in $\mathbb{S}$ with the convention that the indices are given in increasing order. We use $1^{{\mathit{i}}_1}{01}^{{\mathit{i}}_2}\cdots 1^{{\mathit{i}}_{\mathit{k}}}$ to code it. Sets are presented in increasing order of size and increasing value of argument index (sets of the same size being ordered lexicographically using the indices of members, e.g. $\{{\mathit{x}}_2\}$ before $\{{\mathit{x}}_5\}$ , $\{{\mathit{x}}_1\mathrm{,}{\mathit{x}}_4\}$ before $\{{\mathit{x}}_2\mathrm{,}{\mathit{x}}_3\}$ etc.)

Distinct sets in $\mathbb{S}$ are separated by 00 and the end of the list by 000. For example to describe the system $\mathbb{S}=\{\varnothing \mathrm{,}\{{\mathit{x}}_1\}\mathrm{,}\{{\mathit{x}}_3\}\mathrm{,}\{{\mathit{x}}_2\mathrm{,}{\mathit{x}}_3\}\}$ we would have 0010011100110111000. With the example we would encode the system as $$\begin{array}{c}11100101100110111001101001110100000100110111000\end{array}$$ Note that the empty set in $\mathbb{S}$ is expressed as 000 (end of attack list token) immediately followed by 00 (next set in $\mathbb{S}$ token). We also note the distinction $\mathit{S}=\{\varnothing \}$ encoded as $1^{|\mathcal{X}|}00code\mathrm{(}\mathcal{A}\mathrm{)}00000000$ (that is end of $\mathcal{A}$ code 000; content of empty set 00; end of $\mathbb{S}$ code 000) and $\mathbb{S}=\varnothing$ coded as $1^{|\mathcal{X}|}00code\mathrm{(}\mathcal{A}\mathrm{)}000000$ .

For the pair $\mathrm{(}\mathcal{H}\mathrm{,}\mathbb{S}\mathrm{)}$ we use $\mathit{\mu }\mathrm{(}\mathcal{H}\mathrm{,}\mathbb{S}\mathrm{)}\in {\{0\mathrm{,}1\}}^{\ast }$ to denote its (unique) encoding as a binary word.

3.3. Power set constructions

Define the power set iteration operation, ${\mathbb{D}}^{\mathrm{(}\mathit{k}\mathrm{)}}$ for $\mathit{k}⩾0$ applied to a (finite) set, S, as $$\begin{array}{c}{\mathbb{D}}^{\mathrm{(}\mathit{k}\mathrm{)}}\mathrm{(}\mathit{S}\mathrm{)}=\left\{\begin{array}{cc}\mathit{S}\hfill & \text{if }\mathit{k}=0\hfill \\ 2^{{\mathbb{D}}^{\mathrm{(}\mathit{k}-1\mathrm{)}}\mathrm{(}\mathit{S}\mathrm{)}}\hfill & \text{if }\mathit{k}⩾1\hfill \end{array}\right.\end{array}$$ Hence ${\mathbb{D}}^{\mathrm{(}0\mathrm{)}}\mathrm{(}\mathit{S}\mathrm{)}\mathrm{,}{\mathbb{D}}^{\mathrm{(}1\mathrm{)}}\mathrm{(}\mathit{S}\mathrm{)}\mathrm{,}{\mathbb{D}}^{\mathrm{(}2\mathrm{)}}\mathrm{(}\mathit{S}\mathrm{)}\mathrm{,}\dots$ are successively S itself, the set of all subsets of S, the set of all subsets of the set of all subsets of S, and so on (more tersely S, $2^{\mathit{S}}$ , $2^{2^{\mathit{S}}}$ ).

Lemma 1.

For any finite S and $\mathit{k}⩾1$ there is a total computable mapping $$\begin{array}{c}{\mathit{\eta }}^{\mathrm{(}\mathit{k}\mathrm{)}}:{\mathbb{D}}^{\mathrm{(}\mathit{k}\mathrm{)}}\mathrm{(}\mathit{S}\mathrm{)}\leftrightarrow [0\mathrm{,}1\mathrm{,}2\mathrm{,}\dots \mathrm{,}|{\mathbb{D}}^{\mathrm{(}\mathit{k}\mathrm{)}}\mathrm{(}\mathit{S}\mathrm{)}|-1]\end{array}$$

Proof.

First note that $|{\mathbb{D}}^{\mathrm{(}\mathit{k}\mathrm{)}}\mathrm{(}\mathit{S}\mathrm{)}|=2^{|{\mathbb{D}}^{\mathrm{(}\mathit{k}-1\mathrm{)}}\mathrm{(}\mathit{S}\mathrm{)}|}$ . Order the sets in ${\mathbb{D}}^{\mathrm{(}\mathit{k}-1\mathrm{)}}\mathrm{(}\mathit{S}\mathrm{)}$ by increasing size (and “lexicographically” for sets of the same size). Consider the binary encoding of any whole number, w, with $0⩽\mathit{w}⩽|{\mathbb{D}}^{\mathrm{(}\mathit{k}\mathrm{)}}\mathrm{(}\mathit{S}\mathrm{)}|-1$ . We can use the value (0 or 1) of the ith bit to describe the presence (1) or absence (0) of the ith set in ${\mathbb{D}}^{\mathrm{(}\mathit{k}-1\mathrm{)}}\mathrm{(}\mathit{S}\mathrm{)}$ when describing a member of ${\mathbb{D}}^{\mathrm{(}\mathit{k}\mathrm{)}}\mathrm{(}\mathit{S}\mathrm{)}$ . Thus the whole number 0 describes the empty set (binary encoding as a string of $|{\mathbb{D}}^{\mathrm{(}\mathit{k}-1\mathrm{)}}\mathrm{(}\mathit{S}\mathrm{)}|$ 0s) while the whole number $|{\mathbb{D}}^{\mathrm{(}\mathit{k}\mathrm{)}}\mathrm{(}\mathit{S}\mathrm{)}|-1$ describes the set containing all members of ${\mathbb{D}}^{\mathrm{(}\mathit{k}-1\mathrm{)}}\mathrm{(}\mathit{S}\mathrm{)}$ (binary encoding as a string of $|{\mathbb{D}}^{\mathrm{(}\mathit{k}-1\mathrm{)}}\mathrm{(}\mathit{S}\mathrm{)}|$ 1s).

It should be clear that given any S, $\mathit{k}⩾1$ and $\mathit{U}\in {\mathbb{D}}^{\mathrm{(}\mathit{k}\mathrm{)}}\mathrm{(}\mathit{S}\mathrm{)}$ we form ${\mathit{\eta }}^{\mathrm{(}\mathit{k}\mathrm{)}}\mathrm{(}\mathit{U}\mathrm{)}$ and from any S, $\mathit{k}⩾1$ and $0⩽\mathit{u}⩽|{\mathbb{D}}^{\mathrm{(}\mathit{k}\mathrm{)}\mathrm{(}\mathit{S}\mathrm{)}}|-1$ recover ${\mathit{\eta }}^{{\mathrm{(}\mathit{k}\mathrm{)}}^{-1}}\mathrm{(}\mathit{u}\mathrm{)}$ the corresponding member of ${\mathbb{D}}^{\mathrm{(}\mathit{k}\mathrm{)}}\mathrm{(}\mathit{S}\mathrm{)}$ . □

Now it is not hard to see that we can also think in terms of numerical properties via functions, $\mathit{f}:\mathbb{N}\to \mathbb{N}$ . For example $\mathrm{♯}\mathrm{cf}:\mathbb{N}\to \mathbb{N}$ describes “the number of conflict-free sets in ${dec}^{\mathrm{(}\mathbb{A}\mathrm{)}}\mathrm{(}\mathit{n}\mathrm{)}$ ”.

We develop this notion more precisely in the next section.

4. Languages, predicates, and argument semantics

We have described a language L as a set of words over a finite alphabet (often $\mathrm{\Sigma }=\{0\mathrm{,}1\}$ ).

We have predicates, p, whose domain we consider to be the Natural numbers, $\mathbb{N}$ .

An argument semantics, σ, we treat as a set of pairs $\mathrm{(}\mathcal{H}\mathrm{,}\mathbb{S}\mathrm{)}$ with $\mathcal{H}$ an af and $\mathbb{S}\subseteq 2^{\mathcal{X}}$ so that $\mathit{\sigma }\mathrm{(}\mathcal{H}\mathrm{)}=\mathbb{S}$ , or equivalently that ${\mathit{E}}_{\mathit{\sigma }}\mathrm{(}\mathcal{H}\mathrm{,}\mathbb{S}\mathrm{)}$ holds.

Superficially these may seem to be three quite distinct formalisms. One of the gains of the encoding mechanisms described in the previous section is in demonstrating that all are equivalent: we can treat a language, L, as a predicate ${\mathit{p}}_{\mathit{L}}$ or argument semantics ${\mathit{\sigma }}_{\mathit{L}}$ ; we can go in the opposite direction and formulate from a predicate, p, languages over single character alphabets, ${\mathit{L}}_{\mathit{p}}^{\mathrm{(}\mathbb{N}\mathrm{)}}$ and argument semantics ${\mathit{\sigma }}_{\mathit{p}}^{\mathrm{(}\mathbb{N}\mathrm{)}}$ . Finally we may move from an argument semantics, σ, to languages ${\mathit{L}}_{\mathit{\sigma }}$ or predicates ${\mathit{p}}_{\mathit{\sigma }}$ . The fact that encoding schemes over some collection of objects, $\mathbb{O}$ can be ordered is a key tool here.

The purpose of this section is to describe these translations and introduce the notational conventions used in Section 5.

4.1. Languages to predicates and semantics

Let $\mathrm{lex}:{\{0\mathrm{,}1\}}^{\ast }\to \mathbb{N}$ be the usual lexicographic ordering (with $0\prec 1$ )

Suppose $\mathit{L}\subseteq {\{0\mathrm{,}1\}}^{\ast }$ . The predicate ${\mathit{p}}_{\mathit{L}}:\mathbb{N}\to \{\top \mathrm{,}\perp \}$ has $$\begin{array}{c}{\mathit{p}}_{\mathit{L}}\mathrm{(}\mathit{n}\mathrm{)}=\top \iff {lex}^{-1}\mathrm{(}\mathit{n}\mathrm{)}\in \mathit{L}\end{array}$$ The argument semantics, ${\mathit{\sigma }}_{\mathit{L}}$ is described by $$\begin{array}{c}\mathit{w}\in \mathit{L}\iff {\mathit{E}}_{{\mathit{\sigma }}_{\mathit{L}}}\mathrm{\left(}{dec}^{\mathrm{(}\mathbb{A}\mathrm{)}}\mathrm{\right(}lex\mathrm{(}\mathit{w}\mathrm{)}\mathrm{\left)}\mathrm{\right)}=\top \end{array}$$

4.2. Predicates to languages and semantics

Given $\mathit{p}:\mathbb{N}\to \{\top \mathrm{,}\perp \}$ the language, ${\mathit{L}}_{\mathit{p}}^{\mathrm{(}\mathbb{N}\mathrm{)}}\subseteq {\{1\}}^{\ast }$ corresponding to it has $$\begin{array}{c}{\mathit{L}}_{\mathit{p}}^{\mathrm{(}\mathbb{N}\mathrm{)}}=\{1^{\mathit{n}}:\mathit{p}\mathrm{(}\mathit{n}\mathrm{)}=\top \}\end{array}$$ The argument semantics ${\mathit{\sigma }}_{\mathit{p}}^{\mathrm{(}\mathbb{N}\mathrm{)}}$ has $$\begin{array}{c}{\mathit{E}}_{{\mathit{\sigma }}_{\mathit{p}}^{\mathrm{(}\mathbb{N}\mathrm{)}}}\mathrm{(}\mathcal{H}\mathrm{,}\mathbb{S}\mathrm{)}=\top \iff \mathit{p}\mathrm{(}{enc}^{\mathrm{(}\mathbb{A}\mathrm{)}}\mathrm{(}\mathcal{H}\mathrm{,}\mathbb{S}\mathrm{)}\mathrm{)}=\top \end{array}$$

4.3. Semantics to languages and predicates

If σ is an argument semantics the language ${\mathit{L}}_{\mathit{\sigma }}\subseteq {\{0\mathrm{,}1\}}^{\ast }$ is $$\begin{array}{c}{\mathit{L}}_{\mathit{\sigma }}=\{\mathit{\mu }\mathrm{(}\mathcal{H}\mathrm{,}\mathbb{S}\mathrm{)}:{\mathit{E}}_{\mathit{\sigma }}\mathrm{(}\mathcal{H}\mathrm{,}\mathbb{S}\mathrm{)}=\top \}\end{array}$$ The predicate ${\mathit{p}}_{\mathit{\sigma }}$ has $$\begin{array}{c}{\mathit{p}}_{\mathit{\sigma }}\mathrm{(}\mathit{n}\mathrm{)}=\top \iff {\mathit{E}}_{\mathit{\sigma }}\mathrm{(}{dec}^{\mathrm{(}\mathbb{A}\mathrm{)}}\mathrm{(}\mathit{n}\mathrm{)}\mathrm{)}=\top \end{array}$$

4.4. Summary

A semantics, σ, has an associated predicate ${\mathit{E}}_{\mathit{\sigma }}:\mathbb{A}\to \{\top \mathrm{,}\perp \}$ so that ${\mathit{E}}_{\mathit{\sigma }}\mathrm{(}\mathcal{H}\mathrm{,}\mathbb{S}\mathrm{)}\iff \mathbb{S}=\mathit{\sigma }\mathrm{(}\mathcal{H}\mathrm{)}$ .

A semantics, σ, is described by a predicate, ${\mathit{\sigma }}^{\mathrm{(}\mathbb{N}\mathrm{)}}:\mathbb{N}\to \{\top \mathrm{,}\perp \}$ for which ${\mathit{\sigma }}^{\mathrm{(}\mathbb{N}\mathrm{)}}\mathrm{(}\mathit{n}\mathrm{)}\iff {\mathit{E}}_{\mathit{\sigma }}\mathrm{(}{dec}^{\mathrm{(}\mathbb{A}\mathrm{)}}\mathrm{(}\mathit{n}\mathrm{)}\mathrm{)}$ .

A predicate $\mathit{p}:\mathbb{N}\to \{\top \mathrm{,}\perp \}$ has an associated semantics ${\mathit{\sigma }}_{\mathit{p}}$ for which $\mathit{p}\mathrm{(}\mathit{n}\mathrm{)}\iff {\mathit{E}}_{{\mathit{\sigma }}_{\mathit{p}}}\mathrm{(}{dec}^{\mathrm{(}\mathbb{A}\mathrm{)}}\mathrm{(}\mathit{n}\mathrm{)}\mathrm{)}$ .

Predicates, $\mathit{q}:\mathbb{N}\to \{\top \mathrm{,}\perp \}$ (regardless of their source) are languages, ${\mathit{L}}_{\mathit{q}}$ , of finite length single character words so that ${\mathit{L}}_{\mathit{q}}=\{1^{\mathit{n}}:\mathit{q}\mathrm{(}\mathit{n}\mathrm{)}=\top \}$ .

5. Decidability in argumentation semantics

In looking at properties of semantics from a computational perspective we would like these to have some desirable features, One such is given by the concept of verifiability.

A semantics, σ, is verifiable if there is a program, M, that given $\mathit{\mu }\mathrm{(}\mathcal{H}\mathrm{,}\{\mathit{S}\}\mathrm{)}$ as input behaves as follows:

M checks that its input is valid, i.e. describes an af $\mathcal{H}$ and a subset S of $\mathcal{X}$ , rejecting if this is not the case.

M checks $\mathit{S}\in \mathit{\sigma }\mathrm{(}\mathcal{H}\mathrm{)}$ and rejects if $\mathit{S}\notin \mathit{\sigma }\mathrm{(}\mathcal{H}\mathrm{)}$ .

Theorem 1.

Let σ be a verifiable semantics. The language $$\begin{array}{c}{\mathit{L}}_{\mathit{\sigma }}=\{\mathit{\mu }\mathrm{(}\mathcal{H}\mathrm{,}\mathbb{S}\mathrm{)}:{\mathit{E}}_{\mathit{\sigma }}\mathrm{(}\mathcal{H}\mathrm{,}\mathbb{S}\mathrm{)}=\top \}\end{array}$$ is recursive.

Proof.

Consider the program, ${\mathit{M}}_{\mathit{\sigma }}$ that does the following on input $\mathit{w}\in {\{0\mathrm{,}1\}}^{\ast }$ .

${\mathit{M}}_{\mathit{\sigma }}$ checks $\mathit{w}=\mathit{\mu }\mathrm{(}\mathcal{H}\mathrm{,}\mathbb{S}\mathrm{)}$ with $\mathbb{S}\in {\mathbb{D}}^{\mathrm{(}2\mathrm{)}}\mathrm{(}\mathcal{X}\mathrm{)}$ rejecting if this is not the case.

For each $\mathit{S}\in \mathbb{S}$ , ${\mathit{M}}_{\mathit{\sigma }}$ verifies $\mathit{S}\in \mathit{\sigma }\mathrm{(}\mathcal{H}\mathrm{)}$ rejecting if any $\mathit{S}\notin \mathit{\sigma }\mathrm{(}\mathcal{H}\mathrm{)}$ is found.

For each $\mathit{S}\in {\mathbb{D}}^{\mathrm{(}1\mathrm{)}}\mathrm{(}\mathcal{X}\mathrm{)}\setminus \mathbb{S}$ , ${\mathit{M}}_{\mathit{\sigma }}$ verifies $\mathit{S}\notin \mathit{\sigma }\mathrm{(}\mathcal{H}\mathrm{)}$ rejecting if any $\mathit{S}\in \mathit{\sigma }\mathrm{(}\mathcal{H}\mathrm{)}$ is found.

If all of the tests in (1)–(3) succeed then ${\mathit{M}}_{\mathit{\sigma }}$ accepts.

The program ${\mathit{M}}_{\mathit{\sigma }}$ will accept any $\mathrm{(}\mathcal{H}\mathrm{,}\mathbb{S}\mathrm{)}$ with ${\mathit{E}}_{\mathit{\sigma }}\mathrm{(}\mathcal{H}\mathrm{,}\mathbb{S}\mathrm{)}=\top$ and reject any $\mathrm{(}\mathcal{H}\mathrm{,}\mathbb{S}\mathrm{)}$ with ${\mathit{E}}_{\mathit{\sigma }}\mathrm{(}\mathcal{H}\mathrm{,}\mathbb{S}\mathrm{)}=\perp$ hence ${\mathit{L}}_{\mathit{\sigma }}$ is recursive. □

The notion of “semantic properties”, as promoted in the principle-based concepts of Baroni and Giacomin [1], becomes rather more complicated. Suppose we have some property, π. We wish to formulate the question “does a semantics σ respect property π?” in computational terms, i.e. as a language of finite words.

We have shown in the previous section that any argumentation semantics describes a predicate over $\mathbb{N}$ and such predicates define languages of words from a single character alphabet. In computational terms, we can therefore focus on the computation of languages, $\mathit{L}\subseteq {\{1\}}^{\ast }$ . Each such language offers an (admittedly usually highly artificial) argumentation semantics; every argumentation semantics (in the sense we have defined these) describes such a language. In computational terms we would only be interested in verifiable semantics, that is to say those for which the associated single character language, ${\mathit{L}}_{{\mathit{\sigma }}^{\mathrm{(}\mathbb{N}\mathrm{)}}}$ has a Turing Machine program, ${\mathit{M}}_{\mathit{\sigma }}$ which recognises $$\begin{array}{c}{\mathit{L}}_{{\mathit{\sigma }}^{\mathrm{(}\mathbb{N}\mathrm{)}}}=\{1^{\mathit{n}}:{\mathit{E}}_{\mathit{\sigma }}\mathrm{(}{dec}^{\mathrm{(}\mathbb{A}\mathrm{)}}\mathrm{(}\mathit{n}\mathrm{)}\mathrm{)}=\top \}\end{array}$$ We can code these Turing machine programs in binary and order these codes. In summary, a semantics property, π, is $$\begin{array}{c}{\mathit{L}}_{\mathrm{\Pi }}=\{\mathit{\chi }\mathrm{(}\mathit{M}\mathrm{)}:\mathit{L}\mathrm{(}\mathit{M}\mathrm{)}\subseteq {\{1\}}^{\ast }\text{ and }{\mathit{\sigma }}_{\mathit{L}}\text{ respects }\mathit{\pi }\}\end{array}$$ There is, of course, a well-known issue with this approach, as exemplified in the next result.

Theorem 2.

There are semantics, σ, for which the language ${\mathit{L}}_{{\mathit{\sigma }}^{\mathrm{(}\mathbb{N}\mathrm{)}}}$ is not recursive.

Proof.

Suppose the contrary and that for every σ we have a Turing machine program ${\mathit{M}}_{{\mathit{\sigma }}^{\mathrm{(}\mathbb{N}\mathrm{)}}}$ that on input $1^{\mathit{n}}$ halts and reports ⊤ whenever ${\mathit{E}}_{\mathit{\sigma }}\mathrm{(}{dec}^{\mathrm{(}\mathbb{A}\mathrm{)}}\mathrm{(}\mathit{n}\mathrm{)}\mathrm{)}=\top$ and halts and reports ⊥ with all other instances. Define the predicate $\mathrm{diagsem}:\mathbb{N}\to \{\top \mathrm{,}\perp \}$ as $$\begin{array}{c}diagsem\mathrm{(}\mathit{k}\mathrm{)}=\left\{\begin{array}{cc}\perp \hfill & \text{if }{\mathit{M}}_{\mathit{k}}\mathrm{(}{1}^{\mathit{k}}\mathrm{)}=\top \hfill \\ \top \hfill & \text{if }{\mathit{M}}_{\mathit{k}}\mathrm{(}{1}^{\mathit{k}}\mathrm{)}=\perp \hfill \end{array}\right.\end{array}$$ Here ${\mathit{M}}_{\mathit{k}}$ is the k’th Turing machine as given by the standard lexicographic ordering of TM codes with single symbol input alphabets. The predicate $\mathrm{diagsem}$ defines a semantics, ${\mathit{\sigma }}_{\mathrm{diagsem}}$ as described in Section 4.2. From the starting assumption, the language ${\mathit{L}}_{{\mathit{\sigma }}_{\mathrm{diagsem}}^{\mathrm{(}\mathbb{N}\mathrm{)}}}$ is recursive and so there is a TM, ${\mathit{M}}_{\mathrm{diagsem}}$ that halts and reports ⊤ on instances $1^{\mathit{n}}$ for which ${\mathit{E}}_{{\mathit{\sigma }}_{\mathrm{diagsem}}}\mathrm{(}{dec}^{\mathrm{(}\mathbb{A}\mathrm{)}}\mathrm{(}\mathit{n}\mathrm{)}\mathrm{)}=\top$ and which halts and reports ⊥ on all other instances. Since ${\mathit{M}}_{\mathrm{diagsem}}$ is a TM program with a single symbol input alphabet there is some $\mathit{t}\in \mathbb{N}$ such that $\mathit{\chi }\mathrm{(}{\mathit{M}}_{\mathrm{diagsem}}\mathrm{)}$ is the t’th codeword. What, however, is the value $diagsem\mathrm{(}\mathit{t}\mathrm{)}$ ? It cannot be ⊤ since by definition $diagsem\mathrm{(}\mathit{t}\mathrm{)}=\top$ if ${\mathit{M}}_{\mathit{t}}\mathrm{(}{1}^{\mathit{t}}\mathrm{)}=\perp$ ; similarly it cannot be ⊥ since this would only happen should ${\mathit{M}}_{\mathit{t}}\mathrm{(}{1}^{\mathit{t}}\mathrm{)}=\top$ . It follows that ${\mathit{L}}_{{\mathit{\sigma }}_{\mathrm{diagsem}}^{\mathrm{(}\mathbb{N}\mathrm{)}}}$ is not recursive. □

The proof technique, “diagonalization”, of Theorem 2 is one of the classical tools used in the study of properties of infinite structures and dates back to the late 19th century.

One consequence is,

Corollary 1.

There are semantics, σ, for which the language ${\mathit{L}}_{{\mathit{\sigma }}^{\mathrm{(}\mathbb{N}\mathrm{)}}}$ is not recursively enumerable.

Proof.

Let σ be a semantics. Define its complementary semantics, $\mathrm{co}\mathit{\sigma }$ through the behaviour ${\mathit{E}}_{\mathrm{co}\mathit{\sigma }}\mathrm{(}\mathcal{H}\mathrm{,}\mathbb{S}\mathrm{)}=\neg {\mathit{E}}_{\mathit{\sigma }}\mathrm{(}\mathcal{H}\mathrm{,}\mathbb{S}\mathrm{)}$ . The language ${\mathit{L}}_{\mathrm{co}{\mathit{\sigma }}^{\mathrm{(}\mathbb{N}\mathrm{)}}}={\mathrm{coL}}_{{\mathit{\sigma }}^{\mathrm{(}\mathbb{N}\mathrm{)}}}$ , i.e ${\mathit{L}}_{\mathrm{co}{\mathit{\sigma }}^{\mathrm{(}\mathbb{N}\mathrm{)}}}={\{1\}}^{\ast }\setminus {\mathit{L}}_{{\mathit{\sigma }}^{\mathrm{(}\mathbb{N}\mathrm{)}}}$ . It is a well-known result from computability that if a language, L is not recursive then its complement $\mathrm{coL}$ is not r.e. This suffices to prove the claim. □

We could deal with each of the various semantic principles that have been proposed on a case-by-case basis. We can, however, proceed in a much more general style.

Definition 5.

Let σ be any semantics. A blocking set for σ is a specific $\mathit{T}\subseteq \mathcal{X}$ for which there are choices ${\mathcal{A}}_{\mathrm{in}}$ and ${\mathcal{A}}_{\mathrm{out}}$ with $\mathit{T}\in \mathit{\sigma }\mathrm{(}{\mathcal{H}}_{\mathrm{in}}\mathrm{)}$ but $\mathit{T}\notin \mathit{\sigma }\mathrm{(}{\mathcal{H}}_{\mathrm{out}}\mathrm{)}$ , ${\mathcal{H}}_{\mathrm{in}}$ , ${\mathcal{H}}_{\mathrm{out}}$ being the afs with attack sets ${\mathcal{A}}_{\mathrm{in}}$ respectively ${\mathcal{A}}_{\mathrm{out}}$ .

The augmentation of σ by a blocking set ${\mathit{T}}_{\mathit{\sigma }}^{\mathcal{X}}$ is the semantics, denoted ${\mathit{\sigma }}_{+\mathrm{,}{\mathit{T}}^{\mathcal{X}}}$ , defined as $$\begin{array}{c}\{\mathrm{(}\mathcal{H}\mathrm{,}\mathbb{S}\mathrm{)}:\mathbb{S}=\mathit{\sigma }\mathrm{(}\mathcal{H}\mathrm{)}\text{ or }{\mathit{T}}_{\mathit{\sigma }}^{\mathcal{X}}\in \mathbb{S}\}\end{array}$$

For example for $\mathit{\sigma }=\mathrm{cf}$ we could choose ${\mathit{T}}_{\mathrm{cf}}^{\mathcal{X}}=\mathcal{X}$ ; for $\mathit{\sigma }=\mathrm{com}$ , ${\mathit{T}}_{\mathrm{com}}^{\mathcal{X}}=\{{\mathit{x}}_1\}$ .

Theorem 3.

Let σ be a semantics with a blocking set ${\mathit{T}}_{\mathit{\sigma }}^{\mathcal{X}}$ . Suppose that π is a semantics property that σ respects but ${\mathit{\sigma }}_{+\mathrm{,}{\mathit{T}}^{\mathcal{X}}}$ does not respect (for example conflict-freeness is respected by $\mathrm{cf}$ but not by ${\mathrm{cf}}_{+\mathrm{,}\mathcal{X}}$ ). Furthermore assume that ${\mathit{L}}_{\mathit{\sigma }}$ is infinite (i.e. there are infinitely instances $\mathrm{(}\mathcal{H}\mathrm{,}\mathbb{S}\mathrm{)}$ such that ${\mathit{E}}_{\mathit{\sigma }}\mathrm{(}\mathcal{H}\mathrm{,}\mathbb{S}\mathrm{)}=\top$ ). $$\begin{array}{c}{\mathit{L}}_{\mathrm{\Pi }}=\{\mathit{\chi }\mathrm{(}\mathit{M}\mathrm{)}:\mathit{L}\mathrm{(}\mathit{M}\mathrm{)}\subseteq {\{1\}}^{\ast }\mathit{\text{ and }}{\mathit{\sigma }}_{\mathit{L}\mathrm{(}\mathit{M}\mathrm{)}}\mathit{\text{ respects }}\mathit{\pi }\}\end{array}$$ is not recursively enumerable.

Proof.

The proof uses a technique adapted from the proof of Rice’s Theorem for r.e. properties, see Hopcroft and Ullman [5, Theorem 8.7, pp. 191–2].

It is known that the language $$\begin{array}{c}{\mathit{L}}_{\mathrm{out}}=\{⟨\mathit{\chi }\mathrm{(}\mathit{M}\mathrm{)}\mathrm{,}\mathit{w}⟩:\mathit{w}\notin \mathit{L}\mathrm{(}\mathit{M}\mathrm{)}\}\end{array}$$ is not r.e. (see Hopcroft and Ullman [5, Theorem 8.4, p. 184])

Suppose the contrary and that for some such property within the conditions stated, π say, there is some program, ${\mathit{M}}_{\mathrm{\Pi }}$ accepting ${\mathit{L}}_{\mathrm{\Pi }}$ : that is ${\mathit{M}}_{\mathrm{\Pi }}$ , given $\mathit{\chi }\mathrm{(}\mathit{M}\mathrm{)}$ , ${\mathit{M}}_{\mathrm{\Pi }}$ halts and accepts all instances for which ${\mathit{\sigma }}_{\mathit{L}\mathrm{(}\mathit{M}\mathrm{)}}$ respects the property π.

Let σ have property π but be such that ${\mathit{\sigma }}_{+\mathrm{,}{\mathit{T}}^{\mathcal{X}}}$ does not. $$\begin{array}{l}{\mathit{L}}_{\mathit{\sigma }}=\{1^{\mathit{k}}:{\mathit{E}}_{\mathit{\sigma }}\mathrm{(}{dec}^{\mathrm{(}\mathbb{A}\mathrm{)}}\mathrm{(}\mathit{k}\mathrm{)}\mathrm{)}=\top \}\\ {\mathit{L}}_{{\mathit{\sigma }}_{+\mathrm{,}{\mathit{T}}^{\mathcal{X}}}}=\{1^{\mathit{k}}:{\mathit{E}}_{{\mathit{\sigma }}_{+\mathrm{,}{\mathit{T}}^{\mathcal{X}}}}\mathrm{(}{dec}^{\mathrm{(}\mathbb{A}\mathrm{)}}\mathrm{(}\mathit{k}\mathrm{)}\mathrm{)}=\top \}\end{array}$$ With these ${\mathit{L}}_{\mathit{\sigma }}\subset {\mathit{L}}_{{\mathit{\sigma }}_{+\mathrm{,}{\mathit{T}}^{\mathcal{X}}}}$ .

Suppose we have an instance $⟨\mathit{\chi }\mathrm{(}\mathit{M}\mathrm{)}\mathrm{,}\mathit{w}⟩$ of ${\mathit{L}}_{\mathrm{out}}$ and consider the semantics defined as follows. Given $1^{\mathit{k}}$ with ${dec}^{\mathrm{(}\mathbb{A}\mathrm{)}}\mathrm{(}\mathit{k}\mathrm{)}=\mathrm{(}\mathcal{H}\mathrm{,}\mathbb{S}\mathrm{)}$ we run a “pre-compilation” stage using a program Q.

Q simulates M running with input w. If M halts and accepts w then Q starts ${\mathit{M}}_{{\mathit{\sigma }}_{+\mathrm{,}{\mathit{T}}^{\mathcal{X}}}}$ with $1^{{enc}^{\mathrm{(}\mathbb{A}\mathrm{)}}\mathrm{(}\mathcal{H}\mathrm{,}\mathbb{S}\mathrm{)}}$ , the encoding of a program accepting the language ${\mathit{L}}_{{\mathit{\sigma }}_{+\mathrm{,}{\mathit{T}}^{\mathcal{X}}}}$ .

Regardless of what happens in (1) (e.g. this step could be performed in parallel) Q will run ${\mathit{M}}_{\mathit{\sigma }}$ with input $1^{{enc}^{\mathrm{(}\mathbb{A}\mathrm{)}}\mathrm{(}\mathcal{H}\mathrm{,}\mathbb{S}\mathrm{)}}$ .

Now the semantics described by Q will correspond to ${\mathit{\sigma }}_{+\mathrm{,}{\mathit{T}}^{\mathcal{X}}}$ in the event that $\mathit{w}\in \mathit{L}\mathrm{(}\mathit{M}\mathrm{)}$ and to $\mathit{\sigma }\subset {\mathit{\sigma }}_{+\mathrm{,}{\mathit{T}}^{\mathcal{X}}}$ should $\mathit{w}\notin \mathit{L}\mathrm{(}\mathit{M}\mathrm{)}$ . Thus given an instance $⟨\mathit{\chi }\mathrm{(}\mathit{M}\mathrm{)}\mathrm{,}\mathit{w}⟩$ of ${\mathit{L}}_{\mathrm{out}}$ we can using Q construct the code of program, ${\mathit{M}}_{\mathit{\tau }\mathrm{,}\mathit{M}\mathrm{,}\mathit{w}}$ taking as its inputs $1^{{enc}^{\mathrm{(}\mathbb{A}\mathrm{)}}\mathrm{(}\mathcal{H}\mathrm{,}\mathbb{S}\mathrm{)}}$ .

Suppose now that the property defined by ${\mathit{L}}_{\mathrm{\Pi }}$ were r.e., $$\begin{array}{c}{\mathit{L}}_{\mathrm{\Pi }}=\{\mathit{\chi }\mathrm{(}{\mathit{M}}_{\mathit{\sigma }}\mathrm{)}:\mathit{\sigma }\text{ respects }\mathit{\pi }\}\end{array}$$ Then we build a program to recognise ${\mathit{L}}_{\mathrm{out}}$ by

Given $⟨\mathit{\chi }\mathrm{(}\mathit{M}\mathrm{)}\mathrm{,}\mathit{w}⟩$ use Q to compile the code $\mathit{\chi }\mathrm{(}{\mathit{M}}_{\mathit{\tau }\mathrm{,}\mathit{M}\mathrm{,}\mathit{w}}\mathrm{)}$ whose inputs are of the form $1^{{enc}^{\mathrm{(}\mathbb{A}\mathrm{)}}\mathrm{(}\mathcal{H}\mathrm{,}\mathbb{S}\mathrm{)}}$ .

Run ${\mathit{M}}_{\mathrm{\Pi }}$ with input $\mathit{\chi }\mathrm{(}{\mathit{M}}_{\mathit{\tau }\mathrm{,}\mathit{M}\mathrm{,}\mathit{w}}\mathrm{)}$ .

Then ${\mathit{M}}_{\mathrm{\Pi }}$ will accept $\mathit{\chi }\mathrm{(}{\mathit{M}}_{\mathit{\tau }\mathrm{,}\mathit{M}\mathrm{,}\mathit{w}}\mathrm{)}$ only if the semantics it describes corresponds to ${\mathit{L}}_{\mathit{\sigma }}$ that is $\mathit{w}\notin \mathit{L}\mathrm{(}\mathit{M}\mathrm{)}$ so contradicting the fact that ${\mathit{L}}_{\mathrm{out}}$ is not r.e. □

Corollary 2.

The languages describing the following properties for a semantics, σ, are not recursively enumerable.

Conflict-freeness.

Reinstatement.

Admissibility.

Strong admissibility, i.e. $\mathit{\sigma }\mathrm{(}\mathcal{H}\mathrm{)}\subseteq adm\mathrm{(}\mathcal{H}\mathrm{)}$ and $\mathit{S}\in \mathit{\sigma }\mathrm{(}\mathcal{H}\mathrm{)}\Rightarrow \mathrm{(}\forall \mathit{p}\in \mathit{S}\mathrm{,}\mathit{q}\in {\mathit{p}}^{-}\exists \mathit{r}\in \mathit{S}\setminus \mathit{p}:⟨\mathit{r}\mathrm{,}\mathit{q}⟩\in \mathcal{A}\mathrm{)}$ .

Naivety, i.e. $\mathit{S}\in \mathit{\sigma }\mathrm{(}\mathcal{H}\mathrm{)}\Rightarrow \mathrm{(}\mathit{S}\in cf\mathrm{(}\mathcal{H}\mathrm{)}\mathrm{)}$ and is a maximal (w.r.t. ⊆) set in $cf\mathrm{(}\mathcal{H}\mathrm{)}$ .

Abstention, i.e $\forall \mathit{x}\in \mathcal{X}$ if $\mathit{S}\mathrm{,}\mathit{T}\in \mathit{\sigma }\mathrm{(}\mathcal{H}\mathrm{)}$ with $\mathit{x}\in \mathit{S}$ , $\mathit{x}\in {\mathit{T}}^{+}$ then there is some $\mathit{Q}\in \mathit{\sigma }\mathrm{(}\mathcal{H}\mathrm{)}$ with $\mathit{x}\notin \mathit{Q}\cup {\mathit{Q}}^{+}$ .

I-maximality, i.e. $\forall \mathit{S}\mathrm{,}\mathit{T}\in \mathit{\sigma }\mathrm{(}\mathcal{H}\mathrm{)}$ $\mathit{S}\subseteq \mathit{T}\to \mathit{S}=\mathit{T}$ .

Proof.

From Theorem 3, it suffices to identify σ, and an augmentation of σ by a blocking set ${\mathit{T}}^{\mathcal{X}}$ in such a way that σ has the property of interest but ${\mathit{\sigma }}_{+\mathrm{,}{\mathit{T}}^{\mathcal{X}}}$ does not.

$\mathit{\sigma }=\mathrm{cf}$ , ${\mathit{T}}^{\mathcal{X}}=\mathcal{X}$ .

$\mathit{\sigma }=\mathrm{com}$ , ${\mathit{T}}^{\mathcal{X}}=\{{\mathit{x}}_1\}$ .

$\mathit{\sigma }=\mathrm{adm}$ , ${\mathit{T}}^{\mathcal{X}}=\mathcal{X}$ .

$\mathit{\sigma }=\mathrm{gnd}$ , ${\mathit{T}}^{\mathcal{X}}=\mathcal{X}$ .

$\mathit{\sigma }=\mathrm{naive}$ , ${\mathit{T}}^{\mathcal{X}}=\{{\mathit{x}}_1\mathrm{,}{\mathit{x}}_2\}$ .

$\mathit{\sigma }=\mathrm{com}$ , ${\mathit{T}}^{\mathcal{X}}=\mathcal{X}$ .

$\mathit{\sigma }=\mathrm{pr}$ , ${\mathit{T}}^{\mathcal{X}}=\{{\mathit{x}}_1\}$

 □

The case of “abstention” is of interest since, of the standard argumentation semantics, only the complete semantics has this property (conventionally unique status semantics such as the grounded only “satisfy” abstention in a rather vacuous sense).

The results above are a consequence of the languages concerned i.e. “property of a semantics σ”, failing to satisfy one of the three necessary and sufficient conditions prescribed by Rice’s Theorem for r.e. properties. Namely, let ${\mathit{L}}_{\mathrm{\Pi }}$ be $$\begin{array}{c}{\mathit{L}}_{\mathrm{\Pi }}=\{\mathit{\chi }\mathrm{(}\mathit{M}\mathrm{)}:\mathit{L}\mathrm{(}\mathit{M}\mathrm{)}\text{ has property }\mathrm{\Pi }\}\end{array}$$

If ${\mathit{L}}_{\mathrm{\Pi }}$ is r.e. and $\mathit{\chi }\mathrm{(}\mathit{M}\mathrm{)}\in {\mathit{L}}_{\mathrm{\Pi }}$ is such that $\mathit{L}\mathrm{(}\mathit{M}\mathrm{)}$ is infinite then every r.e. ${\mathit{L}}^{\prime }$ with ${\mathit{L}}^{\prime }\supset \mathit{L}\mathrm{(}\mathit{M}\mathrm{)}$ is in ${\mathit{L}}_{\mathrm{\Pi }}$ , i.e. the code $\mathit{\chi }\mathrm{(}{\mathit{M}}^{\prime }\mathrm{)}$ with $\mathit{L}\mathrm{(}{\mathit{M}}^{\prime }\mathrm{)}={\mathit{L}}^{\prime }$ is in ${\mathit{L}}_{\mathrm{\Pi }}$ .

If ${\mathit{L}}_{\mathrm{\Pi }}$ is r.e. and $\mathit{\chi }\mathrm{(}\mathit{M}\mathrm{)}\in {\mathit{L}}_{\mathrm{\Pi }}$ is such that $\mathit{L}\mathrm{(}\mathit{M}\mathrm{)}$ is infinite then there is a finite ${\mathit{L}}^{\prime }\subset \mathit{L}$ which is in ${\mathit{L}}_{\mathrm{\Pi }}$ , i.e. the code $\mathit{\chi }\mathrm{(}{\mathit{M}}^{\prime }\mathrm{)}$ with $\mathit{L}\mathrm{(}{\mathit{M}}^{\prime }\mathrm{)}={\mathit{L}}^{\prime }$ is in ${\mathit{L}}_{\mathrm{\Pi }}$ .

The set of finite languages, L, such that $\mathit{L}\in {\mathit{L}}_{\mathrm{\Pi }}$ can be enumerated. That is to say, there is a program which will produce the output ${\mathit{L}}_1\mathrm{\#}{\mathit{L}}_2\mathrm{\#}\cdots {\mathit{L}}_{\mathit{k}}\mathrm{\#}\cdots$ in which ${\mathit{L}}_{\mathit{i}}$ is a list of all of the members of the i’th finite language (ordering is unimportant) and in which every finite language $\mathit{L}\in {\mathit{L}}_{\mathrm{\Pi }}$ (eventually) will appear.

The languages ${\mathit{L}}_{\mathrm{CF}}$ , and ${\mathit{L}}_{\mathrm{reinst}}$ fail to satisfy (RE1) (the so-called “containment property”). It is, however, possible to show these satisfy (RE2). Theorem 4.

Let σ be a semantics that satisfies $$\begin{array}{c}\exists \mathit{k}\in \mathbb{N}{\mathit{E}}_{\mathit{\sigma }}\mathrm{(}{\mathcal{H}}_{\mathit{k}}\mathrm{,}\mathbb{T}\mathrm{)}\end{array}$$ where $|{\mathcal{X}}_{\mathit{k}}|⩽\mathit{k}$ . Let τ be the semantics with corresponding language $$\begin{array}{c}{\mathit{L}}_{\mathit{\tau }}=\{1^{\mathit{m}}:{dec}^{\mathrm{(}\mathbb{A}\mathrm{)}}\mathrm{(}\mathit{m}\mathrm{)}=\mathrm{(}\mathcal{H}\mathrm{,}\mathbb{S}\mathrm{)}\mathrm{,}{\mathit{E}}_{\mathit{\sigma }}\mathrm{(}\mathcal{H}\mathrm{,}\mathbb{S}\mathrm{)}\mathit{\text{ and }}|\mathcal{X}|⩽\mathit{k}\}\end{array}$$ If π is a semantic property that σ respecting π implies τ respecting π then ${\mathit{L}}_{\mathrm{\Pi }}$ satisfies (RE2), i.e. for every infinite language with the property there is a finite subset with the property.

Proof.

If $\mathit{\chi }\mathrm{(}{\mathit{M}}_{\mathit{\sigma }}\mathrm{)}\in {\mathit{L}}_{\mathrm{\Pi }}$ then the condition indicates that $\mathit{\chi }\mathrm{(}{\mathit{M}}_{\mathit{\tau }}\mathrm{)}\in {\mathit{L}}_{\mathrm{\Pi }}$ . The language ${\mathit{L}}_{\mathit{\tau }}$ is finite by virtue of its corresponding afs having only finitely many arguments. □

6. A positive result

Although many of the semantic properties of interest yield non r.e. languages and hence fail even to be partially decidable, we can conclude by presenting what is in some ways, a rather surprising positive result. This arises in the technically sophisticated concept of serializability from Thimm [6].

We first need the concept of initial sets, which Xu and Cayrol [8] introduced as the non-empty S in $\mathcal{H}$ such that $$\begin{array}{c}\mathit{S}\in adm\mathrm{(}\mathcal{H}\mathrm{)}\text{and}\forall :\varnothing \subset \mathit{T}\subset \mathit{S}:\mathit{T}\notin adm\mathrm{(}\mathcal{H}\mathrm{)}\end{array}$$ Letting $IS\mathrm{(}\mathcal{H}\mathrm{)}$ denote the initial sets of $\mathcal{H}$ , Thimm [6] groups initial sets into three classes.

unattacked initial sets S: those with ${\mathit{S}}^{-}=\varnothing$ .

unchallenged initial sets S: those for which ${\mathit{S}}^{-}\ne \varnothing$ and for all $\mathit{T}\in IS\mathrm{(}\mathcal{H}\mathrm{)}$ ${\mathit{T}}^{+}\cap \mathit{S}=\varnothing$ .

challenged initial sets S: those with ${\mathit{S}}^{-}\ne \varnothing$ and for which some $\mathit{T}\in IS\mathrm{(}\mathcal{H}\mathrm{)}$ has ${\mathit{T}}^{+}\cap \mathit{S}\ne \varnothing$

For $\mathcal{H}=\mathrm{(}\mathcal{X}\mathrm{,}\mathcal{A}\mathrm{)}$ :

${IS}^{\nleftarrow }\mathrm{(}\mathcal{H}\mathrm{)}$ are the unattacked initial sets of $\mathcal{H}$ .

${IS}^{\nleftrightarrow }\mathrm{(}\mathcal{H}\mathrm{)}$ the unchallenged initial sets of $\mathcal{H}$ .

${IS}^{\leftrightarrow }\mathrm{(}\mathcal{H}\mathrm{)}$ the challenged initial sets of $\mathcal{H}$ .

The reduct of $\mathcal{H}=\mathrm{(}\mathcal{X}\mathrm{,}\mathcal{A}\mathrm{)}$ with respect to $\mathit{S}\subseteq \mathcal{X}$ is the af, ${\mathcal{H}}_{\mathit{S}}$ with arguments $\mathcal{X}\setminus \mathrm{(}\mathit{S}\cup {\mathit{S}}^{+}\mathrm{)}$ and attacks $\mathcal{A}\setminus \{⟨\mathit{p}\mathrm{,}\mathit{q}⟩:\mathit{p}\in \mathit{S}\cup {\mathit{S}}^{+}\text{ or }\mathit{q}\in \mathit{S}\cup {\mathit{S}}^{+}\}$ .

Finally the concept of a semantics being serializable is presented in Thimm [6].

Let σ be a semantics, i.e. a mapping from any $\mathcal{H}$ to sets of subsets of $\mathcal{X}$ .

A state is a pair $\mathrm{(}\mathcal{H}\mathrm{,}\mathit{S}\mathrm{)}$ with $\mathit{S}\subseteq \mathcal{X}$ .

A selector is a function $\mathit{\alpha }:2^{2^{\mathcal{X}}}\times 2^{2^{\mathcal{X}}}\times 2^{2^{\mathcal{X}}}\to 2^{2^{\mathcal{X}}}$ satisfying $\mathit{\alpha }\mathrm{(}\mathit{R}\mathrm{,}\mathit{S}\mathrm{,}\mathit{T}\mathrm{)}\subseteq \mathit{R}\cup \mathit{S}\cup \mathit{T}$ for all $\mathit{R}\mathrm{,}\mathit{S}\mathrm{,}\mathit{T}\subseteq 2^{\mathcal{X}}$ .

A terminator is any Boolean function β mapping states to $\{0\mathrm{,}1\}$ .

A transition takes $\mathrm{(}\mathcal{H}\mathrm{,}\mathit{S}\mathrm{)}$ and $\mathit{T}\in \mathit{\alpha }\mathrm{(}{IS}^{\nleftarrow }\mathrm{(}\mathcal{H}\mathrm{)}\mathrm{,}{IS}^{\nleftrightarrow }\mathrm{(}\mathcal{H}\mathrm{)}\mathrm{,}{IS}^{\leftrightarrow }\mathrm{(}\mathcal{H}\mathrm{)}\mathrm{)}$ and returns the state $\mathrm{(}{\mathcal{H}}_{\mathit{T}}\mathrm{,}\mathit{S}\cup \mathit{T}\mathrm{)}$ .

We write $\mathrm{(}\mathcal{H}\mathrm{,}\mathit{S}\mathrm{)}{⇝}^{\mathrm{(}\mathit{\alpha }\mathrm{)}}\mathrm{(}{\mathcal{H}}^{\prime }\mathrm{,}\mathit{T}\mathrm{)}$ if the state $\mathrm{(}{\mathcal{H}}^{\prime }\mathrm{,}\mathit{T}\mathrm{)}$ results after a finite number of applications of α. If $\mathit{\beta }\mathrm{(}{\mathcal{H}}^{\prime }\mathrm{,}\mathit{T}\mathrm{)}=1$ the state is terminal in which case we write $\mathrm{(}\mathcal{H}\mathrm{,}\mathit{S}\mathrm{)}{\to }^{\mathrm{(}\mathit{\alpha }\mathrm{,}\mathit{\beta }\mathrm{)}}\mathrm{(}{\mathcal{H}}^{\prime }\mathrm{,}\mathit{T}\mathrm{)}$ .

Finally let ${\mathcal{G}}^{\mathrm{(}\mathit{\alpha }\mathrm{,}\mathit{\beta }\mathrm{)}}\mathrm{(}\mathcal{H}\mathrm{)}$ be $$\begin{array}{c}{\mathcal{G}}^{\mathrm{(}\mathit{\alpha }\mathrm{,}\mathit{\beta }\mathrm{)}}\mathrm{(}\mathcal{H}\mathrm{)}=\{\mathit{S}\subset \mathcal{X}:\mathrm{(}\mathcal{H}\mathrm{,}\varnothing \mathrm{)}{⇝}^{\mathrm{(}\mathit{\alpha }\mathrm{,}\mathit{\beta }\mathrm{)}}\mathrm{(}{\mathcal{H}}^{\prime }\mathrm{,}\mathit{S}\mathrm{\left)}\right\}\end{array}$$ (for some af, ${\mathcal{H}}^{\prime }$ )

Definition 6 (Thimm [6]).

A semantics σ is serializable if there are a selector α and terminator β with which $\mathit{\sigma }\mathrm{(}\mathcal{H}\mathrm{)}={\mathcal{G}}^{\mathrm{(}\mathit{\alpha }\mathrm{,}\mathit{\beta }\mathrm{)}}\mathrm{(}\mathcal{H}\mathrm{)}$ .

The following example is taken from Thimm [6].

Choose as selector function $$\begin{array}{c}{\mathit{\alpha }}_{\mathrm{adm}}\mathrm{(}\mathit{R}\mathrm{,}\mathit{S}\mathrm{,}\mathit{T}\mathrm{)}=\mathit{R}\cup \mathit{S}\cup \mathit{T}\text{subject to }\mathit{R}\in {\mathrm{IS}}^{\nleftarrow }\mathrm{,}\mathit{S}\in {\mathrm{IS}}^{\nleftrightarrow }\mathrm{,}\mathit{T}\in {\mathrm{IS}}^{\leftrightarrow }\end{array}$$ Let the termination function be $\mathit{\beta }\mathrm{(}\mathcal{H}\mathrm{,}\mathit{S}\mathrm{)}=1$ if and only if $IS\mathrm{(}\mathcal{H}\mathrm{)}=\varnothing$ : hence the termination condition is such that the process of “select (using ${\mathit{\alpha }}_{\mathrm{adm}}$ ) – apply transition (form the reduct)” leads to a framework with no initial sets. Using these Thimm [6] has shown that the preferred semantics are serializable. Changing the termination condition from “ $\mathit{\beta }\mathrm{(}\mathcal{H}\mathrm{,}\mathit{S}\mathrm{)}=1$ if and only if $IS\mathrm{(}\mathcal{H}\mathrm{)}=\varnothing$ ” to “ $\mathit{\beta }\mathrm{(}\mathcal{H}\mathrm{,}\mathit{S}\mathrm{)}=1$ ”, that is irrespective of further conditions on the state $\mathrm{(}\mathcal{H}\mathrm{,}\mathit{S}\mathrm{)}$ , establishes that the admissibility semantics are serializable. In fact all of the cases in Definition 3 are serializable as also stable semantics (S is admissible with ${\mathit{S}}^{+}=\mathcal{X}\setminus \mathit{S}$ ). In contrast, however, neither semi-stable (S is admissible with $\mathit{S}\cup {\mathit{S}}^{+}$ maximal) nor ideal (S is admissible with every argument of S in every preferred extension) are serializable.

It is clear that $$\begin{array}{c}\mathit{\sigma }\mathrm{(}\mathcal{H}\mathrm{)}=\{\mathit{S}\subseteq \mathcal{X}:\mathit{S}\text{ is an initial set of }\mathcal{H}\}\end{array}$$ is verifiable, as also the associated semantics arising from unattacked, unchallenged and challenged initial sets. Recall that a state is a pair $⟨\mathcal{H}\mathrm{,}\mathit{S}⟩$ mapped by a selector function α whose arguments come from ${IS}^{\nleftarrow }\mathrm{(}\mathcal{H}\mathrm{)}$ , ${IS}^{\nleftrightarrow }\mathrm{(}\mathcal{H}\mathrm{)}$ and ${IS}^{\leftrightarrow }\mathrm{(}\mathcal{H}\mathrm{)}$ to a new state. We thus have $$\begin{array}{c}{\mathit{L}}_{\mathrm{trans}}=\{\mathrm{(}{\mathit{q}}_{\mathrm{init}}\mathrm{,}{\mathit{q}}_{\mathrm{dest}}\mathrm{)}:\exists \mathit{\alpha }\text{ with }{\mathit{q}}_{\mathrm{init}}{⇝}^{\mathrm{(}\mathit{\alpha }\mathrm{)}}{\mathit{q}}_{\mathrm{dest}}\}\end{array}$$

Theorem 5.

${\mathit{L}}_{\mathrm{trans}}$ is recursive.

Proof.

Recall that instances are pairs of states $⟨\mathrm{(}\mathcal{H}\mathrm{,}\mathit{S}\mathrm{)}\mathrm{,}\mathrm{(}{\mathcal{H}}^{\prime }\mathrm{,}\mathit{T}\mathrm{)}⟩$ . Furthermore selectors, α, may be viewed as 4-tuples of whole numbers $\mathrm{(}\mathit{u}\mathrm{,}\mathit{v}\mathrm{,}\mathit{w}\mathrm{,}\mathit{t}\mathrm{)}$ with $0⩽\mathit{u}\mathrm{,}\mathit{v}\mathrm{,}\mathit{w}\mathrm{,}\mathit{t}⩽2^{2^{|\mathcal{X}|}}-1$ . From Lemma 1 we can move between sets of subsets of $\mathcal{X}$ and whole numbers in this range. Finally we note that starting from the 4-tuple $\mathrm{(}0\mathrm{,}0\mathrm{,}0\mathrm{,}0\mathrm{)}$ we can consider each 4-tuple in turn ending at $\mathrm{(}{2}^{2^{|\mathcal{X}|}}-1\mathrm{,}{2}^{2^{|\mathcal{X}|}}-1\mathrm{,}{2}^{2^{|\mathcal{X}|}}-1\mathrm{,}{2}^{2^{|\mathcal{X}|}}-1\mathrm{)}$ . It is thus possible systematically to review every selector function.

We do not, of course, propose the following algorithm as a practical method: it is solely to demonstrate the claim of the Theorem.

Given $⟨\mathrm{(}\mathcal{H}\mathrm{,}\mathit{S}\mathrm{)}\mathrm{,}\mathrm{(}{\mathcal{H}}^{\prime }\mathrm{,}\mathit{T}\mathrm{)}⟩$ proceed as follows

Set the current state $\mathrm{(}\mathcal{G}\mathrm{,}\mathit{R}\mathrm{)}$ to be $\mathrm{(}\mathcal{H}\mathrm{,}\mathit{S}\mathrm{)}$

Choose the next selector $\mathrm{(}\mathit{u}\mathrm{,}\mathit{v}\mathrm{,}\mathit{w}\mathrm{,}\mathit{t}\mathrm{)}$ .

If the subsets corresponding to $\mathrm{(}\mathit{u}\mathrm{,}\mathit{v}\mathrm{,}\mathit{w}\mathrm{)}$ are not from $\mathrm{(}{IS}^{\nleftarrow }\mathrm{(}\mathcal{G}\mathrm{)}\mathrm{,}{IS}^{\nleftrightarrow }\mathrm{(}\mathcal{G}\mathrm{)}\mathrm{,}{IS}^{\leftrightarrow }\mathrm{(}\mathcal{G}\mathrm{)}\mathrm{)}$ go back to (b).

If the subset corresponding to t is not a subset of the union of those given by u, v, w go back to (b)

Let $\mathit{B}={\mathit{\eta }}^{-1}\mathrm{(}\mathit{t}\mathrm{)}$ . Update the current state to $\mathrm{(}{\mathcal{G}}_{\mathit{B}}\mathrm{,}\mathit{S}\cup \mathit{B}\mathrm{)}$ .

If $\mathit{B}=\varnothing$ return to (b).

Recursively call the procedure with input $⟨\mathrm{(}{\mathcal{G}}_{\mathit{B}}\mathrm{,}\mathit{S}\cup \mathit{B}\mathrm{)}\mathrm{,}\mathrm{(}{\mathcal{H}}^{\prime }\mathrm{,}\mathit{T}\mathrm{)}⟩$ .

If the result of (f) is accept then report accept otherwise return to (b)

If all selectors considered then reject.

Notice that the reduct operation reduces the number of arguments while the second state argument increases. Thus the recursive step at (g) will eventually terminate. □

Although Theorem 5 establishes the decidability of whether a selector function exists that moves from one state to another it is a little bit unsatisfactory in one regard: it can be shown that the preferred semantics is serializable via the selector $\mathit{\alpha }\mathrm{(}\mathit{X}\mathrm{,}\mathit{Y}\mathrm{,}\mathit{Z}\mathrm{)}=\mathit{X}\cup \mathit{Y}\cup \mathit{Z}$ a choice which is clearly effective. A selector function discovered by the procedure of Theorem 5 only identifies a sequence of transitions relevant to one framework.

7. Conclusions

Our main aim in this paper has been to consider a different aspect of algorithmics and argumentation semantics: that of decidability rather than computational complexity. The issue of whether algorithmic processes exist is not one that arises in typical environments: these will involve finite systems and deal with questions concerning specific semantics. Such semantics are matters that concern properties of finite sets of subsets of arguments. When, however, we start to consider argumentation semantics in the principle based terms promoted by, among others, Baroni and Giacomin [1] we face a new set of problems. In principle, it is always possible to analyze new proposals on an ad hoc basis in determining which desirable properties such have. Were it possible, however, to demonstrate adherence to given principle algorithmically such ad hoc approaches become redundant: codify the semantics in a form open to computational processing, present the codified form to a suitable program for analysis. We have shown that the main obstacle to this process is not the first aspect (finite codification of a semantics) but the second. The scale of unsolvability going beyond merely non-recursive (as in classical examples such as the Halting Problem of Turing [7]): in these when an instance is positive then it will, eventually, be accepted. Instead for semantic properties we face non-recursive enumerability: neither positive nor negative instances are guaranteed eventually to be recognized. The interplay between computation and argument semantics as described in Section 4 provides an insight into how powerful the notion of argument semantics is. Whether there are significant gains from this viewpoint is the object of study in future work.