Cristian S. Calude

Orcid: 0000-0002-8711-6799

Affiliations:
  • University of Auckland, New Zealand


According to our database1, Cristian S. Calude authored at least 173 papers between 1976 and 2024.

Collaborative distances:
  • Dijkstra number2 of four.
  • Erdős number3 of two.

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2024
How real is incomputability in physics?
Theor. Comput. Sci., 2024

To Halt or Not to Halt? That Is the Question
WorldScientific, ISBN: 9789811232299, 2024

2023
What perceptron neural networks are (not) good for?
Inf. Sci., April, 2023

2022
Deciding Parity Games in Quasi-polynomial Time.
SIAM J. Comput., 2022

2021
A new quantum random number generator certified by value indefiniteness.
Theor. Comput. Sci., 2021

Bi-immunity over different size alphabets.
Theor. Comput. Sci., 2021

Incompleteness and the Halting Problem.
Stud Logica, 2021

Solomon Marcus Contributions to Theoretical Computer Science and Applications.
Axioms, 2021

Gödel Incompleteness and Proof-Assistants Extended Abstract.
Proceedings of the 23rd International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, 2021

2020
Searching for shortest and least programs.
Theor. Comput. Sci., 2020

Infinitesimal Probabilities Based on Grossone.
SN Comput. Sci., 2020

Quantum solutions for densest k-subgraph problems.
J. Membr. Comput., 2020

A statistical anytime algorithm for the Halting Problem.
Comput., 2020

2018
Liouville, Computable, Borel Normal and Martin-Löf Random Numbers.
Theory Comput. Syst., 2018

A Simple Construction of Absolutely Disjunctive Liouville Numbers.
J. Autom. Lang. Comb., 2018

Quassical Computing.
Int. J. Unconv. Comput., 2018

A Hybrid Quantum-Classical Paradigm to Mitigate Embedding Costs in Quantum Annealing - Abridged Version.
Proceedings of the 9th International Workshop on Physics and Computation, 2018

A Hybrid Quantum-Classical Paradigm to Mitigate Embedding Costs in Quantum Annealing.
CoRR, 2018

A probabilistic anytime algorithm for the halting problem.
Comput., 2018

2017
QUBO formulations for the graph isomorphism problem and related problems.
Theor. Comput. Sci., 2017

Deciding parity games in quasipolynomial time.
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

Quantum Randomness: From Practice to Theory and Back.
Proceedings of the Incomputable: Journeys Beyond the Turing Barrier, 2017

2016
Classical, quantum and biological randomness as relative unpredictability.
Nat. Comput., 2016

Editorial.
Int. J. Unconv. Comput., 2016

Finite state incompressible infinite sequences.
Inf. Comput., 2016

Solomon Marcus, 1925-2016.
Bull. EATCS, 2016

Incompleteness, Undecidability and Automated Proofs - (Invited Talk).
Proceedings of the Computer Algebra in Scientific Computing - 18th International Workshop, 2016

2015
Guest Column: Adiabatic Quantum Computing Challenges.
SIGACT News, 2015

Deterministic Frequency Pushdown Automata.
J. Univers. Comput. Sci., 2015

A Non-Probabilistic Model of Relativised Predictability in Physics.
Inf., 2015

Anytime Algorithms for Non-Ending Computations.
Int. J. Found. Comput. Sci., 2015

Universality and Almost Decidability.
Fundam. Informaticae, 2015

News from New Zealand.
Bull. EATCS, 2015

On the Unpredictability of Individual Quantum Measurement Outcomes.
Proceedings of the Fields of Logic and Computation II, 2015

2014
A quantum random number generator certified by value indefiniteness.
Math. Struct. Comput. Sci., 2014

Preface.
Fundam. Informaticae, 2014

Can we solve the pipeline problem?
Proceedings of the Fourth Symposium on Digital Production, 2014

2013
Discrete mathematical structures: From dynamics to complexity.
Theor. Comput. Sci., 2013

Inductive Complexity of the P versus NP Problem.
Parallel Process. Lett., 2013

Algorithmic Complexity of Mathematical Problems: An Overview of Results and Open Problems.
Int. J. Unconv. Comput., 2013

Inductive Complexity Measures for Mathematical Problems.
Int. J. Found. Comput. Sci., 2013

Spectral Representation of Some Computably Enumerable Sets with an Application to Quantum Provability.
Proceedings of the Unconventional Computation and Natural Computation, 2013

2012
The complexity of Euler's integer partition theorem.
Theor. Comput. Sci., 2012

Introduction: computability of the physical.
Math. Struct. Comput. Sci., 2012

A Nuclear Magnetic Resonance Implementation of a Classical Deutsch-Jozsa Algorithm.
Int. J. Unconv. Comput., 2012

State-Size Hierarchy for Finite-State Complexity.
Int. J. Found. Comput. Sci., 2012

An Empirical Approach to the Normality of π.
Exp. Math., 2012

Von Neumann Normalisation of a Quantum Random Number Generator.
Comput., 2012

Is there a universal image generator?
Appl. Math. Comput., 2012

Preface to the Special Issue on Physics and Computation "Towards a Computational Interpretation of Physical Theories".
Appl. Math. Comput., 2012

Inductive Complexity of P versus NP Problem - Extended Abstract.
Proceedings of the Unconventional Computation and Natural Computation, 2012

2011
An Interview with Erol Gelenbe: Practical Theories Make the World Go (Part II).
Ubiquity, 2011

Finite state complexity.
Theor. Comput. Sci., 2011

Universal recursively enumerable sets of strings.
Theor. Comput. Sci., 2011

Simplicity via provability for universal prefix-free Turing machines.
Theor. Comput. Sci., 2011

Representation of left-computable ε-random reals.
J. Comput. Syst. Sci., 2011

Editorial.
Int. J. Unconv. Comput., 2011

An Observer-Based de-Quantisation of Deutsch's Algorithm.
Int. J. Found. Comput. Sci., 2011

A Multi-Criteria Metric Algorithm for Recommender Systems.
Fundam. Informaticae, 2011

Von Neumann Normalisation and Symptoms of Randomness: An Application to Sequences of Quantum Random Bits.
Proceedings of the Unconventional Computation - 10th International Conference, 2011

2010
An Interview with Erol Gelenbe.
Ubiquity, 2010

Preface to the Special Issue Unconventional Computing 2008.
Nat. Comput., 2010

A note on accelerated Turing machines.
Math. Struct. Comput. Sci., 2010

The complexity of the four colour theorem.
LMS J. Comput. Math., 2010

Algorithmically independent sequences.
Inf. Comput., 2010

Finite-State Complexity and the Size of Transducers
Proceedings of the Proceedings Twelfth Annual Workshop on Descriptional Complexity of Formal Systems, 2010

Pi_1-Statements, Chaotic Systems and the Church-Turing Thesis
CoRR, 2010

Understanding the Quantum Computational Speed-up via De-quantisation
Proceedings of the Proceedings Sixth Workshop on Developments in Computational Models: Causality, 2010

Experimental Evidence of Quantum Randomness Incomputability
CoRR, 2010

Evaluating the Complexity of Mathematical Problems: Part 2.
Complex Syst., 2010

2009
Topology on words.
Theor. Comput. Sci., 2009

Introduction.
Nat. Comput., 2009

On universal computably enumerable prefix codes.
Math. Struct. Comput. Sci., 2009

Every computably enumerable random real is provably computably enumerable random.
Log. J. IGPL, 2009

Evaluating the Complexity of Mathematical Problems: Part 1.
Complex Syst., 2009

Information: The Algorithmic Paradigm.
Proceedings of the Formal Theories of Information: From Shannon to Semantic Information Theory and General Concepts of Information [Muenchenwiler Seminar (Switzerland), 2009

Formal Proof: Reconciling Correctness and Understanding.
Proceedings of the Intelligent Computer Mathematics, 2009

2008
Foreword.
Nat. Comput., 2008

Most programs stop quickly or never halt.
Adv. Appl. Math., 2008

Incompleteness: A Personal Perspective.
Proceedings of the 10th International Workshop on Descriptional Complexity of Formal Systems, 2008

2007
Preface.
Theor. Comput. Sci., 2007

Preface.
Nat. Comput., 2007

Combinatorics and Related Areas A Collection of Papers in Honour of the 65th Birthday of Ioan Tomescu.
J. Univers. Comput. Sci., 2007

Exact Approximations of omega Numbers.
Int. J. Bifurc. Chaos, 2007

2006
A New Measure of the Difficulty of Problems.
J. Multiple Valued Log. Soft Comput., 2006

Natural halting probabilities, partial randomness, and zeta functions.
Inf. Comput., 2006

Automata Recognizing No Words: A Statistical Approach.
Fundam. Informaticae, 2006

On partial randomness.
Ann. Pure Appl. Log., 2006

2005
Generalisations of disjunctive sequences.
Math. Log. Q., 2005

Constructivity, Computability, and Logic A Collection of Papers in Honour of the 60th Birthday of Douglas Bridges.
J. Univers. Comput. Sci., 2005

Preface.
Int. J. Found. Comput. Sci., 2005

Proving as a Computable Procedure.
Fundam. Informaticae, 2005

Contagious Creativity.
Fundam. Informaticae, 2005

Is complexity a source of incompleteness?
Adv. Appl. Math., 2005

2004
A fast natural algorithm for searching.
Theor. Comput. Sci., 2004

Passages of Proof.
Bull. EATCS, 2004

Algorithmic Randomness, Quantum Physics, and Incompleteness.
Proceedings of the Machines, Computations, and Universality, 4th International Conference, 2004

Mathematical Proofs at a Crossroad?
Proceedings of the Theory Is Forever, 2004

Balance Machines: Computing = Balancing.
Proceedings of the Aspects of Molecular Computing, 2004

2003
What is the Value of Taxicab(6)?
J. Univers. Comput. Sci., 2003

A topological characterization of random sequences.
Inf. Process. Lett., 2003

2002
Information and Randomness - An Algorithmic Perspective
Texts in Theoretical Computer Science. An EATCS Series, Springer, ISBN: 978-3-662-04978-5, 2002

Chaitin Omega numbers, Solovay machines, and Gödel incompleteness.
Theor. Comput. Sci., 2002

A characterization of c.e. random reals.
Theor. Comput. Sci., 2002

Coins, Quantum Measurements, and Turing's Barrier.
Quantum Inf. Process., 2002

Incompleteness, Complexity, Randomness and Beyond.
Minds Mach., 2002

Additive Distances and Quasi-Distances Between Words.
J. Univers. Comput. Sci., 2002

Advances and Trends in Automata and Formal Languages A Collection of Papers in Honour of the 60th Birthday of Helmut Jürgensen - J.UCS Special Issue.
J. Univers. Comput. Sci., 2002

Computing a Glimpse of Randomness.
Exp. Math., 2002

The Bridge Crossing Problem.
Bull. EATCS, 2002

Bead-Sort: A Natural Sorting Algorithm.
Bull. EATCS, 2002

Entropic measures, Markov information sources and complexity.
Appl. Math. Comput., 2002

2001
Recursively enumerable reals and Chaitin Omega numbers.
Theor. Comput. Sci., 2001

Coding with Minimal Programs.
Int. J. Found. Comput. Sci., 2001

Automata: From Uncertainty to Quantum.
Proceedings of the Developments in Language Theory, 5th International Conference, 2001

Computational complementarity for probabilistic automata.
Proceedings of the Where Mathematics, 2001

Liars, Demons, and Chaos.
Proceedings of the Words, Semigroups, and Transductions, 2001

2000
Finite nondeterministic automata: Simulation and minimality.
Theor. Comput. Sci., 2000

Automata, Logic, and Computability: J.UCS Special Issue Dedicated to Professor Sergiu Rudeanu Festschrift.
J. Univers. Comput. Sci., 2000

Computing with cells and atoms in a nutshell.
Complex., 2000

Reflections on quantum computing.
Complex., 2000

Quantum Correlations Conundrum: An Automata-Theoretic Approach.
Proceedings of the Recent Topics in Mathematical and Computational Linguistics, 2000

Solving Problems with Finite Test Sets.
Proceedings of the Finite Versus Infinite, 2000

1999
Metric Lexical Analysis.
Proceedings of the Automata Implementation, 1999

Bisimulations and behaviour of nondeterministic automata.
Proceedings of the Developments in Language Theory, 1999

Program-Size Complexity of Initial Segments and Domination Reducibility.
Proceedings of the Jewels are Forever, 1999

1998
Computable Approximations of Reals: An Information-Theoretic Analysis.
Fundam. Informaticae, 1998

Computational Complementarity for Mealy Automata.
Bull. EATCS, 1998

Introduction to unconventional models of computation.
Complex., 1998

Computational Complementarity and Sofic Shifts.
Proceedings of Computing: The Fourth Australasian Theory Symposium (CATS'98), 1998

1997
Complexity: A Language-Theoretic Point of View.
Proceedings of the Handbook of Formal Languages, 1997

Optimum Extendible Prefix Codes.
J. Univers. Comput. Sci., 1997

Chaitin Omega Numbers and Strong Reducibilities.
J. Univers. Comput. Sci., 1997

Logic in Computer Science.
J. Univers. Comput. Sci., 1997

Do the Zeros of Riemann's Zeta-Function Form a Random Sequence?
Bull. EATCS, 1997

Language-theoretic Complexity of Disjunctive Sequences.
Discret. Appl. Math., 1997

A genius's story: Two books on Gödel.
Complex., 1997

Deterministic Automata: Simulation, Universality and Minimality.
Ann. Pure Appl. Log., 1997

Deterministic Automata: Simulation, Universality and Minimality. Extended Abstract.
Proceedings of the 3rd International Conference Developments in Language Theory, 1997

Effects of Kolmogorov Complexity Present in Inductive Inference as Well.
Proceedings of the Algorithmic Learning Theory, 8th International Conference, 1997

1996
Effective Category and Measure in Abstract Complexity Theory.
Theor. Comput. Sci., 1996

Kraft-Chaitin Inequality Revisited.
J. Univers. Comput. Sci., 1996

Algorithmic Information Theory: Open Problems.
J. Univers. Comput. Sci., 1996

The Finite, The Unbounded and The Infinite.
J. Univers. Comput. Sci., 1996

Are binary codings universal?
Complex., 1996

1995
What Is a Random String?
J. Univers. Comput. Sci., 1995

Program-size Complexity Computes the Halting Problem.
Bull. EATCS, 1995

Effective Category and Measure in Abstract Complexity Theory (Extended Abstract).
Proceedings of the Fundamentals of Computation Theory, 10th International Symposium, 1995

1994
Information and Randomness - An Algorithmic Perspective
EATCS Monographs on Theoretical Computer Science, Springer, ISBN: 978-3-662-03049-3, 1994

On Recursive Bounds for the Exceptional Values in Speed-Up.
Theor. Comput. Sci., 1994

Journal of Universal Computer Science.
J. Univers. Comput. Sci., 1994

Three Theories of Computational Complexity Extended Abstract.
Sci. Ann. Cuza Univ., 1994

Randomness as an Invariant for Number Representations.
Proceedings of the Results and Trends in Theoretical Computer Science, 1994

Pocket Mathematics.
Proceedings of the Mathematical Aspects of Natural and Formal Languages, 1994

1993
Note on the Topological Structure of Random Strings.
Theor. Comput. Sci., 1993

Algorithmically Coding the Universe.
Proceedings of the Developments in Language Theory, 1993

Borel Normality and Algorithmic Randomness.
Proceedings of the Developments in Language Theory, 1993

1992
Recursive Baire Classification and Speedable Functions.
Math. Log. Q., 1992

1991
Determining and Stationary Sets for Some Classes of Partial Recursive Functions.
Theor. Comput. Sci., 1991

Relativized Topological Size of Sets of Partial Recursive Functions.
Theor. Comput. Sci., 1991

1990
On a theorem of Günter Asser.
Math. Log. Q., 1990

1989
Ehrenfeucht Test Set Theorem and Hilbert Basis Theorem: A Constructive Glimpse.
Proceedings of the Mathematical Foundations of Computer Science 1989, 1989

1987
Super-Exponentials Nonprimitive Recursive, but Rudimentary.
Inf. Process. Lett., 1987

1986
Note on Ehrenfeucht's conjecture and Hilbert's basis theorem.
Bull. EATCS, 1986

1984
A class of nuniversal P Marti-Löf tests.
Bull. EATCS, 1984

1983
On a class of independent problems related to Rice theorem.
SIGACT News, 1983

Representability of recursive P. Martin-Löf tests.
Kybernetika, 1983

On representability of P. Martin-Löf tests.
Kybernetika, 1983

Independent Instances for Some Undecidable Problems.
RAIRO Theor. Informatics Appl., 1983

1982
Topological Size of Sets of Partial Recursive Functions.
Math. Log. Q., 1982

1981
Global syntax and semantics for recursively enumerable languages.
Fundam. Informaticae, 1981

1979
On topologies generated by Moisil resemblance relations.
Discret. Math., 1979

1976
On metrizability of the free monoids.
Discret. Math., 1976


  Loading...