Wyniki wyszukiwania - Biblioteka Nauki

1

Logic, primes and computation: a tale of unrest

100%

Leonesi S. , Toffalori C.

TASK Quarterly : scientific bulletin of Academic Computer Centre in Gdansk

|

2005

|

tom Vol. 9, No 3

273-291

EN

The early connections between Mathematical Logic and Computer Science date back to the thirties and to the birth itself of modern Theoretical Computer Science, and concern computability. This survey wishes to emphasize how alive and fruitful this relationship has been since then, and still is.

2

Computability in Type-2 Objects with Well-Behaved Type-1 Oracles is p-Normal

100%

Tourlakis G.

Fundamenta Informaticae

|

2001

|

tom Vol. 48, nr 1

83-91

EN

We show that computability in a type-2 object is p-normal if type-1 partial inputs are computed by ``well-behaved oracles''

3

Tissue P Systems with Small Cell Volume

100%

Leporati A. , Manzoni L. , Mauri G. , Porreca A. E. , Zandron C.

Fundamenta Informaticae

|

2017

|

tom Vol. 154, nr 1/4

261--275

EN

Traditionally, P systems allow their membranes or cells to grow exponentially (or even more) in volume with respect to the size of the multiset of objects they contain in the initial configuration. This behaviour is, in general, biologically unrealistic, since large cells tend to divide in order to maintain a suitably large surface-area-to-volume ratio. On the other hand, it is usually the number of cells that needs to grow exponentially with time by binary division in order to solve NP-complete problems in polynomial time. In this paper we investigate families of tissue P systems with cell division where each cell has a small volume (i.e., sub-polynomial with respect to the input size), assuming that each bit of information contained in the cell, including both those needed to represent the multiset of objects and the cell label, occupies a unit of volume. We show that even a constant volume bound allows us to reach computational universality for families of tissue P systems with cell division, if we employ an exponential-time uniformity condition on the families. Furthermore, we also show that a sub-polynomial volume does not suffice to solve NP-complete problems in polynomial time, unless the satisfiability problem for Boolean formulae can be solved in sub-exponential time, and that solving an NP-complete problem in polynomial time with logarithmic cell volume implies P = NP.

4

Uniwersalność systemów funkcyjnych a całkowitość dziedzin funkcji – granice konfliktu i wzajemnego wpływu

100%

Mycka J.

Zagadnienia Filozoficzne w Nauce

|

2017

|

nr 63

31-58

PL

The article presents several examples of different mathematical structures and interprets their properties related to the existence of universal functions. In this context, relations between the problem of totality of elements and possible forms of universal functions are analyzed. Furthermore, some global and local aspects of the mentioned functional systems are distinguished and compared. In addition, the paper attempts to link universality and totality with the dynamic and static properties of mathematical objects and to consider the problem of limitations in the construction of structures combining harmoniously the availability of information at the local and global level.

5

Computing with Infinite Terms and Infinite Reductions

88%

Ketema J. , Simonsen J. G.

Fundamenta Informaticae

|

2019

|

tom Vol. 170, nr 4

339--365

EN

We define computable infinitary rewriting by introducing computability to the study of strongly convergent infinite reductions over infinite first-order terms. Given computable infinitary reductions, we show that descendants and origins-essential to proving fundamental properties such as compression and confluence-are computable across such reductions.

6

Platek spaces

88%

Ivanov L.

Fundamenta Informaticae

|

2000

|

tom Vol. 44, Nr 1,2

145-181

EN

The aim of this work is to axiomatize and enhance the recursion theory on monotonic hierarchies of operative spaces developed. This is to be accomplished by employing a special new variety of operative spaces called Platek spaces. The original structure studied by Platek in corresponds to the particular Platek space with structural class O = w and a bottom operative space consisting of single-valued partial functions over an arbitrary domain (Example 1.1 below). We believe that Platek spaces not only redefine Platek's approach in an abstract manner, but also provide the appropriate setting for an intrinsic Generalized Recursion Theory.

7

Boldface recursion on Platek spaces

88%

Ivanov L.

Fundamenta Informaticae

|

2000

|

tom Vol. 44, Nr 1,2

183-208

EN

The present work develops a boldface version of the theory of Platek spaces initiated. This is done by studying recursion on spaces with special elements which embody the so called transfer operation, Chapter 14 affording full lambda-abstraction. Transfer is characteristic of the monotonic hierarchies of operative spaces, which hierarchies form models of a typed lambda-mu-calculus. The principal result here is a boldface version of the abstract Platek First Recursion Theorem; we prove appropriate boldface Enumeration and Second Recursion Theorems as well.

8

On Computing Bodies

75%

Kelemen J.

Fundamenta Informaticae

|

2007

|

tom Vol. 76, nr 3

337-347

EN

Eco-grammar (EG) systems are proposed as a suitable formal framework for the study of some of the computationally relevant properties of the behavior of collections of embodied agents sharing a common environment and acting in it in simple ways. It is illustrated that the computational power of such systems goes - in certain situations - beyond the traditional limits of the Turing-computability.

9

Gödel’s Philosophical Challenge (to Turing)

75%

Sieg W.

Studia Semiotyczne

|

2020

|

tom 34

|

nr 1

EN

The incompleteness theorems constitute the mathematical core of Gödel’s philosophical challenge. They are given in their “most satisfactory form”, as Gödel saw it, when the formality of theories to which they apply is characterized via Turing machines. These machines codify human mechanical procedures that can be carried out without appealing to higher cognitive capacities. The question naturally arises, whether the theorems justify the claim that the human mind has mathematical abilities that are not shared by any machine. Turing admits that non-mechanical steps of intuition are needed to transcend particular formal theories. Thus, there is a substantive point in comparing Turing’s views with Gödel’s that is expressed by the assertion, “The human mind infinitely surpasses any finite machine”. The parallelisms and tensions between their views are taken as an inspiration for beginning to explore, computationally, the capacities of the human mathematical mind.

10

Algorithmic Completeness of Imperative Programming Languages

75%

Marquer Y.

Fundamenta Informaticae

|

2019

|

tom Vol. 168, nr 1

51--77

EN

According to the Church-Turing Thesis, effectively calculable functions are functions computable by a Turing machine. Models that compute these functions are called Turing-complete. For example, we know that common imperative languages (such as C, Ada or Python) are Turing complete (up to unbounded memory). Algorithmic completeness is a stronger notion than Turing-completeness. It focuses not only on the input-output behavior of the computation but more importantly on the step-by-step behavior. Moreover, the issue is not limited to partial recursive functions, it applies to any set of functions. A model could compute all the desired functions, but some algorithms (ways to compute these functions) could be missing (see [10, 27] for examples related to primitive recursive algorithms). This paper’s purpose is to prove that common imperative languages are not only Turing-complete but also algorithmically complete, by using the axiomatic definition of the Gurevich’s Thesis and a fair bisimulation between the Abstract State Machines of Gurevich (defined in [16]) and a version of Jones’ While programs. No special knowledge is assumed, because all relevant material will be explained from scratch.

11

Flexible and Robust Patterning by Centralized Gene Networks

75%

Vakulenko S. , Radulescu O.

Fundamenta Informaticae

|

2012

|

tom Vol. 118, nr 4

345-369

EN

We investigate the possibility of programming arbitrarily complex space-time patterns, and transitions between such patterns, by gene networks. We consider networks with two types of nodes. The v-nodes, called centers, are hyperconnected and interact one to another via u-nodes, called satellites. This centralized architecture realizes a bow-tie scheme and possesses interesting properties. Namely, this organization creates feedback loops that are capable to generate any prescribed patterning dynamics, chaotic or periodic, or stabilize a number of prescribed equilibrium states. We show that activation or silencing of a node can sharply switch the network dynamics, even if the activated or silenced node is weakly connected. Centralized networks can keep their flexibility, and still be protected against environmental noises. Finding an optimized network that is both robust and flexible is a computationally hard problem in general, but it becomes feasible when the number of satellites is large. In theoretical biology, this class of models can be used to implement the Driesch-Wolpert program, allowing to go from morphogen gradients to multicellular organisms.

12

O różnych sposobach rozumienia analogowości w informatyce

71%

Stacewicz P.

Semina Scientiarum

|

2017

|

tom 16

EN

Two different types of analog computations are discussed in the paper: 1)analog-continuous computations (performed physically upon continuous signals),2) analog-analogical computations (performed naturally by means of socalled natural analogons of mathematical operations). They are analyzed withregard to such questions like: a) are continuous computations physically implementable?b) what is the actual computational power of different analogtechniques? c) can natural (empirical) computations be such reliable as digital?d) is it possible to develop universal analog computers (assuming that theyshould be functionally similar to universal Turing machine)? Presented analysesare rather methodological than formal.

13

On the Dynamics of Cellular Automata with Memory

63%

Martínez G. J. , Adamatzky A. , Alonso-Sanz R.

Fundamenta Informaticae

|

2015

|

tom Vol. 138, nr 1/2

1--16

EN

Elementary cellular automata (ECA) are linear arrays of finite-state machines (cells) which take binary states, and update their states simultaneously depending on states of their closest neighbours. We design and study ECA with memory (ECAM), where every cell remembers its states during some fixed period of evolution. We characterize complexity of ECAM in a case study of rule 126, and then provide detailed behavioural classification of ECAM. We show that by enriching ECA with memory we can achieve transitions between the classes of behavioural complexity. We also show that memory helps to 'discover' hidden information and behaviour on trivial (uniform, periodic), and non-trivial (chaotic, complex) dynamical systems.

14

The Computational and Pragmatic Approach to the Dynamics of Science

51%

Marciszewski W.

Filozofia i Nauka

|

2020

|

tom 8/1

31-67

EN

Sciencemeans here mathematics and those empirical disciplines which avail themselves of mathematical models. The pragmaticapproachis conceived in Karl R. Popper’s The Logic of Scientific Discovery(p.276) sense: a logical appraisal of the success of a theory amounts to the appraisal of its corroboration. This kind of appraisal is exemplified in section 6 by a case study—on how Isaac Newton justified his theory of gravitation. The computationalapproach in problem-solving processes consists in considering them in terms of computability: either as being performed according to a model of computation in a narrower sense, e.g., the Turing machine, or in a wider perspective—of machines associated with a non-mechanical device called “oracle”by Alan Turing (1939). Oracle can be interpreted as computer-theoretic representation of intuitionor invention. Computational approach in an-other sense means considering problem-solving processes in terms of logical gates, supposed to be a physical basis for solving problems with a reasoning.Pragmatic rationalismabout science, seen at the background of classical ration-alism (Descartes, Gottfried Leibniz etc.), claims that any scientific idea, either in empirical theories or in mathematics, should be checked through applications to problem-solving processes. Both the versions claim the existence of abstract objects, available to intellectual intuition. The difference concerns the dynamics of science: (i) the classical rationalism regards science as a stationary system that does not need improvements after having reached an optimal state, while (ii) the pragmatical ver-sion conceives science as evolving dynamically due to fertile interactions between creative intuitions, or inventions, with mechanical procedures.The dynamics of science is featured with various models, like Derek J.de Solla Price’sexponential and Thomas Kuhn’s paradigm model (the most familiar instanc-es). This essay suggests considering Turing’s idea of oracle as a complementary model to explain most adequately, in terms of exceptional inventiveness, the dynam-ics of mathematics and mathematizable empirical sciences.

15

Diagonal Anti-Mechanist Arguments

51%

Kashtan D.

Studia Semiotyczne

|

2020

|

tom 34

|

nr 1

EN

Gödel’s first incompleteness theorem is sometimes said to refute mechanism about the mind. §1 contains a discussion of mechanism. We look into its origins, motivations and commitments, both in general and with regard to the human mind, and ask about the place of modern computers and modern cognitive science within the general mechanistic paradigm. In §2 we give a sharp formulation of a mechanistic thesis about the mind in terms of the mathematical notion of computability. We present the argument from Gödel’s theorem against mechanism in terms of this formulation and raise two objections, one of which is known but is here given a more precise formulation, and the other is new and based on the discussion in §1.

16

The Computational and Pragmatic Approach to the Dynamics of Science

51%

Marciszewski W.

Filozofia i Nauka

|

2020

|

tom 8

|

nr 1

31-67

EN

Science means here mathematics and those empirical disciplines which avail themselves of mathematical models. The pragmatic approach is conceived in Karl R. Popper’s The Logic of Scientific Discovery (p. 276) sense: a logical appraisal of the success of a theory amounts to the appraisal of its corroboration. This kind of appraisal is exemplified in section 6 by a case study-on how Isaac Newton justified his theory of gravitation. The computational approach in problem-solving processes consists in considering them in terms of computability: either as being performed according to a model of computation in a narrower sense, e.g., the Turing machine, or in a wider perspective-of machines associated with a non-mechanical device called “oracle” by Alan Turing (1939). Oracle can be interpreted as computertheoretic representation of intuition or invention. Computational approach in another sense means considering problem-solving processes in terms of logical gates, supposed to be a physical basis for solving problems with a reasoning. Pragmatic rationalism about science, seen at the background of classical rationalism (Descartes, Gottfried Leibniz etc.), claims that any scientific idea, either in empirical theories or in mathematics, should be checked through applications to problem-solving processes. Both the versions claim the existence of abstract objects, available to intellectual intuition. The difference concerns the dynamics of science: (i) the classical rationalism regards science as a stationary system that does not need improvements after having reached an optimal state, while (ii) the pragmatical version conceives science as evolving dynamically due to fertile interactions between creative intuitions, or inventions, with mechanical procedures. The dynamics of science is featured with various models, like Derek J. de Solla Price’s exponential and Thomas Kuhn’s paradigm model (the most familiar instances). This essay suggests considering Turing’s idea of oracle as a complementary model to explain most adequately, in terms of exceptional inventiveness, the dynamics of mathematics and mathematizable empirical sciences.

17

On Accelerations in Science Driven by Daring Ideas: Good Messages from Fallibilistic Rationalism

51%

Marciszewski W.

Studies in Logic, Grammar and Rhetoric

|

2015

|

tom 40

|

nr 1

19-41

EN

The first good message is to the effect that people possess reason as a source of intellectual insights, not available to the senses, as e.g. axioms of arithmetic. The awareness of this fact is called rationalism. Another good message is that reason can daringly quest for and gain new plausible insights. Those, if suitably checked and confirmed, can entail a revision of former results, also in mathematics, and - due to the greater efficiency of new ideas - accelerate science’s progress. The awareness that no insight is secured against revision, is called fallibilism. This modern fallibilistic rationalism (Peirce, Popper, Gödel, etc. oppose the fundamentalism of the classical version (Plato, Descartes etc.), i.e. the belief in the attainability of inviolable truths of reason which would forever constitute the foundations of knowledge. Fallibilistic rationalism is based on the idea that any problem-solving consists in processing information. Its results vary with respect to informativeness and its reverse - certainty. It is up to science to look for highly informative solutions, in spite of their uncertainty, and then to make them more certain through testing against suitable evidence. To account for such cognitive processes, one resorts to the conceptual apparatus of logic, informatics, and cognitive science.