Ultrafinitism postulates that we can only compute on relatively short objects, and numbers beyond certain value are not available. This approach would also forbid many forms of infinitary reasoning and allow to remove certain paradoxes stemming from enumeration theorems. However, philosophers still disagree of whether such a finitist logic would be consistent. We present preliminary work on a proof system based on Curry-Howard isomorphism. We also try to present some well-known theorems that stop being true in such systems, whereas opposite statements become provable. This approach presents certain impossibility results as logical paradoxes stemming from a profligate use of transfinite reasoning.
相關內容
This paper examines the art practices, artwork, and motivations of prolific users of the latest generation of text-to-image models. Through interviews, observations, and a user survey, we present a sampling of the artistic styles and describe the developed community of practice around generative AI. We find that: 1) the text prompt and the resulting image can be considered collectively as an art piece prompts as art and 2) prompt templates (prompts with ``slots'' for others to fill in with their own words) are developed to create generative art styles. We discover that the value placed by this community on unique outputs leads to artists seeking specialized vocabulary to produce distinctive art pieces (e.g., by reading architectural blogs to find phrases to describe images). We also find that some artists use "glitches" in the model that can be turned into artistic styles of their own right. From these findings, we outline specific implications for design regarding future prompting and image editing options.
When modeling complex robot systems such as branched robots, whose kinematic structures are a tree, current techniques often require modeling the whole structure from scratch, even when partial models for the branches are available. This paper proposes a systematic modular procedure for the dynamic modeling of branched robots comprising several subsystems, each composed of an arbitrary number of rigid bodies, providing the final dynamic model by reusing previous models of each branch. Unlike previous approaches, the proposed strategy is applicable even if some subsystems are regarded as black boxes, requiring only twists and wrenches at the connection points between them. To help in the model composition, we also propose a weighted directed graph representation where the weights encode the propagation of twists and wrenches between the subsystems. A simple linear operation on the graph interconnection matrix provides the dynamics of the whole system. Numerical results using a 38-DoF fixed-base branched robot composed of nine subsystems show that the proposed formalism is as accurate as a state-of-the-art library for robotic dynamic modeling. Additional results using a 39-DoF holonomic branched mobile manipulator composed of ten subsystems demonstrate the fidelity of our model to a modern robotics simulator.
A patch framework consists of a bipartite graph between $n$ points and $m$ local views (patches) and the $d$-dimensional local coordinates of the points due to the views containing them. Given a patch framework, we consider the problem of finding a rigid alignment of the views, identified with an element of the product of $m$ orthogonal groups, $\mathbb{O}(d)^m$, that minimizes the alignment error. In the case when the views are noiseless, a perfect alignment exists, resulting in a realization of the points that respects the geometry of the views. The affine rigidity of such realizations, its connection with the overlapping structure of the views, and its consequences in spectral and semidefinite algorithms has been studied in related work [Zha and Zhang; Chaudhary et al.]. In this work, we characterize the non-degeneracy of a rigid alignment, consequently obtaining a characterization of the local rigidity of a realization, and convergence guarantees on Riemannian gradient descent for aligning the views. Precisely, we characterize the non-degeneracy of an alignment of (possibly noisy) local views based on the kernel and positivity of a certain matrix. Thereafter, we work in the noiseless setting. Under a mild condition on the local views, we show that the non-degeneracy and uniqueness of a perfect alignment, up to the action of $\mathbb{O}(d)$, are equivalent to the local and global rigidity of the resulting realization, respectively. This also yields a characterization of the local rigidity of a realization. We also provide necessary and sufficient conditions on the overlapping structure of the noiseless local views for their realizations to be locally/globally rigid. Finally, we focus on the Riemannian gradient descent for aligning the local views and obtain a sufficient condition on an alignment for the algorithm to converge (locally) linearly to it.
In this short note, I derive the Bell-CHSH inequalities as an elementary result in the present-day theory of statistical causality based on graphical models or Bayes' nets, defined in terms of DAGs (Directed Acyclic Graphs) representing direct statistical causal influences between a number of observed and unobserved random variables. I show how spatio-temporal constraints in loophole-free Bell experiments, and natural classical statistical causality considerations, lead to Bell's notion of local hidden variables, and thence to the CHSH inequalities. The word "local" applies to the way that the chosen settings influence the observed outcomes. The case of contextual setting-dependent hidden variables (thought of as being located in the measurement devices and dependent on the measurement settings) is automatically covered, despite recent claims that Bell's conclusions can be circumvented in this way.
In this paper, by constructing extremely hard examples of CSP (with large domains) and SAT (with long clauses), we prove that such examples cannot be solved without exhaustive search, which implies a weaker conclusion P $\neq$ NP. This constructive approach for proving impossibility results is very different (and missing) from those currently used in computational complexity theory, but is similar to that used by Kurt G\"{o}del in proving his famous logical impossibility results. Just as shown by G\"{o}del's results that proving formal unprovability is feasible in mathematics, the results of this paper show that proving computational hardness is not hard in mathematics. The intuition behind this mathematical tractability is that proving exhaustive search for constructed examples avoids handling numerous effective strategies of avoiding exhaustive search that exist for many hard problems such as 3-SAT. Consequently, it makes the separation of lower bounds between SAT (with long clauses) and 3-SAT much easier than that between 3-SAT and 2-SAT.
The ability to compose code in a modular fashion is important to the construction of large programs. In the logic programming setting, it is desirable that such capabilities be realized through logic-based devices. We describe an approach for doing this here. In our scheme a module corresponds to a block of code whose external view is mediated by a signature. Thus, signatures impose a form of hiding that is explained logically via existential quantifications over predicate, function and constant names. Modules interact through the mechanism of accumulation that translates into conjoining the clauses in them while respecting the scopes of existential quantifiers introduced by signatures. We show that this simple device for statically structuring name spaces suffices for realizing features related to code scoping for which the dynamic control of predicate definitions was earlier considered necessary. The module capabilities we present have previously been implemented via the compile-time inlining of accumulated modules. This approach does not support separate compilation. We redress this situation by showing how each distinct module can be compiled separately and inlining can be realized by a later, complementary and equally efficient linking phase.
Safety is critical in robotic tasks. Energy function based methods have been introduced to address the problem. To ensure safety in the presence of control limits, we need to design an energy function that results in persistently feasible safe control at all system states. However, designing such an energy function for high-dimensional nonlinear systems remains challenging. Considering the fact that there are redundant dynamics in high dimensional systems with respect to the safety specifications, this paper proposes a novel approach called abstract safe control. We propose a system abstraction method that enables the design of energy functions on a low-dimensional model. Then we can synthesize the energy function with respect to the low-dimensional model to ensure persistent feasibility. The resulting safe controller can be directly transferred to other systems with the same abstraction, e.g., when a robot arm holds different tools. The proposed approach is demonstrated on a 7-DoF robot arm (14 states) both in simulation and real-world. Our method always finds feasible control and achieves zero safety violations in 500 trials on 5 different systems.
Blind source separation (BSS) aims to recover an unobserved signal $S$ from its mixture $X=f(S)$ under the condition that the effecting transformation $f$ is invertible but unknown. As this is a basic problem with many practical applications, a fundamental issue is to understand how the solutions to this problem behave when their supporting statistical prior assumptions are violated. In the classical context of linear mixtures, we present a general framework for analysing such violations and quantifying their impact on the blind recovery of $S$ from $X$. Modelling $S$ as a multidimensional stochastic process, we introduce an informative topology on the space of possible causes underlying a mixture $X$, and show that the behaviour of a generic BSS-solution in response to general deviations from its defining structural assumptions can be profitably analysed in the form of explicit continuity guarantees with respect to this topology. This allows for a flexible and convenient quantification of general model uncertainty scenarios and amounts to the first comprehensive robustness framework for BSS. Our approach is entirely constructive, and we demonstrate its utility with novel theoretical guarantees for a number of statistical applications.
Gradient-based learning in multi-layer neural networks displays a number of striking features. In particular, the decrease rate of empirical risk is non-monotone even after averaging over large batches. Long plateaus in which one observes barely any progress alternate with intervals of rapid decrease. These successive phases of learning often take place on very different time scales. Finally, models learnt in an early phase are typically `simpler' or `easier to learn' although in a way that is difficult to formalize. Although theoretical explanations of these phenomena have been put forward, each of them captures at best certain specific regimes. In this paper, we study the gradient flow dynamics of a wide two-layer neural network in high-dimension, when data are distributed according to a single-index model (i.e., the target function depends on a one-dimensional projection of the covariates). Based on a mixture of new rigorous results, non-rigorous mathematical derivations, and numerical simulations, we propose a scenario for the learning dynamics in this setting. In particular, the proposed evolution exhibits separation of timescales and intermittency. These behaviors arise naturally because the population gradient flow can be recast as a singularly perturbed dynamical system.
Transition systems are often used to describe the behaviour of software systems. If viewed as a graph then, at their most basic level, vertices correspond to the states of a program and each edge represents a transition between states via the (atomic) action labelled. In this setting, systems are thought to be consistent so that at each state formulas are evaluated as either True or False. On the other hand, when a structure of this sort - for example a map where states represent locations, some local properties are known and labelled transitions represent information available about different routes - is built resorting to multiple sources of information, it is common to find inconsistent or incomplete information regarding what holds at each state, both at the level of propositional variables and transitions. This paper aims at bringing together Belnap's four values, Dynamic Logic and hybrid machinery such as nominals and the satisfaction operator, so that reasoning is still possible in face of contradicting evidence. Proof-theory for this new logic is explored by means of a terminating, sound and complete tableaux system.
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191