22 papers · ranked by Valyu relevance
K. L. Kirkpatrick
The theoretical foundation of neuroscience differs from that of artificial intelligence, and to bridge this gap with AI, we would need a new computing paradigm that describes both fields well. The gap came from mathematicians’ invention of computability theory, which was deliberately narrower than cognition and yet…
Jeffrey Watumull, Marc D. Hauser, Ian G. Roberts, Norbert Hornstein
It is a truism that conceptual understanding of a hypothesis is required for its empirical investigation. However, the concept of recursion as articulated in the context of linguistic analysis has been perennially confused. Nowhere has this been more evident than in attempts to critique and extend Hauseretal's. ([24])…
Paul Vitányi
A Turing machine refers to a hypothetical machine proposed by Alan M. Turing (1912–1954) in 1936 [11] whose computations are intended to give an operational and formal definition of the intuitive notion of computability in the discrete domain. It is a digital device and sufficiently simple to be amenable to theoretical…
Nima Dehghani, Gianluca Caterina
This paper introduces a category theory-based framework to redefine physical computing in light of advancements in quantum computing and non-standard computing systems. By integrating classical definitions within this broader perspective, the paper rigorously recontextualizes what constitutes physical computing devices…
Jeannette M. Wing
Computational thinking will influence everyone in every field of endeavour. This vision poses a new educational challenge for our society, especially for our children. In thinking about computing, we need to be attuned to the three drivers of our field: science, technology and society. Accelerating technological…
Kristina Šekrst, Sandro Skansi
Even though it is only a thesis, not just unproven, but by definition, unprovable, the Church-Turing thesis has spearheaded research in computability for decades. At its core, it is a definition, whose task is to define in precise terms what it means to be "computable". But it is not called a "definition" because it is…
Yinsheng Zhang, Stanislav N. Gorb
Consciousness is liable to not be defined in scientific research, because it is an object of study in philosophy too, which actually hinders the integration of research on a large scale. The present study attempts to define consciousness with mathematical approaches by including the common meaning of consciousness…
Samson Abramsky
1 Indeed, I was once challenged on this point by an eminent physicist (now knighted), who demanded to know how I could speak of information increasing in computation when Shannon Information theory tells us that it cannot! My failure to answer this point very convincingly at the time led me to continue to ponder the…
Herbert Jaeger, Beatriz Noheda, Wilfred G. van der Wiel
Approaching limitations of digital computing technologies have spurred research in neuromorphic and other unconventional approaches to computing. Here we argue that if we want to engineer unconventional computing systems in a systematic way, we need guidance from a formal theory that is different from the classical…
Héctor Zenil
What does it mean to claim that a physical or natural system computes? One answer, endorsed here, is that computing is about programming a system to behave in different ways. This paper offers an account of what it means for a physical system to compute based on this notion. It proposes a behavioural characterisation…
Aran Nayebi
For over a decade, the hypercomputation movement has produced computational models that in theory solve the algorithmically unsolvable, but they are not physically realizable according to currently accepted physical theories. While opponents to the hypercomputation movement provide arguments against the physical…
Tiasa Mondol, Daniel G. Brown, Ercan Kuruoglu
We build an analysis based on the Algorithmic Information Theory of computational creativity and extend it to revisit computational aesthetics, thereby, improving on the existing efforts of its formulation. We discuss Kolmogorov complexity, models and randomness deficiency (which is a measure of how much a model falls…
Juan P. Franco, Karlo Doroc, Nitin Yadav, Peter Bossaerts + 1 more
The survival of human organisms depends on our ability to solve complex tasks in the face of limited cognitive resources. However, little is known about the factors that drive the complexity of those tasks. Here, building on insights from computational complexity theory, we quantify the computational hardness of…
Alexander Ngu
This paper uses the concept of algorithmic efficiency to present a unified theory of intelligence. Intelligence is defined informally, formally, and computationally. We introduce the concept of Dimensional complexity in algorithmic efficiency and deduce that an optimally efficient algorithm has zero Time complexity…
Juan Pablo Franco, Nitin Yadav, Peter Bossaerts, Carsten Murawski
Life presents us with decisions of varying degrees of difficulty. Many of them are NP-hard, that is, they are computationally intractable. Two important questions arise: which properties of decisions drive extreme computational hardness and what are the effects of these properties on human-decision making? Here, we…
Authors not listed
Step-by-step thinking is essential in all domains of chemical sciences and engineering. While machine learning tools are broadly used, algorithms that automate reasoning are far less common. We elaborate on seven categories of human reasoning activities and connect each to applications in chemical science and…
Authors not listed
Data-driven strategies are reshaping computational materials design by accelerating the prediction of novel compounds with targeted functionalities. Beyond high-throughput screening, the integration of generative artificial intelligence enables exploration across vast chemical spaces comprising millions of known and…
Hector Zenil, Narsis A. Kiani, Francesco Marabita, Yue Deng + 4 more
It remains fundamentally unclear how to reprogram complex evolving systems. Here, we introduce a conceptual framework and an interventional calculus to steer and manipulate systems based on their intrinsic algorithmic probability using the universal principles of the theory of computability and algorithmic information.…
Scott Federhen
The pure λ-calculus is endless fun for people of a certain disposition, but not everyone will want to work out division with Church numerals. Once it has been shown that it is possible to do everything with the λ-calculus, the next question becomes: is it possible to do anything useful with it? The advent of computers…
Stephen R. Piccolo, Michael B. Frampton
When reporting research findings, scientists document the steps they followed so that others can verify and build upon the research. When those steps have been described in sufficient detail that others can retrace the steps and obtain similar results, the research is said to be reproducible. Computers play a vital…
Authors not listed
The era of exascale computing presents both exciting opportunities and unique challenges for quantum mechanical simulations. While the transition from petaflops to exascale computing has been marked by a steady increase in computational power, the shift towards heterogeneous architectures, particularly the dominant…
Alan Aspuru-Guzik, Roland Lindh, Markus Reiher
To date, the program for the development of methods and models for atomistic and continuum simulation directed toward chemicals and materials has reached an incredible degree of sophistication and maturity. Currently, one can witness an increasingly rapid emergence of advances in computing, artificial intelligence, and…