Tomáš Gonda, Tobias Reinhart, Sebastian Stengele, Gemma De les Coves

Turing machines and spin models share a notion of universality according to which some simulate all others. Is there a theory of universality that captures this notion? We set up a categorical framework for universality which includes as instances universal Turing machines, universal spin models, NP completeness, top of a preorder, denseness of a subset, and more. By identifying necessary conditions for universality, we show that universal spin models cannot be finite. We also characterize when universality can be distinguished from a trivial one and use it to show that universal Turing machines are non-trivial in this sense. Our framework allows not only to compare universalities within each instance, but also instances themselves. We leverage a Fixed Point Theorem inspired by a result of Lawvere to establish that universality and negation give rise to unreachability (such as uncomputability). As such, this work sets the basis for a unified approach to universality and invites the study of further examples within the framework.

Read the full article at: arxiv.org

Maria del Rio-Chanona, Nadzeya Laurentsyeva, Johannes Wachs

Large language models like ChatGPT efficiently provide users with information about various topics, presenting a potential substitute for searching the web and asking people for help online. But since users interact privately with the model, these models may drastically reduce the amount of publicly available human-generated data and knowledge resources. This substitution can present a significant problem in securing training data for future models. In this work, we investigate how the release of ChatGPT changed human-generated open data on the web by analyzing the activity on Stack Overflow, the leading online Q\&A platform for computer programming. We find that relative to its Russian and Chinese counterparts, where access to ChatGPT is limited, and to similar forums for mathematics, where ChatGPT is less capable, activity on Stack Overflow significantly decreased. A difference-in-differences model estimates a 16\% decrease in weekly posts on Stack Overflow. This effect increases in magnitude over time, and is larger for posts related to the most widely used programming languages. Posts made after ChatGPT get similar voting scores than before, suggesting that ChatGPT is not merely displacing duplicate or low-quality content. These results suggest that more users are adopting large language models to answer questions and they are better substitutes for Stack Overflow for languages for which they have more training data. Using models like ChatGPT may be more efficient for solving certain programming problems, but its widespread adoption and the resulting shift away from public exchange on the web will limit the open data people and models can learn from in the future.

Read the full article at: arxiv.org

Diego Rybski & Antonio Ciccone 

Archive for History of Exact Sciences (2023)

Power-law city-size distributions are a statistical regularity researched in many countries and urban systems. In this history of science treatise we reconsider Felix Auerbach’s paper published in 1913. We reviewed his analysis and found (i) that a constant absolute concentration, as introduced by him, is equivalent to a power-law distribution with exponent ≈1, (ii) that Auerbach describes this equivalence, and (iii) that Auerbach also pioneered the empirical analysis of city-size distributions across countries, regions, and time periods. We further investigate his legacy as reflected in citations and find that important follow-up work, e.g. by Lotka (Elements of physical biology. Williams & Wilkins Company, Baltimore, 1925) and Zipf (Human behavior and the principle of least effort: an introduction to human ecology, Martino Publishing, Manfield Centre, CT (2012), 1949), does give proper reference to his discovery—but others do not. For example, only approximately 20% of city-related works citing Zipf (1949) also cite Auerbach (Petermanns Geogr Mitteilungen 59(74):74–76, 1913). To our best knowledge, Lotka (1925) was the first to describe the power-law rank-size rule as it is analyzed today. Saibante (Metron Rivista Internazionale di Statistica 7(2):53–99, 1928), building on Auerbach and Lotka, investigated the power-law rank-size rule across countries, regions, and time periods. Zipf’s achievement was to embed these findings in his monumental 1949 book. We suggest that the use of “Auerbach–Lotka–Zipf law” (or “ALZ-law”) is more appropriate than “Zipf’s law for cities”, which also avoids confusion with Zipf’s law for word frequency. We end the treatise with biographical notes on Auerbach.

Read the full article at: link.springer.com

Gabriele Di Bona, Alessandro Bellina, Giordano De Marzo, Angelo Petralia, Iacopo Iacopini, Vito Latora

The Heaps’ law, which characterizes the growth of novelties, has triggered new mathematical descriptions, based on urn models or on random walks, of the way we explore the world. However, an often-overlooked aspect is that novelties can also arise as new combinations of existing elements. Here we propose to study novelties as n≥1 consecutive elements appearing for the first time in a sequence, and we introduce the nth-order Heaps’ exponents to measure the pace of discovery of novelties of any order. Through extensive analyses of real-world sequences, we find that processes displaying the same pace of discovery of single items can instead differ at higher orders. We then propose to model the exploration dynamics as an edge-reinforced random walk with triggering on a network of relations between items which elvolves over time. The model reproduces the observed properties of higher-order novelties, and reveals how the space of possibilities expands over time along with the exploration process.

Read the full article at: arxiv.org