The INI has a new website!

This is a legacy webpage. Please visit the new site to ensure you are seeing up to date information.

Isaac Newton Institute for Mathematical Sciences

Semantics and Syntax: A Legacy of Alan Turing

Papers and Preprints

Preprint No. Author(s) Title and publication details
IP12014 S Sanders Nonstandard analysis: a new way to compute
IP12025 S Lempp, U Andrews and JS Miller Universal computably enumerable equivalence relations
IP12026 S Lempp, RG Downey and AM Kach The complexity of computable categoricity
IP12027 S Lempp, G Barmpalias and TA Slaman A strong version of the minimal pair theorem for the c.e. Turing degrees
IP12028 S Lempp, U Andrews and M Cai On minimal pairs of c.e. truth-table degrees inside the Turing degree 0'
IP12043 P Aczel, H Ishihara and T Nemoto Generalized geometric theories and set-generated classes
IP12044 P Aczel Rudimentary and arithmetical constructive set theory Annals of Pure and Applied Logic
IP12046 ESV Freire, D Hofheniz and E Kiltz Non-interactive key exchange
IP12047 M Bellare, KG Paterson and S Thompson RKA-security beyond the Linear Barrier
IP12048 KG Paterson, A Polychroniadou and D Sibborn A coding-theoretic approach to recovering noisy RSA keys
IP12049 A Sorbi, U Andrews and J Miller Universal computably enumerable equivalence relations
IP12050 S B Cooper Incomputability after Alan Turing AMS Vol 59, number 6, June-July 2012
IP12051 AA Soskova Properties of the quasi-minimal degrees with resoect to degree spectra
IP12052 MI Soskova and H Ganchev Definability via K-pairs
IP12053 A Melnikov and R Downey Arithmetical categoricity of completely decomposable groups
IP12054 S Wainer and H Schwichtenberg Proofs and computations ASL Perspectives in Logic, Cambridge University Press 2012
IP12058 S B Cooper The incomputable reality Nature, Vol 482, Issue 7386
IP12059 SB Cooper Mathematics, metaphysics and the multiverse Computation, Physics and Beyond 2012 (Michael J Dinneen, Bakhadyr Khoussainov, Andre Nies, Eds), Lecture Notes in Computer Science 7160 Springer 2012
IP12060 SB Cooper From Turing machine to morphogenesis: forming and informing computation Theory & Applications of Models of Computation (Manindra Agrawal, S Barry Cooper, Angsheng Li, Eds), Lecture Notes in Computer Science 7287 Spr 2012
IP12061 S B Cooper Turing's Titanic machine? Communications of the ACM, Vol 55, January 2012
IP12062 G Barmpalias, R Holzl and A Lewis Analogues of Chaitin's Omega in the computably enumerable sets
IP12063 G Barmpalias and R Downey Resolute sets and initial segment complexity
IP12064 G Barmpalias Measures of complexity and randomness
IP12065 G Barmpalias and R Downey Integer valued martingales
IP12067 A Beckmann, S R Buss and S D Friedman Safe recursive set functions
IP12068 A Beckmann and S R Buss Improved witnessing and local improvement principles for second-order bounded arithmetic
IP12070 M Stannett, E Csuhaj-Varju and M Gheorghe P systems controlled by general topologies Proceedings of "Unconventional Computation & Natural Computation 2012, Orleans, 3-7 Sept 2012". To appear in LNCS
IP12071 M Stannett Membrane systems and hypercomputation CMC 13 (Conference on Membrane Computing, Budapest 2011. Will be included in associated LNCS proceedings volume.
IP12072 M Stannett and S Akl Guest editor's note: special issue on hypercomputation, physics and computation Parallel Proceeding Letters, Vol 22, No 03. Online version (July 2012)
IP12073 V Brattka, S Le Roux and A Pauly On the computational content of the Brouwer fixed point theorem How the World Computes,vol 7318 of LectureNotes in Computer Sciences (pages 57-67). Spirnger, Berlin 2012.
IP12074 M Fellows and R Downey Fundamentals of parameterized complexity
IP12075 P Koepke and B Seyfferth Towards a theory of infinite time Blum-Shub-Smale machines Turning Centenary Conference & 8th Conference on Computability in Europe, CiE 2012 Camb Lecture notes in Computer Science, Vol 7318 (2012) 405-15
IP12076 P Koepke and A Morozov On the computational strength of infinite time Blum Shub Smale machines
IP12077 P Koepke Felix Hausdorff and the foundations of mathematics
IP12079 P Welch The mathematical legacy of Alan Turning
IP12082 H Schwichtenberg Computational content of proofs
IP12084 R Downey and A Melnikov Completely decomposable groups and arithmetical categoricity
IP12085 R Downey The legacy of Alan Turing
IP12090 G Primiero intuitionistic logic of proofs with dependent proof terms
IP12091 G primiero a modal language for contextual computations
IP12092 G primiero A taxonomy of errors for information systems Minds & Machines
NI12010 J Alama, L Mamame and J Urban Dependencies in formal mathematics: applications and extraction for Coq and Mizar
NI12011 C Bylinski and J Alama New developments in parsing Mizar
NI12017 J Alama Tipi: A TPTP-based theory development environment emphasizing proof dependencies
NI12018 J Alama, T Heskes and D Kühlwein Premise selection for mathematics by corpus analysis and Kernel methods
NI12019 J Alama and R Kahle Checking proofs
NI12020 U Andrews, S Lempp and JS Miller Universal computably enumerable equivalence relations
NI12021 B Kjos-Hassen, A Taveneaux and N Thapen How much randomness is needed for statistics? Proceedings of Computability in Europe 2012, LNCS 7318, pages 395-404
NI12022 D Doty, JH Lutz and MJ Patitz The tile assembly model is intrinsically universal
NI12025 J Alama Escape to Mizar from ATPs
NI12026 G Primiero Intuitionistic logic of proofs with dependant proof terms
NI12027 X Gu, JH Lutz and E Mayordomo Dimension spectra of random subfractals of self-similar fractals
NI12030 RR Lutz, JH Lutz and JI Lathrop Requirements analysis for a product family of DNA Nanodevices
NI12031 P Aczel Some open (?) problems concerning dependent type theories
NI12032 P Aczel, H Ishihara and T Nemoto Generalized geometric theories and set-generated classes
NI12033 P Aczel Rudimentary and arithmetical constructive set theory
NI12035 J Avigad and V Brattka Computability and analysis: the legacy of Alan Turing
NI12036 V Brattka, S Le Roux and A Pauly Connected choice and the Brouwer Fixed Point Theorem
NI12037 R Downey Randomness, computation and mathematics
NI12038 R Downey, A Dediu and C Martin-Vide A parameterized complexity tutorial Proceedings, Language and Automata Theory & Applications, LATA 2012. Springer-Verlag LNCS 7183 (2012), 38-56
NI12039 RG Downey, CG Jockusch Jr. and PE Schupp Asymptotic density and computably enumerable sets s
NI12040 R Downey The birth and early years of parameterized complexity The Multivariate Algorithmic Revolution and Beyond. Essays Dedicated to Michael R Fellows on Occasion of 60th Birthday.
NI12041 R Downey, H Bodlaender and F Fomin A basic parameterized complexity primer The Multivariate Algorithmic Revolution and Beyond, Essays Dedicated to Michael R Fellows on the Occasion of His 60th Birthday.
NI12042 G Barmpalias and R Downey Exact pairs for the ideal of the $\it K$-trivial sequences in the turing degrees
NI12043 R Downey, A Kach and S Lempp Computable categoricity versus relative computable categoricity
NI12044 R Downey, KM Ng and R Solomon On minimal wtt-degrees and computably enumerable Turing degrees
NI12046 EJ Spoors and SS Wainer A hierarchy of ramified theories below PRA
NI12047 R Downey and KM Ng Lowness for bounded randomness Theoretical Computer Science A
NI12048 R Bod, B Fisseni and A Kurji Objectivity and reproducibility of proppian narrative annotations
NI12049 B Fisseni and B Löwe Which dimensions of narratives are relevent for human judgments of story equivalence?
NI12050 PD Welch $\it G \delta\sigma$-games
NI12051 PD Welch Global reflection principles
NI12052 JM Hitchcock and E Mayordomo Base invariance of feasible dimension
NI12053 AA Abbott, CS Calude and J Conder Kochen-Specker theorem revisited and strong incomputability of quantum randomness
NI12055 JD Hamkins, G Leibman and B Löwe Structural connections between a forcing class and its modal logic
NI12056 JD Hamkins Every countable model of set theory embeds into its own constructible universe
NI12059 JD Hamkins and B Löwe Moving up and down in the generic multiverse
NI12060 E Mayordomo Effective dimension in some general metric spaces
NI12061 R Glaschick A size index for multitape Turing Machines
NI12063 TA Slaman and A Sorbi A note on initial segments of the enumeration degrees
NI12064 V Becher and S Grigorieff Wadge hardness in Scott spaces and its effectivization
NI12065 V Becher and PA Heiber Normal numbers and finite automata
NI12066 V Becher and S Grigorieff Borel and Hausdorff hierarchies in topological spaces of Choquet games and their effectivization
NI12067 V Becher and PA Heiber Normality and differentiability
NI12068 V Becher Turing's normal numbers: towards randomness
NI12069 RA Shore The Turing degrees below generics and randoms
NI12070 G Barmpalias, R Hölzl and AEM Lewis Analogues of Chaitin's omega in the computably enumerable sets
NI12071 G Barmpalias and A Li Kolmogorov complexity and computably enumerable sets
NI12072 G Barmpalias and RG Downey Resolute sequences in initial segment complexity
NI12073 G Barmpalias Algorithmic randomness and measures of complexity
NI12081 A Beckmann and SR Buss Improved witnessing and local improvement principles for second-order bounded arithmetic
NI12082 A Beckmann, SR Buss and S-D Friedman Safe recursive set functions