Supplementary Information. Undecidability of the spectral gap

This is the supplementary information associated to the article: T.S. Cubitt, D. Perez-Garcia, M.M. Wolf, Undecidability of the spectral gap, Nature 528, 207-211 (2015), doi:10.1038/nature16059

Subshifts with Simple Cellular Automata

A subshift is a set of in nite one- or two-way sequences over a xed nite set, de ned by a set of forbidden patterns. In this thesis, we study subshifts in the topological setting, where the natural morphisms between them are ones de ned by a (spatially uniform) local rule. Endomorphisms of subshifts are called cellular automata, and we call the set of cellular automata on a subshift its endomorphism monoid. It is known that the set of all sequences (the full shift) allows cellular automata with complex dynamical and computational properties. We are interested in subshifts that do not support such cellular automata. In particular, we study countable subshifts, minimal subshifts and subshifts with additional universal algebraic structure that cellular automata need to respect, and investigate certain criteria of `simplicity' of the endomorphism monoid, for each of them. In the case of countable subshifts, we concentrate on countable so c shifts, that is, countable subshifts de ned by a nite state automaton. We develop some general tools for studying cellular automata on such subshifts, and show that nilpotency and periodicity of cellular automata are decidable properties, and positive expansivity is impossible. Nevertheless, we also prove various undecidability results, by simulating counter machines with cellular automata. We prove that minimal subshifts generated by primitive Pisot substitutions only support virtually cyclic automorphism groups, and give an example of a Toeplitz subshift whose automorphism group is not nitely generated. In the algebraic setting, we study the centralizers of CA, and group and lattice homomorphic CA. In particular, we obtain results about centralizers of symbol permutations and bipermutive CA, and their connections with group structures.

Defining Contexts in Context-Free Grammars

This thesis introduces an extension of Chomsky’s context-free grammars equipped with operators for referring to left and right contexts of strings.The new model is called grammar with contexts. The semantics of these grammars are given in two equivalent ways — by language equations and by logical deduction, where a grammar is understood as a logic for the recursive definition of syntax. The motivation for grammars with contexts comes from an extensive example that completely defines the syntax and static semantics of a simple typed programming language. Grammars with contexts maintain most important practical properties of context-free grammars, including a variant of the Chomsky normal form. For grammars with one-sided contexts (that is, either left or right), there is a cubic-time tabular parsing algorithm, applicable to an arbitrary grammar. The time complexity of this algorithm can be improved to quadratic,provided that the grammar is unambiguous, that is, it only allows one parsefor every string it defines. A tabular parsing algorithm for grammars withtwo-sided contexts has fourth power time complexity. For these grammarsthere is a recognition algorithm that uses a linear amount of space. For certain subclasses of grammars with contexts there are low-degree polynomial parsing algorithms. One of them is an extension of the classical recursive descent for context-free grammars; the version for grammars with contexts still works in linear time like its prototype. Another algorithm, with time complexity varying from linear to cubic depending on the particular grammar, adapts deterministic LR parsing to the new model. If all context operators in a grammar define regular languages, then such a grammar can be transformed to an equivalent grammar without context operators at all. This allows one to represent the syntax of languages in a more succinct way by utilizing context specifications. Linear grammars with contexts turned out to be non-trivial already over a one-letter alphabet. This fact leads to some undecidability results for this family of grammars

La logique ordinale de Turing

Le sujet visé par cette dissertation est la logique ordinale de Turing. Nous nous référons au texte original de Turing «Systems of logic based on ordinals» (Turing [1939]), la thèse que Turing rédigea à Princeton sous la direction du professeur Alonzo Church. Le principe d’une logique ordinale consiste à surmonter localement l’incomplétude gödelienne pour l’arithmétique par le biais de progressions d’axiomes récursivement consistantes. Étant donné son importance considérable pour la théorie de la calculabilité et les fondements des mathématiques, cette recherche méconnue de Turing mérite une attention particulière. Nous retraçons ici le projet d’une logique ordinale, de ses origines dans le théorème d’incomplétude de Gödel jusqu'à ses avancées dans les développements de la théorie de la calculabilité. Nous concluons par une discussion philosophique sur les fondements des mathématiques en fonction d’un point de vue finitiste.

Postdramatisme et esthétique de l’indécidabilité dans Cleansed et Phaedra’s Love de Sarah Kane

Face à l’opacité interprétative et la faillite du langage auxquelles nous nous heurtons dans l’analyse des œuvres-chocs de Sarah Kane, quelle approche nous permettrait de commenter exhaustivement les formes et les moyens mis en œuvre par la dramaturge pour imprimer sa marque dans l’esprit du spectateur contemporain? Le théâtre postdramatique, paradigme élaboré par Hans-Thies Lehmann, présenterait a priori un dispositif pertinent pour faire lumière sur des problématiques contemporaines cruciales en jeu dans l’œuvre de Kane. Aucunement univoque, car soumis à l’interprétation et à l’engagement du spectateur, le caractère politique des pièces, pourtant spectral, s’avère ici essentiel. Ce spectre politique se laisse percevoir à travers le prisme de la violence et la nécessité du choc semble être son parti pris pour redéfinir le rôle du théâtre dans nos sociétés modernes caractérisées par la circulation massive des images à travers les nouveaux médias. Un lien de coresponsabilité de l’artiste et du spectateur se crée: l’œuvre nous interroge, spectateur/lecteur, sur la part mystérieuse de ce fond de cruauté humaine et sur notre complicité dans l’omniprésence de la violence à travers la consommation de ses produits. Mettant en relief les caractères transgressifs venant bousculer nos affects à travers des références à la « culture d’en bas » et un exercice des limites du spectaculaire centré sur l’obscène et le détournement des codes de la pornographie, cette lecture postdramatique de Cleansed et de Phaedra’s love entend restituer à l’œuvre de Kane son énergie pour un changement qui passe par un éveil des sens.

Schauder – Zur Dekonstruktion eines Spürens

Zusammenfassung: Ziel der Arbeit ist den Sinn von Schauder philosophisch zu erhellen. An einem Einzelphänomen, wie es so bisher nicht behandelt wurde, wird zugleich das Geflecht von Affekt/Emotion/Gefühl, gestützt auf Hegel, Heidegger, Husserl, Freud und Lacan, in immer neuen Ansätzen kritisch reflektiert und Zug um Zug mit Derrida dekonstruiert. In einem Textverfahren, das sich auch grafisch durch gegenübergestellte Kolumnen auszeichnet, werden heterogene Ansätze zum Sinn von Schauder mit dekonstruktivistischen Einsichten konfrontiert. Die Ansätze, Schauder über Datum, Begriff, Phänomen oder Strukturelement bestimmen zu wollen, durchdringen sich dabei mit denjenigen, die sich einer solchen Bestimmung entziehen (Hegels Negativität, Heideggers Seinsentzug oder Lacans Signifikantenmangel). Am Fokus Schauder, an dem sich das Fiktive einer mit sich selbst identischen Präsenz besonders eindringlich darstellt, werden so spezifische Aporien der Metaphysik der Präsenz entfaltet und die Geschlossenheit logozentristischer Systeme in die Bewegung einer anderen Öffnung und Schließung im Sinn der Schrift bzw. des allgemeinen Textes transformiert. Neben der différance, dem Entzug der Metapher, dem Supplement und dem Gespenstischen stützt sich die Arbeit auf die Iterabilität, bei der im selben Zug die Identität des Sinns gestiftet und zerstreut wird (Dissemination). Im Kapitel Piloerection werden Ambivalenzen und Paradoxien des Schauders am Beispiel von computergestützten empirisch-psychologischen Studien aufgezeigt. Im Kapitel Atopologie des Schauders prädikative, propositionale und topologische Bedingungen zum Sinn von Schauder analysiert und dekonstruiert. Ebenso, im Folgekapitel Etymon, etymologische und technisch-mediale Bedingungen. Im Schlußkapitel Maß, Anmaß, Unmaß der Empfindung des Schauders wird am Beispiel der konkreten Beiträge zum Schauder von Aristoteles, Kant, Fechner, Otto, Klages, Lorenz und Adorno aufgezeigt, dass (1) ein Schauder nicht von einem Außen aus an-gemessen werden kann, (2) sich im Schauder die metaphysische Opposition von Fiktion und Realität in einer Unentscheidbarkeit zerstreut, (3) dass trotz der Heterogenität der Ansätze in diesen Beiträgen eine Komplizenschaft zum Ausdruck kommt: ein Begehren nach Präsenz, das durch den Ausschluß des Anderen zugleich die Gewalt des Einen produziert, (4) dass der Signifikant Schauder, der selbst in Abwesenheit eines Referenten, eines bestimmten Signifikats, einer aktuellen Bedeutungs­intention, eines Sen­ders oder Empfängers funktioniert, als verändertes Zu­rückbleiben eines differenzieller Zeichens betrachtet werden muss, als Effekt von Spuren, die sich nur in ihrem eige­nen Auslöschen ereignen. Die Arbeit schließt mit dem Vorschlag, Spüren jenseits von Arché, Telos oder Eschaton, jenseits eines Phallogozentrismus in der derridaschen Spur zu denken. Nicht zuletzt über diese Pfropfung, wie sie im Französischen [trace] so nicht möglich ist, schließt sie als deutschsprachiger Beitrag an sein Werk an.

Expressiveness of Concurrent Languages

The aim of this thesis is to go through different approaches for proving expressiveness properties in several concurrent languages. We analyse four different calculi exploiting for each one a different technique. We begin with the analysis of a synchronous language, we explore the expressiveness of a fragment of CCS! (a variant of Milner's CCS where replication is considered instead of recursion) w.r.t. the existence of faithful encodings (i.e. encodings that respect the behaviour of the encoded model without introducing unnecessary computations) of models of computability strictly less expressive than Turing Machines. Namely, grammars of types 1,2 and 3 in the Chomsky Hierarchy. We then move to asynchronous languages and we study full abstraction for two Linda-like languages. Linda can be considered as the asynchronous version of CCS plus a shared memory (a multiset of elements) that is used for storing messages. After having defined a denotational semantics based on traces, we obtain fully abstract semantics for both languages by using suitable abstractions in order to identify different traces which do not correspond to different behaviours. Since the ability of one of the two variants considered of recognising multiple occurrences of messages in the store (which accounts for an increase of expressiveness) reflects in a less complex abstraction, we then study other languages where multiplicity plays a fundamental role. We consider the language CHR (Constraint Handling Rules) a language which uses multi-headed (guarded) rules. We prove that multiple heads augment the expressive power of the language. Indeed we show that if we restrict to rules where the head contains at most n atoms we could generate a hierarchy of languages with increasing expressiveness (i.e. the CHR language allowing at most n atoms in the heads is more expressive than the language allowing at most m atoms, with mundecidability for problems like reachability and coverability.

La déconstruction de l'onto-théologie par Jacques Derrida : détour littéraire et mise en relief de la matrice langagière comme "différance".

Le mouvement derridien de la différance marque la rupture avec l'affirmation de la métaphysique de la présence, avec l'autorité du signifié transcendantal. Dans cet univers mouvant de signifiants qui se renvoient perpétuellement les uns aux autres, la logique d'univocité se disloque. La "présence" n'est que fantomatique, s'esquissant au sein d'une chaîne ininterrompue de signifiants et se laissant toujours creuser par la marque d'un irréductible manque. Face au logocentrisme, corollaire de l'affirmation de la présence, l'écriture se veut siège et articulation de la trace, d'une origine qui ne peut être que raturée, véhicule d'une irrémédiable fêlure. La volet littéraire de la déconstruction a pour but de mettre en évidence le fonctionnement de l'"indécidabilité" du discours, soit une certaine ambivalence dans la signification qui caractérise tout texte. L'objectif principal de la présente recherche est de fournir une compréhension plus approfondie de la déconstruction en insistant sur l'ancrage langagier de tout texte. Le discours philosophique n'échappe ainsi pas au mécanisme différentiel du langage et de la dérive métaphorique. La parenté entre la perspective déconstructiviste derridienne et la conception mallarméenne du langage poétique semble frappante. La mise en oeuvre, par Mallarmé, d'une dislocation de l'espace textuel, son minutieux "creusement" du vers après renoncement à toute quête d'"Idéal", la mise en relief du leurre de l'appropriation langagière, voilà qui trouve un écho particulier dans les thèses derridiennes. La "mimésis" platonicienne se voit au travers du prisme de la "mimique" mallarméenne. La déconstruction poursuit son travail de "luxation" de l'oreille philosophique, insérant les philosophèmes dans la matrice langagière, les livrant ainsi au hasard du cheminement textuel et les confrontant à l'aporie. La philosophie n'a alors d'autre choix que d'abandonner ses prétentions transcendantales. La marche de la "différance" instaure une inexorable distance qui prive le sujet de tout rapport direct avec une origine assurée et lui ôte toute possibilité de maîtrise sur le monde. Au travers de la langue, se profile la question de l'altérité, de la relation dissymétrique qui nous lie à cet "autre", ce "tout-autre" qui nous fonde et nous constitue. L'accueil inconditionnel de cette altérité nous mènera à l'étude de la "religion", la déconstruction se tournant vers le "religieux" tout en effectuant un "retournement" habile de tout credo essentialiste.

Ciudadanía heterogénea y colonización de las prácticas simbólicas micro y macro fronterizas

El objetivo de este ensayo es el de relacionar de forma reflexiva las nuevas dinámicas de colonización, dominación y poder contemporáneas, con las cartografías simbólicas de la ciudad global y sus respectivas fronteras o bordes sistémicos, muchos de ellos desapercibidos por las personas y atravesados por jerarquías y clasificaciones las cuales se hallan inmersas, a su vez,en una multidimensionalidad social tanto positiva como negativa que genera que podamos hablar de una indecibilidad de lo simbólico. En torno a ello se desprende, asimismo, el objetivo de repensar desde una perspectiva crítica y relacional el espacio urbano y heterogéneo en el cual confluyen formas diversas de identidad, subjetividad y aplicabilidad normativa y social de lo jurídico. Finalmente se dejará planteada la pregunta de hasta dónde puede llegar la agencia humana ante cada una de las distintas fronteras y bordes sistémicos y simbólicos de lo global-heterogéneo, considerando para ello aportes teóricos como los de Suely Rolnik, que indican que hoy en día existen subjetividades acríticas por las cuales el poder adquiere cierta plasticidad y hegemonía alienantes.

La déconstruction de l'onto-théologie par Jacques Derrida : détour littéraire et mise en relief de la matrice langagière comme "différance"

Le mouvement derridien de la différance marque la rupture avec l'affirmation de la métaphysique de la présence, avec l'autorité du signifié transcendantal. Dans cet univers mouvant de signifiants qui se renvoient perpétuellement les uns aux autres, la logique d'univocité se disloque. La "présence" n'est que fantomatique, s'esquissant au sein d'une chaîne ininterrompue de signifiants et se laissant toujours creuser par la marque d'un irréductible manque. Face au logocentrisme, corollaire de l'affirmation de la présence, l'écriture se veut siège et articulation de la trace, d'une origine qui ne peut être que raturée, véhicule d'une irrémédiable fêlure. La volet littéraire de la déconstruction a pour but de mettre en évidence le fonctionnement de l'"indécidabilité" du discours, soit une certaine ambivalence dans la signification qui caractérise tout texte. L'objectif principal de la présente recherche est de fournir une compréhension plus approfondie de la déconstruction en insistant sur l'ancrage langagier de tout texte. Le discours philosophique n'échappe ainsi pas au mécanisme différentiel du langage et de la dérive métaphorique. La parenté entre la perspective déconstructiviste derridienne et la conception mallarméenne du langage poétique semble frappante. La mise en oeuvre, par Mallarmé, d'une dislocation de l'espace textuel, son minutieux "creusement" du vers après renoncement à toute quête d'"Idéal", la mise en relief du leurre de l'appropriation langagière, voilà qui trouve un écho particulier dans les thèses derridiennes. La "mimésis" platonicienne se voit au travers du prisme de la "mimique" mallarméenne. La déconstruction poursuit son travail de "luxation" de l'oreille philosophique, insérant les philosophèmes dans la matrice langagière, les livrant ainsi au hasard du cheminement textuel et les confrontant à l'aporie. La philosophie n'a alors d'autre choix que d'abandonner ses prétentions transcendantales. La marche de la "différance" instaure une inexorable distance qui prive le sujet de tout rapport direct avec une origine assurée et lui ôte toute possibilité de maîtrise sur le monde. Au travers de la langue, se profile la question de l'altérité, de la relation dissymétrique qui nous lie à cet "autre", ce "tout-autre" qui nous fonde et nous constitue. L'accueil inconditionnel de cette altérité nous mènera à l'étude de la "religion", la déconstruction se tournant vers le "religieux" tout en effectuant un "retournement" habile de tout credo essentialiste.