Search NASA⌕ Search

SEARCH · Search NASA

Results for “Turing”

Search indexed NASA NTRS and DOE OSTI research on propulsion, heat transfer, battery materials and energy systems. Follow report and document links to the original sources.

Quote a phrase for an exact phrase match. Source license links do not imply unrestricted reuse.

At least 37 records · Page 2

Cosmic logic: a computational model

We initiate a formal study of logical inferences in context of the measure problem in cosmology or what we call cosmic logic. We describe a simple computational model of cosmic logic suitable for analysis of, for example, discretized cosmological systems. The construction is based on a particular model of computation, developed by Alan Turing, with cosmic observers (CO), cosmic measures (CM) and cosmic symmetries (CS) described by Turing machines. CO machines always start with a blank tape and CM machines take CO's Turing number (also known as description number or Gödel number) as input and output the corresponding probability. Similarly, CS machines take CO's Turing number as input, but output either one if the CO machines are in the same equivalence class or zero otherwise. We argue that CS machines are more fundamental than CM machines and, thus, should be used as building blocks in constructing CM machines. We prove the non-computability of a CS machine which discriminates between two classes of CO machines: mortal that halts in finite time and immortal that runs forever. In context of eternal inflation this result implies that it is impossible to construct CM machines to compute probabilities on the set of all CO machines using cut-off prescriptions. The cut-off measures can still be used if the set is reduced to include only machines which halt after a finite and predetermined number of steps.

79 ASTRONOMY AND ASTROPHYSICS↗

On The Computational Capabilities of Physical Systems: Relationship With Conventional Computer Science - Part 2

In the first of this pair of papers, it was proven that there cannot be a physical computer to which one can properly pose any and all computational tasks concerning the physical universe. It was then further proven that no physical computer C can correctly carry out all computational tasks that can be posed to C. As a particular example, this result means that no physical computer that can, for any physical system external to that computer, take the specification of that external system's state as input and then correctly predict its future state before that future state actually occurs; one cannot build a physical computer that can be assured of correctly "processing information faster than the universe does". These results do not rely on systems that are infinite, and/or non-classical, and/or obey chaotic dynamics. They also hold even if one uses an infinitely fast, infinitely dense computer, with computational powers greater than that of a Turing Machine. This generality is a direct consequence of the fact that a novel definition of computation - "physical computation" - is needed to address the issues considered in these papers, which concern real physical computers. While this novel definition does not fit into the traditional Chomsky hierarchy, the mathematical structure and impossibility results associated with it have parallels in the mathematics of the Chomsky hierarchy. This second paper of the pair presents a preliminary exploration of some of this mathematical structure. Analogues of Chomskian results concerning universal Turing Machines and the Halting theorem are derived, as are results concerning the (im)possibility of certain kinds of error-correcting codes. In addition, an analogue of algorithmic information complexity, "prediction complexity", is elaborated. A task-independent bound is derived on how much the prediction complexity of a computational task can differ for two different reference universal physical computers used to solve that task, a bound similar to the "encoding" bound governing how much the algorithm information complexity of a Turing machine calculation can differ for two reference universal Turing machines. Finally, it is proven that either the Hamiltonian of our universe proscribes a certain type of computation, or prediction complexity is unique (unlike algorithmic information complexity), in that there is one and only version of it that can be applicable throughout our universe.

Wolpert, David H.↗

Spatio-temporal dynamics induced by competing instabilities in two asymmetrically coupled nonlinear evolution equations

Pattern formation often occurs in spatially extended physical, biological, and chemical systems due to an instability of the homogeneous steady state. The type of the instability usually prescribes the resulting spatio-temporal patterns and their characteristic length scales. However, patterns resulting from the simultaneous occurrence of instabilities cannot be expected to be simple superposition of the patterns associated with the considered instabilities. To address this issue, we design two simple models composed by two asymmetrically coupled equations of non-conserved (Swift-Hohenberg equations) or conserved (Cahn-Hilliard equations) order parameters with different characteristic wave lengths. The patterns arising in these systems range from coexisting static patterns of different wavelengths to traveling waves. A linear stability analysis allows to derive a two parameter phase diagram for the studied models, in particular, revealing for the Swift-Hohenberg equations, a co-dimension two bifurcation point of Turing and wave instability and a region of coexistence of stationary and traveling patterns. The nonlinear dynamics of the coupled evolution equations is investigated by performing accurate numerical simulations. These reveal more complex patterns, ranging from traveling waves with embedded Turing patterns domains to spatio-temporal chaos, and a wide hysteretic region, where waves or Turing patterns coexist. For the coupled Cahn-Hilliard equations the presence of a weak coupling is sufficient to arrest the coarsening process and to lead to the emergence of purely periodic patterns. The final states are characterized by domains with a characteristic length, which diverges logarithmically with the coupling amplitude.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Large Primtive Asteroids: Thermal and Dynamical Context

Primitiveasteroids, most of which are located in the outer belt and Jupiter’s Trojan clouds, provide information related to the origin and evolution of the solar system and the conditions in which the solar nebula was formed. These asteroids are widely thought to be the origin of the least-altered car-bonaceous chondrite that allow us to put crucial con-straints on the current dynamical and thermal theories of the formation and evolution of the early solar sys-tem. The nature of surface composition of large and low-albedo asteroids, like (1) Ceres, (10) Hygiea and (52) Europa, is still under intense debate and different interpretations have beenput forth to explain the ab-sorption features in these objects (e.g.,[1, 2, 3,4,5,6]). Laboratory and spectroscopic experiments on me-teorites that represent all nine carbonaceous chondrite types also found no spectral matches for these large asteroids (e.g.,[7]). Previous studies of asteroid Ceres (the largest primitive asteroid in the solar system) have been conducted to constrain and estimate its surface composition (e.g., [2, 5]). Using linear mixing,[2]found hydroxide brucite, serpentines, and carbonates, to be consistent with Ceres’ ground-based spectra.[5]estimated the surface composition of Ceres and found evidence of widespread NH3-phyllosilicates across its surface using best-fit solutions to Dawn’s NIR spectra. The presence of NH3-phyllosilicates implies that mate-rial from the outer solar system was incorporated into large primitive asteroids, either during their formation at great heliocentric distance or by incorporation of material transported into the Main Belt region. Here we presentnew largeand primitive asteroidsthat share the same spectral similaritieswith the largest asteroid in the solar system, Ceres.We also present the context of these new observations in terms oftheirthermal and dynamicalevolution.Large Primitive Asteroids: Dynamical and Thermal Context:Orbital Distribution of LargePrimitiveAsteroids: Constraining the mineralogy and surface composition of large primitive asteroids will place crucial con-straints on existing dynamical and thermal theories of the formation of the early solar system. We identified several additional asteroids in the Europa-like group in addition to asteroids Europa, Euphrosyne, and Patien-tia, that wereidentified in [8]using NASA IRTFtele-scope (e.g.,Figure 1). These new asteroids along with the already-observed Ceres-and Europa-like group members are localized in the 2.8 < a < 3.4 AU region and characterized by larger sizes, showing an interest-ing orbital distribution (Figure 2). Ceres-likeand Eu-ropa-like groups, which include the largest asteroids in the solar system, show an interesting orbital distribu-tion. These groups are located in the 2.6 < a < 3.6 AU region that contains the snow-line. The snow-line’s location may have been driftedinwards due to the disk’s cooling and evolution[9,10]. Recent dynamical models[11,12]suggested that a substantial fraction of primitive asteroids originated between or beyond the giant planets (a > 5 AU), where water ice would have been stable, and then implanted in the outer Main Belt region because of the giant planets’ growth.Figure 1. Two asteroids, 94 Aurora and 423 Diotima, showing spectra similar to asteroids (1)Ceres and (52)Europa.Thermal modeling and evolution of primitive aster-oids:Primitive water-rich asteroids are thought to be originally composed of mixtures of anhydrous materi-als and water ice that waslater melted by heating sources such as the decay of 26Al, reacting with anhy-drous materials to form H2O/OH-rich minerals. Calcu-lations of the evolution of the temperature and struc-ture of icy planetesimals were performedusing a 1D finite differences thermal evolution model[13, 14] for 26Al-heated planetesimals. In particular, thermally activated compaction due to hot pressing of bodies with an initially unconsolidated porous structure is included. An ice-rich initial composition that leads to a material dominated by phyllosilicates upon aqueous alteration (with 25 vol% H2O and a rock fraction that contains 85 vol% phyllosilicates and 15 vol% olivine upon aque-ous alteration, similar to CIand CM chondrites) was assumed. Atypical initial porosity of 40%[15] is re-duced following the change of the strain rate that is calculated as Voigt approximation from the strain rates of components[16]. Material properties (thermal con-ductivity, density, heat capacity, etc.) correspond to the composition assumed and are adjusted with tempera-ture and porosity. Melting of the water ice as well as water-rock separation are included[14]. Both short-and long-lived radionuclides are consideredas heat sources. Figure 3 shows the maximum temperature calculated as a function of radius and accretion time. A variety of internal structures is obtained, ranging from primordial (no melting of water ice) over partially melted or partially differentiated (melting of water ice, hydration, formation of a rocky core and water ocean below an undifferentiated layer) to completely differ-entiated ones (rocky core, water mantle, Enceladus-like case). The heating and differentiation of planetesi-mals is determined by the availability of 26Al, i.e., by the accretion time t0 relative to the formation of the calcium-aluminum-rich inclusions (CAIs), such that maximum temperatures and structures vary stronglyfor t0< 6 Myr rel. to CAIs. However, for a later accre-tion only the size of the body determines its maximum tempera-ture and structure due to the nearly constant heating by long-lived radionuclides. Average densities of Ceres-and Europa-like group membersimply high-ly porous interiors and, consequently, relatively late accretion at t0> 3 Myr rel. to CAIs with a maximum temperature of < 600 K (Figure3)

D Takir↗

China’s Booming Plug-in Electric Vehicle Market—How Will It Continue?

The plug-in electric vehicle (PEV) is recognized as a pivotal component in transportation energy security and technology innovation in China. With government incentives and substantial capital investments, the Chinese PEV market has become one of the largest in the world. However, is this market boom ephemeral or will it be continuing? This chapter provides a general review of the Chinese PEV market mainly from the consumer per-spective, by summarizing the characteristics of the vehicle policies and consumer concerns in the PEV market in recent years. Moreover, it intro-duces detailed examples on how the policies, technologies, and infrastruc-ture shape the market. In addition to employing large amounts of reliable data from the China Automotive Technology and Research Center for the review, the authors also adopted a quantitative analysis tool—the New Energy and Oil Consumption Credits model—to project the potential in-dustrial impacts of the government policies in multiple scenarios. Based on the findings, it seems that the prosperity of the PEV market, incentivized by the government, will continue in the short run. The direct subsidies to PEV from the government will gradually phase out, and the supply-side push policies such as the dual-credit policy and other charging infrastruc-ture incentives will work as the invisible hand to force the automakers to invest more in the PEV segment. However, in the long run, innovation in PEV technology and business models, together with consumer acceptance will be the major factors that can sustain further market growth.

Ou, Shawn↗

Pattern formation in a coupled membrane-bulk reaction-diffusion model for intracellular polarization and oscillations

Reaction-diffusion systems have been widely used to study spatio-temporal phenomena in cell biology, such as cell polarization. Coupled bulk-surface models naturally include compartmentalization of cytosolic and membrane-bound polarity molecules. Here we study the distribution of the polarity protein Cdc42 in a mass-conserved membrane-bulk model, and explore the effects of diffusion and spatial dimensionality on spatio-temporal pattern formation. We first analyze a one-dimensional (1-D) model for Cdc42 oscillations in fission yeast, consisting of two diffusion equations in the bulk domain coupled to nonlinear ODEs for binding kinetics at each end of the cell. In 1-D, our analysis reveals the existence of symmetric and asymmetric steady states, as well as anti-phase relaxation oscillations typical of slow-fast systems. We then extend our analysis to a two-dimensional (2-D) model with circular bulk geometry, for which species can either diffuse inside the cell or become bound to the membrane and undergo a nonlinear reaction-diffusion process. We also consider a nonlocal system of PDEs approximating the dynamics of the 2-D membrane-bulk model in the limit of fast bulk diffusion. In all three model variants we find that mass conservation selects perturbations of spatial modes that simply redistribute mass. In 1-D, only anti-phase oscillations between the two ends of the cell can occur, and in-phase oscillations are excluded. In higher dimensions, no radially symmetric oscillations are observed. Instead, the only instabilities are symmetry-breaking, either corresponding to stationary Turing instabilities, leading to the formation of stationary patterns, or to oscillatory Turing instabilities, leading to traveling and standing waves. Codimension-two Bogdanov—Takens bifurcations occur when the two distinct instabilities coincide, causing traveling waves to slow down and to eventually become stationary patterns. Our work clarifies the effect of geometry and dimensionality on behaviors observed in ma.ss-conserved cell polarity models.

97 MATHEMATICS AND COMPUTING↗

Intermolecular Structural Change for Thermoswitchable Polymeric Photosensitizer

A switchable photosensitizer (PS), which can be activated at a spe-cific condition beside light, has tremendous advantages for photo-dynamic therapy (PDT). Herein, we developed a thermo-switchable polymeric photosensitizer (T-PPS) by conjugating PS (Pheophor-bide-a, PPb-a) to a temperature-responsive polymer backbone of biocompatible hydroxypropyl cellulose (HPC). Self-quenched PS molecules linked in close proximity by pi-pi stacking in T-PPS were easily transited to an active monomeric state by the tempera-ture induced phase transition of polymer backbones. The tempera-ture responsive inter-molecular interaction changes of PS molecules in T-PPS were demonstrated in synchrotron small-angle X-ray scattering (SAXS) and UV-Vis spectrophotometer analysis. The T-PPS allowed switchable activation and synergistically enhanced cancer cell killing effect at the hyperthermia temperature (45 °C). Our developed T-PPS has the considerable potential not only as a new class of photomedicine in clinics but also as a biosensor based on temperature responsiveness.

Park, Wooram↗

Routes to spatiotemporal chaos in Kerr optical frequency combs

We investigate the various routes to spatiotemporal chaos in Kerr optical frequency combs, obtained through pumping an ultra-high Q-factor whispering-gallery mode resonator with a continuous-wave laser. The Lugiato–Lefever model is used to build bifurcation diagrams with regards to the parameters that are externally controllable, namely, the frequency and the power of the pumping laser. We show that the spatiotemporal chaos emerging from Turing patterns and solitons display distinctive dynamical features. Experimental spectra of chaotic Kerr combs are also presented for both cases, in excellent agreement with theoretical spectra.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Construction of a universal quantum computer

We construct a universal quantum computer following Deutsch's original proposal of a universal quantum Turing machine (UQTM). Like Deutsch's UQTM, our machine can emulate any classical Turing machine and can execute any algorithm that can be implemented in the quantum gate array framework but under the control of a quantum program, and hence is universal. We present the architecture of the machine, which consists of a memory tape and a processor and describe the observables that comprise the registers of the processor and the instruction set, which includes a set of operations that can approximate any unitary operation to any desired accuracy and hence is quantum computationally universal. We present the unitary evolution operators that act on the machine to achieve universal computation and discuss each of them in detail and specify and discuss explicit program halting and concatenation schemes. We define and describe a set of primitive programs in order to demonstrate the universal nature of the machine. These primitive programs facilitate the implementation of more complex algorithms and we demonstrate their use by presenting a program that computes the NAND function, thereby also showing that the machine can compute any classically computable function.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Nonlinear analysis of a reaction-diffusion system: Amplitude equations

A reaction-diffusion system with a nonlinear diffusion term is considered. Based on nonlinear analysis, the amplitude equations are obtained in the cases of the Hopf and Turing instabilities in the system. Turing pattern-forming regions in the parameter space are determined for supercritical and subcritical instabilities in a two-component reaction-diffusion system.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

OpenSHMEM Implementation of IOR Benchmark

The benchmarking effort within the Computational Research & Development Programs at the Oak Ridge National Laboratory (ORNL) seeks to design and enable High Performance Computing (HPC) benchmarks and test suites. The work described in this report is a part of the effort focusing on the comparison and analysis of OpenSHMEM implementations using the Interleave Or Random (IOR) software for benchmarking parallel file system using POSIX, MPIIO, or HDF5 interfaces. We describe the effort to emulate the MPIIO parallel collective capabilities in the IOR benchmark using OpenSHMEM communication. One development effort was in emulating the MPI derived datatype used in the read/write operations and in setting the file view. Another effort was in implementing an internal cache in OpenSHMEM distributed shared memory to facilitate global collective I/O operations. Experiments comparing collective I/O in MPIIO implementations with the OpenSHMEM implementations were performed on the SGI Turing Cluster and the Cray XK7 Titan supercomputer at the Oak Ridge Leadership Computing Facility (OLCF). The preliminary results suggest that on the Cray XK7 Titan, the MPIIO implementations obtained higher write performance and the OpenSHMEM version obtained slightly higher read performance. On the SGI Turing Cluster, the MPIIO implementations obtained slightly higher performance over the OpenSHMEM implementations on large files.

97 MATHEMATICS AND COMPUTING↗

Incentive-Based Voltage Regulation in Distribution Networks

This paper considers distribution networks fea- turing distributed energy resources, and designs incentive-based mechanisms that allow the network operator and end-customers to pursue given operational and economic objectives, while concurrently ensuring that voltages are within prescribed limits. Two different network-customer coordination mechanisms that require different amounts of information shared between the network operator and end-customers are developed to identify a solution of a well-defined social-welfare maximization prob- lem. Notably, the signals broadcast by the network operator assume the connotation of prices/incentives that induce the end- customers to adjust the generated/consumed powers in order to avoid the violation of the voltage constraints. Stability of the proposed schemes is analytically established and numerically corroborated.

24 POWER TRANSMISSION AND DISTRIBUTION↗

Reversal-bounded multipushdown machines

Several representations of the recursively enumerable (r.e.) sets are presented. The first states that every r.e. set is the homomorphic image of the intersection of two linear context-free languages. The second states that every r.e. set is accepted by an on-line Turing acceptor with two pushdown stores such that in every computation, each pushdown store can make at most one reversal (that is, one change from 'pushing' to 'popping'). It is shown that this automata theoretic representation cannot be strengthened by restricting the acceptors to be deterministic multitape, nondeterministic one-tape, or nondeterministic multicounter acceptors. This provides evidence that reversal bounds are not a natural measure of computational complexity for multitape Turing acceptors.

Baker, B. S.↗

Consequences of nonclassical measurement for the algorithmic description of continuous dynamical systems

Continuous dynamical systems intuitively seem capable of more complex behavior than discrete systems. If analyzed in the framework of the traditional theory of computation, a continuous dynamical system with countably many quasistable states has at least the computational power of a universal Turing machine. Such an analysis assumes, however, the classical notion of measurement. If measurement is viewed nonclassically, a continuous dynamical system cannot, even in principle, exhibit behavior that cannot be simulated by a universal Turing machine.

Fields, Chris↗

Is thinking computable?

Strong artificial intelligence claims that conscious thought can arise in computers containing the right algorithms even though none of the programs or components of those computers understand which is going on. As proof, it asserts that brains are finite webs of neurons, each with a definite function governed by the laws of physics; this web has a set of equations that can be solved (or simulated) by a sufficiently powerful computer. Strong AI claims the Turing test as a criterion of success. A recent debate in Scientific American concludes that the Turing test is not sufficient, but leaves intact the underlying premise that thought is a computable process. The recent book by Roger Penrose, however, offers a sharp challenge, arguing that the laws of quantum physics may govern mental processes and that these laws may not be computable. In every area of mathematics and physics, Penrose finds evidence of nonalgorithmic human activity and concludes that mental processes are inherently more powerful than computational processes.

Denning, Peter J.↗

Consequences of nonclassical measurement for the algorithmic description of continuous dynamical systems

Continuous dynamical systems intuitively seem capable of more complex behavior than discrete systems. If analyzed in the framework of the traditional theory of computation, a continuous dynamical system with countablely many quasistable states has at least the computational power of a universal Turing machine. Such an analyses assumes, however, the classical notion of measurement. If measurement is viewed nonclassically, a continuous dynamical system cannot, even in principle, exhibit behavior that cannot be simulated by a universal Turing machine.

Fields, Chris↗

Undecidability in macroeconomics

In this paper we study the difficulty of solving problems in economics. For this purpose, we adopt the notion of undecidability from recursion theory. We show that certain problems in economics are undecidable, i.e., cannot be solved by a Turing Machine, a device that is at least as powerful as any computational device that can be constructed. In particular, we prove that even in finite closed economies subject to a variable initial condition, in which a social planner knows the behavior of every agent in the economy, certain important social planning problems are undecidable. Thus, it may be impossible to make effective policy decisions. Philosophically, this result formally brings into question the Rational Expectations Hypothesis which assumes that each agent is able to determine what it should do if it wishes to maximize its utility. We show that even when an optimal rational forecast exists for each agency (based on the information currently available to it), agents may lack the ability to make these forecasts. For example, Lucas describes economic models as 'mechanical, artificial world(s), populated by ... interacting robots'. Since any mechanical robot can be at most as computationally powerful as a Turing Machine, such economies are vulnerable to the phenomenon of undecidability.

Chandra, Siddharth↗

AI's Philosophical Underpinnings: A Thinking Person's Walk through the Twists and Turns of Artificial Intelligence's Meandering Path

Few human endeavors can be viewed both as extremely successful and unsuccessful at the same time. This is typically the case when goals have not been well defined or have been shifting in time. This has certainly been true of Artificial Intelligence (AI). The nature of intelligence has been the object of much thought and speculation throughout the history of philosophy. It is in the nature of philosophy that real headway is sometimes made only when appropriate tools become available. Similarly the computer, coupled with the ability to program (at least in principle) any function, appeared to be the tool that could tackle the notion of intelligence. To suit the tool, the problem of the nature of intelligence was soon sidestepped in favor of this notion: If a probing conversation with a computer could not be distinguished from a conversation with a human, then AI had been achieved. This notion became known as the Turing test, after the mathematician Alan Turing who proposed it in 1950. Conceptually rich and interesting, these early efforts gave rise to a large portion of the field's framework. Key to AI, rather than the 'number crunching' typical of computers until then, was viewed as the ability to manipulate symbols and make logical inferences. To facilitate these tasks, AI languages such as LISP and Prolog were invented and used widely in the field. One idea that emerged and enabled some success with real world problems was the notion that 'most intelligence' really resided in knowledge. A phrase attributed to Feigenbaum, one of the pioneers, was 'knowledge is the power.' With this premise, the problem is shifted from 'how do we solve problems' to 'how do we represent knowledge.' A good knowledge representation scheme could allow one to draw conclusions from given premises. Such schemes took forms such as rules,frames and scripts. It allowed the building of what became known as expert systems or knowledge based systems (KBS).

Colombano, Silvano↗