Loading....
Recent Article links:

Category 'Complexity'

Swarm Games

Carlos Gershenson, a friend of mine, has developed a suite of games with NetLogo for entertainment at parties. The games have to do with patterns that emerge as a result of the iterative application of  very simple rules by humans or other mobile agents.

games
Individuals are provided with a single, simple rule at the outset. The outcomes are sometimes independent of the initial conditions and sometimes sensitive to them, but nobody can anticipate them  (except perhaps Carlos and other complexity researchers).Some of the rules are as follows:
- “Approach one”: Each player chooses another player and approaches them one step at a time.  [ Some people ended up in the center of the room while others were  grouped in clusters.]
- “Retreat from one”: Each player chooses another player and then runs away from them. [Everybody ended up on the periphery of the room.]
- “Step between two”: Each player chooses two players, and tries to step  between them. [I had no idea what would happen. As it turned out, everybody ended up in a single tight cluster in the center of the room.]If different rules are issued to different individuals, interesting patterns emerge.

Recently, the New York Times  published an interesting article entitled “From Ants to People, an Instinct to Swarm” with graphs of ants that strikingly resemble  Carlos’ simulations.

Swarm NYT
As the article points out, people in the U.S. spend 3.7 billion hours a year in congested traffic, but you will never see ants stuck in gridlock. Carlos has himself  worked on improving traffic lights using auto-organization techniques. He recently earned his PhD with a thesis on the subject. Titled 
Design and Control of Self-organizing Systems
, it has been published online as as ebook under a CopyLeft licence. It is an enjoyable work.References:
Gershenson, Carlos. Design and Control of Self-organizing Systems. CopIt ArXives, Mexico, 2007. TS0002ENFrom Ants to People, an Instinct to Swarm. New York Times, 2007.

Carlos Gershenson’s suite of games in NetLogo.

On the Foundations of Quantum Mechanics, The Netherlands


Originally uploaded by hzenilc.

Models and Simulations 2
11 – 13 October 2007
Tilburg University, The Netherlands

I attended this conference one month ago. Among several interesting talks, one in particular caught my attention. It was given by Michael Seevinck from the Institute for History and Foundations of Science at Utrecht, The Netherlands. His talk was about the foundations of Quantum Mechanics, and there were many NKS related topics that it brought  to mind. He talked about reconstructing Quantum Mechanics (QM) from scratch by exploring several restricted models in order to solve the so-called measurement problem, to deal with the nonlocality of quantum correlations, and with its alleged non-classicality, there being  no consensus on  the meaning of Quantum Mechanics  (Niels Bohr said once: “If you think you have understood quantum mechanics, then you have not understood quantum mechanics.”—More quotes of this sort on QM here).  The restrictons chosen in order to reconstruct the theory must be physical principles and not  theoretical assumptions. In other words, one approaches the problem contrariwise than is traditional, taking the least possible restrictions and exploring the theories that can be built thereon. The speaker characterized  this approach  as the “study [of]  a system from the outside” in order to ”reconstruct the model”. It is basically a pure NKS approach: “Start from a general class of possible models and try to constrain it using some physical principles so as to arrive at the model in question (in this case QM).”

One can then proceed to ask such questions as how one might identify QM uniquely, what it is that makes QM quantum, what set of axioms in the model is to be used, and which of them are necessary and sufficient? The question of meaning, previously asked of the formalism, is removed, and bears, if at all, only on the selection and justification of  first principles. Seevinck came up with the following interesting statement: “The partially ordered set of all questions in QM is isomorphic to the partially ordered set of all closed subspaces of a separable Hilbert space” (one of Mackey’s axioms in his axiomatisation of 1957). He added: “They (the principles)have solely an epistemic status. The personal motives for adopting certain first principles should be bracketed. One should be ontologically agnostic. The principles should be free of ontological commitment.” And further: “…axioms are neutral towards philosophical positions: they can be adopted by a realist, instrumentalist, or subjectivist.” He cited Clifton, Bub and Halverson who provided the following quantum information constraints used to derive quantum theory:

1. No superluminal information transfer via measurement.

2. No broadcasting

3. No secure bit commitment

Seevinck’s methodology in further detail is: Start with a general reconstruction model with a very weak formalism. Gradually see what (quantum) features are consequences of what added physical principles, and also see which features are connected and which features are a consequence of adding which principle. One thereby learns which principle is responsible for which element in the (quantum) theoretical structure.

One can generate further foundational questions over the whole space of restricted models, e.g.  how many of them:

- forbid superluminal signalling?

- allow nonlocality, and to what extent?

- solve NP-complete problems in polynomial time?

An important question which arises concerns whether intrinsic randomness would be of a different nature in different models or whether all of them would yield to deterministic randomness.

His talk slides are available online. Highly recommended.

Among other interesting people I met was Rafaela Hillebrand, of  the Institute for The Human Future at Oxford University. The Institute’s director, Nick Bostrom, has proposed an interesting theory concerning the likelihood that our reality is actually  a computer simulation. I have myself approached the  question in my work on experimental algorithmic complexity, in particular in my work on  the testability and the skepticism content of the simulation hypothesis. I will post on that subject later. The subject of thought experiments–in which I have an interest– was one that came up frequently.

On the simplest and smallest universal Turing machine

Why research on the universality of the Wolfram 2,3 Turing machine (http://www.wolframscience.com/prizes/tm23/) and the small universal Turing machine  is relevant for modern computer science:

* New techniques for proving universality are being developed (Alex Smith’s novel approach for unbounded computations from arbitrary lengths and non-periodic initial configurations).
* Completely new universal systems have been discovered (cyclic tag- systems, bi-tag systems).
* Such research provides a better understanding of universality,  its limits, its  underlying principles and its necessary and sufficient conditions.
* It is a base for actually building universal devices when only a few elements can be used, e.g. in nanotechnology or molecular computation.
* Simple/small machines may be more easily/effectively embedded in other systems.
* The old discovery/invention duality question comes to the fore: It sheds light on how simple universality is, how frequently it occurs, whether  it is engineered or not, whether  one builds universal computation or finds it in the universe.
* It could shed light on the relative feasibility of  universal Turing machines based on different tape configurations (e.g. blank characters, repetitive words, non-repetitive with computationally simple backgrounds) as actual physical systems.  At present it is not at all clear why one ought to  favor blank characters over other possible real-world backgrounds, such as “noise.”
* Questions of size and complexity  arise: It would be interesting, for instance, to find out whether there is a polynomial (or exponential) trade-off between program size and and the concept of simulating a process.
* Some questions  on algorithmic complexity arise: Will the encoding always be more complex if the machine is simpler? All theorems in algorithmic information theory depend on additive constants, which depend on the sizes of typical universal Turing machines. What is the impact of different generalizations of universality on algorithmic complexity and what is the role of  encoding in such a measure?
* Some questions arise on the relation between several variants of universality definitions: Is there an effective and efficient encoding for each non-periodic encoding preserving universality? If so, how does this impact their complexity? Is there a non-periodic encoding with blank characters for each periodic blank word encoding, and what would the impact of such  an encoding be on the size/complexity of the Turing machine in question?

The field is active and still an important area of research. Several computer science conferences include talks on small computational systems. For instance, Computability in Europe (CiE) and Machines, Computations and Universality (MCU) included such talks this year, focusing in particular on reversible cellular automata and universal Turing machines.

Here are some references from the small Turing machine community, some of them very recent:

[1] Manfred Kudlek. Small deterministic Turing machines. Theoretical Computer Science, 168(2):241-255, November 1996.
[2] Manfred Kudlek and Yurii Rogozhin. A universal Turing machine with 3 states and 9 symbols. In Werner Kuich, Grzegorz Rozenberg, and Arto Salomaa, editors, Developments in Language Theory (DLT) 2001, vol. 2295 of LNCS, pp. 311-318, Vienna, May 2002. Springer.
[3] Maurice Margenstern and Liudmila Pavlotskaya. On the optimal number of instructions for universality of Turing machines connected with a finite automaton. International Journal of Algebra and Computation, 13(2):133-202, April 2003.
[4] Claudio Baiocchi. Three small universal Turing machines. In Maurice Margenstern and Yurii Rogozhin, editors, Machines, Computations, and Universality (MCU), volume 2055 of LNCS, pp. 1-10, Chisinau Moldavia, May 2001. Springer.
[5] Turlough Neary and Damien Woods. Four small universal Turing machines. Machines, Computations, and Universality (MCU), volume 4664 of LNCS, pp. 242-254, Orleans, France, September 2007. Springer.
[6] Yurii Rogozhin. Small universal Turing machines. Theoretical Computer Science, 168(2):215-240, November 1996.
[7] Shigeru Watanabe. 5-symbol 8-state and 5-symbol 6-state universal Turing machines. Journal of the ACM, 8(4):476-483, October 1961.
[8] Shigeru Watanabe. 4-symbol 5-state universal Turing machines. Journal of Information Processing Society of Japan, 13(9):588-592, 1972.
[9] Stephen Wolfram. A New Kind of Science. Wolfram Media, 2002.

I will post more later on Alex Smith’s contribution after the proof he provided to prove the universality of Wolfram’s 2,3 Turing machine.

Dictionaries, analytical knowledge and new approaches to translating.

When I realized that a dictionary, as a whole, could be viewed as a non -syntactical knowledge container, in other words, that there was  no new knowledge in it, I wondered how something that was such a perfect auto-referential source could actually be useful.  For since every word is defined by other words in the same language, looking up the meaning of a given word would lead you to other words and yet others and eventually back to the first word, the word whose meaning you set out to learn. This would be the case even if  the dictionary were bilingual, and the meaning of the word you wished to check was given in a second language. Thus all dictionaries are perfectly circular, closed, auto-referential sources. However, I discovered that the analytical knowledge in a dictionary comes from the net supporting words connected with each other. Thus  if “chair” is strongly connected with “table”, “office”, “dining room”, etc. it should be easy to map it to its equivalent in any other language. Of course this overlooks languages in which the word “chair” does not exist,  reflecting the lack of  a comparable object in the culture and thus the lack of a cognitive representation of it. But such instances are rare since most cultures share a basic physical reality and human experience.

Of course problems arise with  words like  “personne” in French, which  maps onto “persona” and “nadie” in Spanish,  a noun and an adjective respectively with completely different connections and different supporting nets. Or conversely, when the verb “gustar” from Spanish maps onto”gouter” and “plaire” in French.  So even when it seems that all words are surjective, the general case is not bijective, and that applies to homonyms too, which often creates ambiguities in translation. In other words, any word in any language has its equivalent in any other language, whether a single word in one langauge becomes two or more words in another, or whether two or more words become one after mapping– but one word could mean two completely different things in another language. However, the supporting network  would be able to uncover this fact and solve a possible ambuiguity based on  context by extending the word network to encompass the ambiguity. In other words, if a subnet cannot be uniquely mapped, extending it should eventually solve the ambiguity. What one would need  is a corpus big enough to build such a network once and for all and then simply make comparisons at the network level. This could work even for completely new or unknown languages, either dead or living, assuming that they share a part of our actual reality and hence some part of our mental representations  (In a sense this is what Champollion did when he deciphered the Rosetta stone– he discovered a partial mapping of a subnetwork of words from an unknown language - Egyptian - to a subnetwork of a known one - Greek ). In the final analysis, each language has a single unique network (changing slightly through time but remaining well connected and strong enough to make  it unique and recognizable while being isomorphic with that of any other language).  Thus an entire language could be identified by its fingerprint -its network.

Having  established that, what about mining the world of all possible meanings, the world of all possible translations, and the world of all possible ideas? We wouldn’t have the problem of distinguishing between a coherent idea and a non-coherent one since the network would provide some minimal coherence. Thus the net-into-the -net approach would give us a way of translating from word to word and from phrase to phrase and from idea to idea.

The above ideas would apply to unilingual dictionaries, lets say English-English. The analytical knowledge in them again comes from the net connecting the words, so even if someone does not know English at all I would say that he would be able, albeit with considerable difficulty, to learn English just by deducing the net connecting objects, in other words, by mapping his own mental  representations of objects onto words in the  English dictionary. In the process he could encounter some ambiguities, but the further he goes, the more of these he would be able to resolve. On the other hand,  speakers of those languages in which “chair” does not exist, both in the language itself and as a real object in the culture,   would be able to deduce what  a chair is by tracking its  relations with the objects they know and for which they do have mental representations and the phonemes to externalize them. So the problem of translation, which began with the mapping of word onto word and then phrase onto phrase  with statistical tools,  becomes with this approach a matter of  mapping net to net.  Indeed this seems to be the approach adopted  by Meaningful Machines http://www.meaningfulmachines.com/-.  Such ideas have been around for a while, for example at WordNet: wordnet.princeton.edu/, but they somehow remain old-fashioned even as they are shifting the paradigm.

These ideas could be carried to the limit by taking the sum total of human languages and enquiring into the mapping between such a network and our cognitive representations. Such a move would provide grounds  for rebutting the Chinese room argument, since in the end it does not matter whether someone inside the room has no knowledge at all of a language; he would be able to map what he is mechanically translating onto his own mental representations, generating what, according to the argument, could not be generated: understanding. Because Searle’s  idea was, as I recall, to build up a case against A.I. in terms of the Turing test.

My conclusion: Meaning resides in the net.

This post is  related to a previous post titled “Meaning against A.I.”: http://www.mathrix.org/liquid/?p=29

Seth Lloyd’s answers to my questions

mathematiker.jpg

The original questions were posted here.

From Dr. Seth Lloyd’s answers it is clear that:
1) he is assuming the Deutsch quantum computing model, which is Turing reducible and
2) he is assuming that quantum particles encode a finite amount of information, so that they are completely discrete in every possible sense, including: space/time, mass, energy, momentum, and any other possible physical value.

1 and 2 are, by the way,  standard views in both fields, quantum computing (defined by David Deutsch) and quantum mechanics (as defined by several authors). From 1 and 2 it can be deduced that Seth Lloyd indirectly implies that the universe is Turing computable (since the only difference between a quantum computer and a Turing machine -disregarding the usual fact about the infinite tape- is the run time, a fact borne out by his answers). Regarding 2, most quantum quantities and solutions to equations suggest that there are minimum values, namely the Planck time and the Planck length, a fact which assorts well with a discrete scenario. However the issue is commonly bypassed by physicists and by the theory itself. In other words, quantum mechanics seems to be consistent with both a continuum and a  discrete universe and does not offer final evidence or an ultimate theoretical conclusion one way or the other. In fact it is usual among physicists to think of  superposition as an entanglement in a space continuum, which would allow  a particle to be in an infinite number of  states simultaneously.

From 1 and 2 we can conclude that Church’s thesis–in both its weak and strong non-physical and physical versions, which we will discuss in a separate post– remains intact  even when Dr. Lloyd’s approach is closer to a physical basis (an accepted modern model of the universe) and of course the empirical data (which supports quantum mechanics itself). His chain of reasoning is basicaly as follows:

a&b->c:

a) the universe is completely describable by quantum mechanics
b)  standard quantum computing completely captures quantum mechanics
c) therefore the universe is a quantum computer.

He proved a relation between a and b, which probably puts the standard (or some standard) theory of quantum mechanics and the standard quantum computing model in an isomorphic relation with each other. Here “standard” means that some assumptions were made.

Here is a literal transcription of the answers to my questions given by Dr. Seth Lloyd:
—–
A: A quantum computer differs from a Turing machine in that its bits are quantum bits, and so can exist in a superposition. In addition, it can be instructed to put those bits in superpositions. These two features make a quantum computer apparently much more powerful than an ordinary Turing machine. What a quantum computer does is still Turing computable, but a typical quantum computation of T steps on N qubits requires O(2^N) bits on a classical Turing machine, and O(T 2^2N )logical operations. That is, it takes a Turing machine exponential amounts of time and space to simulate a quantum computer or quantum Turing machine. (Compare the definition of universality: a universal Turing machine can simulate any other Turing machine in polynomial time.)
So a quantum computer is apparently more powerful than a classical computer.
There is a perfectly good definition of a quantum Turing machine (basically, a Turing machine with qubits and extra instructions to put those qubits in superposition, as above). A universal quantum computer is a physical system that can be programmed (i.e., whose state can be prepared) to simulate any quantum Turing machine. The laws of physics support universal quantum computation in a straightforward way, which is why my colleagues and I can build quantum computers. So the universe is at least as powerful as a universal quantum computer. Conversely, a number of years ago I proved that quantum computers could simulate any quantum system precisely, including one such as the universe that abides by the standard model. Accordingly, the universe is no more computationally powerful than a quantum computer.

A: As long as a quantum particle encodes 3, 4, or M states, where M is a finite number, then the computational picture remains the same (this is also true classically). Now, it is a fact that a physical
system with finite energy confined to a finite volume of space has only a finite number of discrete states. So we are OK.
——-
“Now, it is a fact that a physical system with finite energy confined to a finite volume of space has only a finite number of discrete states.”—I wish the obviousness of this final remark were readily apparent to me.

Dr. Seth Lloyd’s work is very compelling, and I am engaged in a project inspired by ideas related to those he expounds here—mining the computational universe to uncover Lloyd’s programmer monkeys. But I find that his theory of the universe– which by the way I agree with, though it may sometimes seem otherwise– assumes no less than any other conception of the universe, which leaves space for continued thinking on evocative hypotheses, including Church’s, even as we attempt to hack the universe.

Lloyd’s thesis adds to the conception of the Universe as a Turing computer an important and remarkable claim (albeit one that depends on the conception of the quantum computer), viz.  that the Universe is not only Turing computable, but because it is constituted by quantum particles which behave according to quantum mechanics, it is a quantum computer computing its future state from its current one. The better we understand and master such theories, the better prepared we would be to hack the universe in order to perform the kind of computations -quantum computations- we would like to perform.

I would agree with Rudy Rucker too as to why Seth Lloyd assigns such an important role to quantum mechanics in this story. Rudy Rucker basically says that being a subscriber to quantum mechanics, Lloyd doesn’t give enough consideration to the possibility of deterministic computations. Lloyd writes, “Without the laws of quantum mechanics, the universe would still be featureless and bare.” However, though I am one among many (including Stephen Wolfram) who agree  that it is unlikely that the universe is a cellular automaton, simply because cellular automata are unable to reproduce quantum behavior from empirical data (but note that Petri and Wolfram himself attempt explanations of quantum processes based on nets), there’s  absolutely no need to rush headlong into quantum mechanics. If you look at computer simulations of physical systems, they don’t use quantum mechanics as a randomizer, and they seem to be able to produce enough variations to feed a computational universe. Non-deterministic randomness is not neccesary; pseudorandomness or unpredictable computation seem to be enough.

Universality on Real Computation

A paper of mine in French on this subject is already in arXiv: “Universality on Real Computation”. Chris Moore called my attention to his paper entitled “Recursion Theory on the Reals and Continuous-time Computation” ,  which arrives at similar results using a different approach. A paper I’m writing in English on this subject, and which I have been discussing with several people, is forthcoming.  A preliminary powerpoint presentation that I used when presenting on the topic to Gregory Chaitin is available here:Universality on Real Computation In computability theory, the theory of real computation deals with hypothetical abstract machines capable of infinite precision. They operate on the set of real numbers, most of which are non-computable by a Turing machine. These hypothetical computing machines can be viewed as idealised analog computers or differential machines. The question I am interested in concerns the consequences of computing on the set of real numbers for current foundational concepts in traditional computation,  for example universality. I have found that an infinite number -possibly denumerable- of  universal real computers of varying power allows what I have called “intrinsic universality” (there is another definition of intrinsic universality related to dynamical systems and universal computation), since real numbers are not bounded in complexity and there is therefore one for each class of complexity. However, taking the complete set of real numbers, what I claim is that a single and ultimate universal machine for real computation is not possible, since for each proposed universal real computer A –with pre-fixed real numbers R=r_1,r_2,…,r_n – it suffices to calculate the maximal Turing degree of the set of the real numbers involved, let’s say O_n, to conceive a new real computer B able to compute numbers of higher Turing degree, let’s say O_m with m>n, which the given universal real machine A won’t be able to emulate– which contradicts the definition of a universal abstract real computer. Therefore A won’t be able to emulate (in the way conceived for defining universality in the traditional Turing model)  any other real machine B which belongs to the same set –the real numbers– (which evidently can be seen as their class of languages) unless it allows non-recursive functions going through all the levels of the arithmetical and hyper-arithmetical hierarchy. In other words, real computation does not allow universality, which is the very foundation of computer science unless we take into consideration non-recursive functions of arbitrary power, which adds an aditional problem to the conception of a universal device and the convergence of real computing models, unlike the traditional model based on recursive functions theory and Turing machines. However, in real computation there is a place for relative universality, which is very rich in ideas and theories and gives rise to a hierarchical Church-Turing type thesis for each level of the arithmetical and hyper-arithmetical hierarchy. So talking about the universal abstract device E_n for example–because of  the arithmetical level E_n– for each n natural number would make sense, unlike a device E able to behave like any other E_n for any n natural number, which would need at least one function or the composite of several functions able to attain any arbitrary degree of computability. In other words, E wouldn’t be a field since it is not closed under the set of operators of the defined E.

Here is a related paper entitled on “The complexity of real recursive functions” by Manuel Lameiras Campagnolo. In France, “M. Olivier Bournez” has a particular interest in real computation, in particular analog and hybrid systems.Other important authors in the field include : Karp, da Costa, Blum, Cucker, Shub and Smale. Felix da Costa has let me know that  he is working on something related to my ideas on universality in real computation and relative universality.It is important to say that being interested in real computation is not the same thing as being an “hyper-computationalist”. In fact, some if not most  of the above authors think that real computation would at best be only as powerful as the digital models.  Their interest in the field is mainly operational, in the sense that these types of  machines perform operations commonly related to fields like real anaylisis.

International Conference in Complex Systems, NECSI

NECSI/ICCS Conference Report, Quincy, Greater Boston, USA, July 2006.

First lesson: For every complex problem there is a simple, neat, wrong solution.

I attended talks given by Ed Fredkin on Finite Nature, Lazlo Barabasi on Complex Networks, Christoph Teuscher on Biology and Computation and John Nash on his research upon Game Theory.
* Ed Fredkin presented a table salt 3-D cellular automata model that fulfils all physical constraints on symmetry and energy conservation. The model is surprisely Turing-universal. As a reminder, the Zuse-Fredkin Thesis is a Church-type thesis which claims additionally that the universe being a Cellular Automaton can be understood in terms of the evolution of  Cellular Automata. An interesting paper entitled “Church-Turing Thesis is Almost Equivalent to Zuse-Fredkin Thesis” by Plamen Petrov is available here>
http://digitalphysics.org/~ppetrov/
And much more information on the interesting ideas of Ed Fredkin is available in
http://www.math.usf.edu/~eclark/ANKOS_zuse_fredkin_thesis.html and on  Ed Fredkin homepage at MIT, which  includes some remarks on why this thesis is not in agreement with  Stephen Wolfram’s, since Wolfram does not intend to imply that the universe is a classical cellular automaton but rather conceives of   a discrete universe based on systems performing simple rules and producing all the complex behavior we find in nature. Such systems are comparable to Turing machines, tag systems, axioms or any other equivalent system.
* In his lecture, Lazlo Barabasi claimed that behind all complex systems there are complex networks, in particular Free-Scale Networks (with a few nodes very well connected with others, and many nodes weakly connected). These nets are efficient and robust (even minus random nodes they remains connected)except under attack (provided the best connected nodes are targeted).
* Christoph Teuscher gave a lecture on computation inspired by biology. However, as he himself admitted, it was not his area of expertise.
* John Nash presented his research on Game Theory using Mathematica as an engine.
* I met Hava Siegelmann and one of her fellows, Yariv, who is working on Artificial Intelligence. Siegelmann worked some years ago (while completing  her PhD dissertation) upon a model of computation called Analog Recurrent Neural Network or just ARNN which, under certain circumstances,  is able to compute more functions than the set of recursive functions , which are those computed by the Turing machines. She is now working on topics related to Molecular Biology. I asked her about the forceful  critiques delivered by traditional logicians like Martin Davis, who wrote a paper entitled “The Myth of HyperComputation.”    The target of most of these critiques is a certain circular argument—to compute more than Turing machines it is necessary to use non-Turing computable weights previously coded into the neural network. It has been known for a long time that the set of all real numbers is able to encode any arbitrary language, even if it is non-Turing computable. What is remarkable from my point of view is her result relating to complexity classes, since weights with lower complexity are able to compute a higher class when  used in those networks. Aditionally she argued that even with a stochastic function her networks are able to solve non-computable functions. Recently I discussed the fact with Stephen Wolfram and we agreed that she is assuming strong randomness. I would say however that Siegelmann’s work is much more beatiful from a complexity point of view than from a “hypercomputational” viewpoint. In her book published under the title “Neural Networks and Analog Computation: Beyond the Turing Limit ” she proves that: a) there exists an universal neural network with only 9 neurons, and b) that  p(r) suffices to compute a non-computable function, where r is an arbitrary complete real number but p(r) represents the first p digits of the expansion of r–which means that linear precision suffices to achieve “super-Turing” capabilities, assuming that the neural network can have access to any possible real number before the computation. In other words this seems to be true only if all possible real numbers are allowed a priori (just as in the Turing machines an unbounded tape is neccesary to carry out all recursive languages, and neural networks with rational numbers as weights do not compute the same set of functions as neural networks with whole numbers as weights, the first having been  proven by Klenee to compute the same set as Turing machines and the second  to compute the same set of languages as finite automata, those called regular languages).
I exchanged ideas with some other interesting people, like an engineer from the Space and Airbone Systems Department of Raytheon. And I met John Nash Jr. during the gala dinner  at which he was presented with an award  for his contributions to  Complexity Theory, mainly honoring his work relating to Game Theory.

Amazon Cloud

ACF loading animated gif