Theory of Computation, Misc

Here, by introducing a version of “Unexpected hanging paradox” first we try to open a new way and a new explanation for paradoxes, similar to liar paradox. Also, we will show that we have a semantic situation which no syntactical logical system could support it. Finally, we propose a claim in Theory of Computation about the consistency of this Theory. One of the major claim is:Theory of Computation and Classical Logic leads us to a contradiction.

The reason ability of considering time as a fuzzy concept is demonstrated in [7],[8]. One of the major questions which arise here is the new definitions of Complexity Classes. In [1],[2],…,[11] we show why we should consider time a fuzzy concept. It is noticeable to mention that that there were many attempts to consider time as a Fuzzy concept, in Philosophy, Mathematics and later in Physics but mostly based on the personal intuition of the authors or as a style of (...) Fuzzifying different various of the concepts. Consequently, fuzzifying time doesn’t go to be popular. In the new attempts we are trying to show why we are somewhat forced to consider time as a Fuzzy concept. It is mostly based on the “Unexpected Hanging Paradox” introduced by a Swedish Mathematician Lennart Ekbom. Our question is:” what will be the impact of it in Theory of Computation and Physics?”. Here, we discuss about the impact of fuzzifying time on Theory of Computation. (shrink)

This is our journal for developing Deduction Theory and studying Deep Learning and Artificial intelligence. Deduction Theory is a Theory of Deducing World’s Relativity by Information Coupling and Asymmetry. We focus on information processing, see intelligence as an information structure that relatively close object-oriented, probability-oriented, unsupervised learning, relativity information processing and massive automated information processing. We see deep learning and machine learning as an attempt to make all types of information processing relatively close to probability information processing. We will discuss (...) about how to understand Deep Learning and Artificial intelligence and why Deep Learning is shown better performance than the other methods by metaphysical logic. (shrink)

Cuốn tài liệu học thuật trình bày phương pháp “BMF analytics” hiện đã bước sang năm thứ ba phục vụ cộng đồng nghiên cứu. Cuốn sách đã góp phần hỗ trợ nhiều nhà nghiên cứu trẻ triển khai và hoàn thành công việc.

The van Wijngaarden grammars are two-level grammars that present many interesting properties. In the present article I elaborate on six of these properties, to wit, (i) their being constituted by two grammars, (ii) their ability to generate (possibly infinitely many) strict languages and their own metalanguage, (iii) their context-sensitivity, (iv) their high descriptive power, (v) their productivity, or the ability to generate an infinite number of production rules, and (vi) their equivalence with the unrestricted, or Type-0, Chomsky grammars.

This is the 3rd edition. Although a number of new technological applications require classical deductive computation with non-classical logics, many key technologies still do well—or exclusively, for that matter—with classical logic. In this first volume, we elaborate on classical deductive computing with classical logic. The objective of the main text is to provide the reader with a thorough elaboration on both classical computing – a.k.a. formal languages and automata theory – and classical deduction with the classical first-order predicate calculus with (...) a view to computational implementations, namely in automated theorem proving and logic programming. The present third edition improves on the previous ones by providing an altogether more algorithmic approach: There is now a wholly new section on algorithms and there are in total fourteen clearly isolated algorithms designed in pseudo-code. Other improvements are, for instance, an emphasis on functions in Chapter 1 and more exercises with Turing machines. (shrink)

We study the structure of families of theories in the language of arithmetic extended to allow these families to refer to one another and to themselves. If a theory contains schemata expressing its own truth and expressing a specific Turing index for itself, and contains some other mild axioms, then that theory is untrue. We exhibit some families of true self-referential theories that barely avoid this forbidden pattern.

Doy una revisión detallada de ' los límites externos de la razón ' por Noson Yanofsky desde una perspectiva unificada de Wittgenstein y la psicología evolutiva. Yo indiqué que la dificultad con cuestiones como la paradoja en el lenguaje y las matemáticas, la incompletitud, la indeterminación, la computabilidad, el cerebro y el universo como ordenadores, etc., surgen de la falta de mirada cuidadosa a nuestro uso del lenguaje en el adecuado contexto y, por tanto, el Error al separar los problemas (...) de hecho científico de las cuestiones de cómo funciona el lenguaje. Discuto las opiniones de Wittgenstein sobre la incompletitud, la paracoherencia y la indecisión y el trabajo de Wolpert en los límites de la computación. Resumiendo: el universo según Brooklyn---buena ciencia, no tan buena filosofía. Aquellos que deseen un marco completo hasta la fecha para el comportamiento humano de la moderna dos sistemas punto de vista puede consultar mi libros Talking Monkeys 3ª ed (2019), Estructura Logica de Filosofia, Psicología, Mente y Lenguaje en Ludwig Wittgenstein y John Searle 2ª ed (2019), Suicidio pela Democracia 4ª ed (2019), La Estructura Logica del Comportamiento Humano (2019), The Logical Structure de la Conciencia (2019, Entender las Conexiones entre Ciencia, Filosofía, Psicología, Religión, Política y Economía (2019), Delirios Utópicos Suicidas en el siglo 21 5ª ed (2019), Observaciones sobre Imposibilidad, Incompletitud, Paraconsistencia, Indecidibilidad, Aleatoriedad, Computabilidad, Paradoja e Incertidumbre en Chaitin, Wittgenstein, Hofstadter, Wolpert, Doria, da Costa, Godel, Searle, Rodych Berto, Floyd, Moyal-Sharrock y Yanofsky y otros. (shrink)

Numerous problems arising in engineering applications can have several objectives to be satisfied. An important class of problems of this kind is lexicographic multi-objective problems where the first objective is incomparably more important than the second one which, in its turn, is incomparably more important than the third one, etc. In this paper, Lexicographic Multi-Objective Linear Programming (LMOLP) problems are considered. To tackle them, traditional approaches either require solution of a series of linear programming problems or apply a scalarization of (...) weighted multiple objectives into a single-objective function. The latter approach requires finding a set of weights that guarantees the equivalence of the original problem and the single-objective one and the search of correct weights can be very time consuming. In this work a new approach for solving LMOLP problems using a recently introduced computational methodology allowing one to work numerically with infinities and infinitesimals is proposed. It is shown that a smart application of infinitesimal weights allows one to construct a single-objective problem avoiding the necessity to determine finite weights. The equivalence between the original multi-objective problem and the new single-objective one is proved. A simplex-based algorithm working with finite and infinitesimal numbers is proposed, implemented, and discussed. Results of some numerical experiments are provided. (shrink)

This paper presents proof that Buss's S22 can prove the consistency of a fragment of Cook and Urquhart's PV from which induction has been removed but substitution has been retained. This result improves Beckmann's result, which proves the consistency of such a system without substitution in bounded arithmetic S12. Our proof relies on the notion of "computation" of the terms of PV. In our work, we first prove that, in the system under consideration, if an equation is proved and either (...) its left- or right-hand side is computed, then there is a corresponding computation for its right- or left-hand side, respectively. By carefully computing the bound of the size of the computation, the proof of this theorem inside a bounded arithmetic is obtained, from which the consistency of the system is readily proven. This result apparently implies the separation of bounded arithmetic because Buss and Ignjatović stated that it is not possible to prove the consistency of a fragment of PV without induction but with substitution in Buss's S12. However, their proof actually shows that it is not possible to prove the consistency of the system, which is obtained by the addition of propositional logic and other axioms to a system such as ours. On the other hand, the system that we have considered is strictly equational, which is a property on which our proof relies. (shrink)

Engineers fine-tune the design of robot bodies for control purposes, however, a methodology or set of tools is largely absent, and optimization of morphology (shape, material properties of robot bodies, etc.) is lagging behind the development of controllers. This has become even more prominent with the advent of compliant, deformable or ”soft” bodies. These carry substantial potential regarding their exploitation for control—sometimes referred to as ”morphological computation”. In this article, we briefly review different notions of computation by physical systems and (...) propose the dynamical systems framework as the most useful in the context of describing and eventually designing the interactions of controllers and bodies. Then, we look at the pros and cons of simple vs. complex bodies, critically reviewing the attractive notion of ”soft” bodies automatically taking over control tasks. We address another key dimension of the design space—whether model-based control should be used and to what extent it is feasible to develop faithful models for different morphologies. (shrink)

“Filter bubble”, “echo chambers”, “information diet” – the metaphors to describe today’s information dynamics on social media platforms are fairly diverse. People use them to describe the impact of the viral spread of fake, biased or purposeless content online, as witnessed during the recent race for the US presidency or the latest outbreak of the Ebola virus (in the latter case a tasteless racist meme was drowning out any meaningful content). This unravels the potential envisioned to arise from emergent activities (...) of human collectives on the World Wide Web, as exemplified by the Arab Spring mass movements or digital disaster response supported by the Ushahidi tool suite. (shrink)

Engineers fine-tune the design of robot bodies for control purposes; however, a methodology or set of tools is largely absent, and optimization of morphology is lagging behind the development of controllers. This has become even more prominent with the advent of compliant, deformable or ‘soft’ bodies. These carry substantial potential regarding their exploitation for control—sometimes referred to as ‘morphological computation’. In this article, we briefly review different notions of computation by physical systems and propose the dynamical systems framework as the (...) most useful in the context of describing and eventually designing the interactions of controllers and bodies. Then, we look at the pros and cons of simple versus complex bodies, critically reviewing the attractive notion of ‘soft’ bodies automatically taking over control tasks. We address another key dimension of the design space—whether model-based control should be used and to what extent it is feasible to develop faithful models for different morphologies. (shrink)

Motivated by the significant amount of successful collaborative problem solving activity on the Web, we ask: Can the accumulated information propagation behavior on the Web be conceived as a giant machine, and reasoned about accordingly? In this paper we elaborate a thesis about the computational capability embodied in information sharing activities that happen on the Web, which we term socio-technical computation, reflecting not only explicitly conditional activities but also the organic potential residing in information on the Web.

Context: At present, we lack a common understanding of both the process of cognition in living organisms and the construction of knowledge in embodied, embedded cognizing agents in general, including future artifactual cognitive agents under development, such as cognitive robots and softbots. Purpose: This paper aims to show how the info-computational approach (IC) can reinforce constructivist ideas about the nature of cognition and knowledge and, conversely, how constructivist insights (such as that the process of cognition is the process of life) (...) can inspire new models of computing. Method: The info-computational constructive framework is presented for the modeling of cognitive processes in cognizing agents. Parallels are drawn with other constructivist approaches to cognition and knowledge generation. We describe how cognition as a process of life itself functions based on info-computation and how the process of knowledge generation proceeds through interactions with the environment and among agents. Results: Cognition and knowledge generation in a cognizing agent is understood as interaction with the world (potential information), which by processes of natural computation becomes actual information. That actual information after integration becomes knowledge for the agent. Heinz von Foerster is identified as a precursor of natural computing, in particular bio computing. Implications: IC provides a framework for unified study of cognition in living organisms (from the simplest ones, such as bacteria, to the most complex ones) as well as in artifactual cognitive systems. Constructivist content: It supports the constructivist view that knowledge is actively constructed by cognizing agents and shared in a process of social cognition. IC argues that this process can be modeled as info-computation. (shrink)

Tailoring the design of robot bodies for control purposes is implicitly performed by engineers, however, a methodology or set of tools is largely absent and optimization of morphology (shape, material properties of robot bodies, etc.) is lag- ging behind the development of controllers. This has become even more prominent with the advent of compliant, deformable or "soft" bodies. These carry substantial potential regarding their exploitation for control – sometimes referred to as "mor- phological computation" in the sense of offloading computation (...) needed for control to the body. Here, we will argue in favor of a dynamical systems rather than com- putational perspective on the problem. Then, we will look at the pros and cons of simple vs. complex bodies, critically reviewing the attractive notion of “soft” bodies automatically taking over control tasks. We will address another key dimension of the design space – whether model-based control should be used and to what extent it is feasible to develop faithful models for different morphologies. ----- This paper was also published in the 2014 AISB proceedings http://aisb50.org/representation-of-reality-humans-animals-and-machines/ - http://doc.gold.ac.uk/aisb50/. (shrink)

In this paper we analyze methodological and philosophical implications of algorithmic aspects of unconventional computation. At first, we describe how the classical algorithmic universe developed and analyze why it became closed in the conventional approach to computation. Then we explain how new models of algorithms turned the classical closed algorithmic universe into the open world of algorithmic constellations, allowing higher flexibility and expressive power, supporting constructivism and creativity in mathematical modeling. As Goedels undecidability theorems demonstrate, the closed algorithmic universe restricts (...) essential forms of mathematical cognition. In contrast, the open algorithmic universe, and even more the open world of algorithmic constellations, remove such restrictions and enable new, richer understanding of computation. (shrink)

The paper investigates how the mathematical languages used to describe and to observe automatic computations influence the accuracy of the obtained results. In particular, we focus our attention on Single and Multi-tape Turing machines which are described and observed through the lens of a new mathematical language which is strongly based on three methodological ideas borrowed from Physics and applied to Mathematics, namely: the distinction between the object (we speak here about a mathematical object) of an observation and the instrument (...) used for this observation; interrelations holding between the object and the tool used for the observation; the accuracy of the observation determined by the tool. Results of the observation executed by the traditional and new languages are compared and discussed. (shrink)

Este estudio del lenguaje natural, realizado desde la observación, permite analizar los aspectos subjetivos que le dan origen al lenguaje, y que posibilitan su adquisición y comprensión. Como tal constituye la primera teoría realmente original aparecida en los últimos 55 años, luego que Chomsky nos hiciera conocer su gramática generativa (1957), con la diferencia que, en este caso, tiene el soporte de una lógica también original, la Lógica Transcursiva. Esta lógica se basa en una modificación de la lógica policontextural de (...) Günther (1959), la primera y única herramienta conocida, para abordar los aspectos subjetivos, o aquellos de los que no se ocupa la ciencia tradicional. En este trabajo, además, se hace una introducción a la primera teoría de la psiquis con base científica, cuyo único antecedente lo constituye el Proyecto que Freud concibiera en 1895. (shrink)

Many cognitive scientists, having discovered that some computational-level characterization f of a cognitive capacity φ is intractable, invoke heuristics as algorithmic-level explanations of how cognizers compute f. We argue that such explanations are actually dysfunctional, and rebut five possible objections. We then propose computational-level theory revision as a principled and workable alternative.

There exist many applications where it is necessary to approximate numerically derivatives of a function which is given by a computer procedure. In particular, all the fields of optimization have a special interest in such a kind of information. In this paper, a new way to do this is presented for a new kind of a computer - the Infinity Computer - able to work numerically with finite, infinite, and infinitesimal number. It is proved that the Infinity Computer is able (...) to calculate values of derivatives of a higher order for a wide class of functions represented by computer procedures. It is shown that the ability to compute derivatives of arbitrary order automatically and accurate to working precision is an intrinsic property of the Infinity Computer related to its way of functioning. Numerical examples illustrating the new concepts and numerical tools are given. (shrink)

Traditional computers work with finite numbers. Situations where the usage of infinite or infinitesimal quantities is required are studied mainly theoretically. In this paper, a recently introduced computational methodology (that is not related to the non-standard analysis) is used to work with finite, infinite, and infinitesimal numbers numerically. This can be done on a new kind of a computer – the Infinity Computer – able to work with all these types of numbers. The new computational tools both give possibilities to (...) execute computations of a new type and open new horizons for creating new mathematical models where a computational usage of infinite and/or infinitesimal numbers can be useful. A number of numerical examples showing the potential of the new approach and dealing with divergent series, limits, probability theory, linear algebra, and calculation of volumes of objects consisting of parts of different dimensions are given. (shrink)

Immanuel Kant famously defined philosophy to be about three questions: “What can I know? What should I do? What can I hope for?” (KrV, B833). I want to suggest that the three questions of our course on the philosophy of computing are: What is computing? What should we do with computing? What could computing do?

We extend Barbanera and Berardi's symmetric lambda calculus [2] to second-order classical propositional logic and prove its strong normalization.

In a series of articles we try to show the need of a novel Theory for Theory of Computation based on considering time as a Fuzzy concept. Time is a central concept In Physics. First we were forced to consider some changes and modifications in the Theories of Physics. In the second step and throughout this article we show the positive Impact of this modification on Theory of Computation and Complexity Theory to rebuild it in a more successful and fruitful (...) approach. We call this novel Theory TC*. (shrink)

در تکوین نظریه محاسبات از اوایل قرن بیستم پارادکسها و خود ارجاعی نقش ویژه ای را بازی کرده اند. هر چند نظریه محاسبات عام بر اساس تعریف ماشین تورینگ، فرض تورینگ_چرچ و کاربردهای آن بنا شده ،اما از همان ابتدا تا به امروز منطق و حوزه های مختلف این علم در ارتباط تنگاتنگ با این تیوری و در ابتدا نظریه محاسبات خاص بوده و این ارتباط روز به روز گسترده و گسترده تر گشته است. از تاثیر پارادوکس دروغگو و پارادکس (...) بری در تمایز میان مفهوم محاسبه پذیر و محاسبه پذیر شمارایانه، قضایای گودل و قضیه چیتین همه جا شاهد این تاثیر و تاثر متقابل هستیم. در این مقال می خواهیم بعد از معرفی اجمالی مطالب باال، تاثیر یک پارادوکس دیگر، پارادوکس اعدام غیر منتظره، را بر این نظریه بررسی نماییم. (shrink)

Here, we give the second proof for TC+CON(TC∗)ͰP≠NP . The first proof is in [1]. In the second proof, we do not employ the concept of scope.

This is a Turing Machine which computes the exponential function f(x,y) = xˆy. Instructions format and operation of this machine are intended to best reflect the basic conditions outlined by Alan Turing in his On Computable Numbers, with an Application to the Entscheidungsproblem (1936), using the simplest single-tape and single-symbol version, in essence due to Kleene (1952) and Carnielli & Epstein (2008). This machine is composed by four basic task machines: one which checks if exponent y is zero, a second (...) which checks if base x is zero, a third that is able to copy the base, and a fourth able to multiply multiple factors (in this case, factors will be all equal). They were conveniently separated in order to ease the reader's task to understand each step of its operation. We adopt the convention that a number n is represented by a string of n+1 symbols "1". Thus, an entry (x, y) will be represented by two respective strings of x+1 and y+1 symbols "1", separated by a single "0" (or a blank), and as an output, this machine will generate a string of (xˆy)+1 symbols "1". Some of the instructions are followed by a brief description of what's going on. (shrink)

When we understand that every potential halt decider must derive a formal mathematical proof from its inputs to its final states previously undiscovered semantic details emerge. -/- When-so-ever the potential halt decider cannot derive a formal proof from its input strings to its final states of Halts or Loops, undecidability has been decided. -/- The formal proof involves tracing the sequence of state transitions of the input TMD as syntactic logical consequence inference steps in the formal language of Turing Machine (...) Descriptions. (shrink)