Computability in Europe, 13 conf., CiE 2017

Front Matter....Pages I-XIII
Front Matter....Pages 1-1
Character-Based Phylogeny Construction and Its Application to Tumor Evolution....Pages 3-13
Is there any Real Substance to the Claims for a ‘New Computationalism’?....Pages 14-23
Formalizing a Fragment of Combinatorics on Words....Pages 24-31
Turing’s 1949 Paper in Context....Pages 32-41
Gödel’s Reception of Turing’s Model of Computability: The “Shift of Perception” in 1934....Pages 42-49
A Guided Tour to Computational Haplotyping....Pages 50-63
Outline of Partial Computability in Computable Topology....Pages 64-76
Eliminating Unbounded Search in Computable Algebra....Pages 77-87
Computable Transformations of Structures....Pages 88-97
Formulas with Reversal....Pages 98-100
Compressibility and Probabilistic Proofs....Pages 101-111
Delayed-Input Cryptographic Protocols....Pages 112-115
Front Matter....Pages 117-117
A Deterministic Algorithm for Testing the Equivalence of Read-Once Branching Programs with Small Discrepancy....Pages 119-128
Counting Substrate Cycles in Topologically Restricted Metabolic Networks....Pages 129-140
Turing Computable Embeddings, Computable Infinitary Equivalence, and Linear Orders....Pages 141-151
Degrees of Categoricity of Rigid Structures....Pages 152-161
Flexible Indexing of Repetitive Collections....Pages 162-174
Admissibles in Gaps....Pages 175-186
Koepke Machines and Satisfiability for Infinitary Propositional Languages....Pages 187-197
The Recognizability Strength of Infinite Time Turing Machines with Ordinal Parameters....Pages 198-209
Front Matter....Pages 117-117
New Bounds on the Strength of Some Restrictions of Hindman’s Theorem....Pages 210-220
Infinite Time Busy Beavers....Pages 221-233
Permutive One-Way Cellular Automata and the Finiteness Problem for Automaton Groups....Pages 234-245
Towards Computable Analysis on the Generalised Real Line....Pages 246-257
Finite Language Forbidding-Enforcing Systems....Pages 258-269
On Higher Effective Descriptive Set Theory....Pages 282-291
Dimension Spectra of Lines....Pages 292-303
A Universal Oracle for Signal Machines....Pages 304-314
Game Characterizations and Lower Cones in the Weihrauch Degrees....Pages 315-326
Randomness Deficiencies....Pages 327-337
McShane-Whitney Pairs....Pages 338-350
Total Nondeterministic Turing Machines and a p-optimal Proof System for SAT....Pages 351-363
A One-Dimensional Physically Universal Cellular Automaton....Pages 364-374
Extending Wadge Theory to k-Partitions....Pages 375-386
Back Matter....Pages 387-399
....Pages 401-401