Concepts and Recipes

If concepts are explicated as abstract procedures, then we can easily show that each empirical concept is a not an effective procedure. Some, but not all empirical concepts are shown to be of a special kind: they cannot in principle guarantee that the object they identify satisfies the intended conditions.

Multiscale analysis for diffusion-driven neutrally stable states

The Turing instabilities for reaction–diffusion systems are studied from the Fourier normal modes which appear by searching the solution obtained from linearization of the reaction–diffusion system at the spatially homogeneous steady state. The linear stability analysis is only appropriate when the temporal eigenvalues associated to every given spatial eigenvalue have non-zero real part. If the real part of the temporal eigenvalue in a normal mode is equal to zero there is no enough information coming from the linearized system. Given an arbitrary spatial eigenvalue, by equating to zero the real part of the corresponding temporal eigenvalue will lead to a neutral stability manifold in the parameter space. If for a given spatial eigenvalue the other parameters in the reaction–diffusion process drive the system to the neutral manifold, then neither stability nor instability can be warranted by the usual linear analysis. In order to give a sketch of the nonlinear analysis we use a multiple scales method. As an application, we analyze the behavior of solutions to the Schnakenberg trimolecular reaction kinetics in the presence of diffusion.     

Formulation of linear problems and solution by a universal machine

Using the predicate language for ordered fields a class of problems referred to aslinear problems is defined. This class contains, for example, all systems of linear equations and inequalities, all linear programming problems, all integer programming problems with bounded variables, all linear complementarity problems, the testing of whether sets that are defined by linear inequalities are semilattices, all satisfiability problems in sentenial logic, the rank-computation of matrices, the computation of row-reduced echelon forms of matrices, and all quadratic programming problems with bounded variables. A single, one, algorithm, to which we refer as theUniversal Linear Machine, is described. It solves any instance of any linear problem. The Universal Linear Machine runs in two phases. Given a linear problem, in the first phase a Compiler running on a Turing Machine generates alinear algorithm for the problem. Then, given an instance of the linear problem, in the second phase the linear algorithm solves the particular instance of the linear problem. The linear algorithm is finite, deterministic, loopless and executes only the five ordered field operations — additions, multiplications, subtractions, divisions and comparisons. Conversely, we show that for each linear algorithm there is a linear problem which the linear algorithm solves uniquely. Finally, it is shown that with a linear algorithm for a linear problem, one can solve certain parametric instances of the linear problem.Research was supported in part by the National Science Foundation Grant DMS 92-07409, by the Department of Energy Grant DE-FG03-87-ER-25028, by the United States—Israel Binational Science Foundation Grant 90-00434 and by ONR Grant N00014-92-J1142.Corresponding author.     

Some New Lattice Constructions in High R. E. Degrees

A well-known theorem by Martin asserts that the degrees of maximal sets are precisely the high recursively enumerable (r. e.) degrees, and the same is true with ‘maximal’ replaced by ‘dense simple’, ‘r-maximal’, ‘strongly hypersimple’ or ‘finitely strongly hypersimple’. Many other constructions can also be carried out in any given high r. e. degree, for instance r-maximal or hyperhypersimple sets without maximal supersets (Lerman, Lachlan). In this paper questions of this type are considered systematically. Ultimately it is shown that every conjunction of simplicity- and non-extensibility properties can be accomplished, unless it is ruled out by well-known, elementary results. Moreover, each construction can be carried out in any given high r. e. degree, as might be expected. For instance, every high r. e. degree contains a dense simple, strongly hypersimple set A which is contained neither in a hyperhypersimple nor in an r-maximal set. The paper also contains some auxiliary results, for instance: every r. e. set B can be transformed into an r. e. set A such that (i) A has no dense simple superset, (ii) the transformation preserves simplicity- or non-extensibility properties as far as this is consistent with (i), and (iii) A ?_T B if B is high, and A ≥_T B otherwise. Several proofs involve refinements of known constructions; relationships to earlier results are discussed in detail.     

A New Reducibility between Turing- and wtt-Reducibility

A new reducibility between Turing and weak truth-table reducibility is defined, which gives an affirmative answer to the open question about the existence of such an intermediate reducibility proposed formally by M. Stob. Mathematics Subject Classification: 03D25.     

关于递归控制Turing可化归性

证明了“递归控制Ｔｕｒｉｎｇ可化归性”（简称ｒｃｔ－可化归性）崩溃成平凡情形，即证明了任何两个有穷集合或任何两个无穷的递归可枚举集合都分别是ｒｃｔ－等价的，而它们两者之间则又不是ｒｃｔ－等价的．也即有且只有两个递归可枚举的ｒｃｔ－度．从而ｒｃｔ－可化归性不是通常递归论意义下的合适的可化归性．     

广义分子计算模型在整数问题中的应用

分子计算是一种新型的并行计算模式. 作为信息载体和计算载体的DNA,生化反应时存在不可控性. 构建具有通用性的分子计算机存在许多困难和限制. 将分子计算黏贴模型与图灵机相结合,已提出一种不依赖于特定生物技术的广义分子计算模型(generalized turing model,GTM). 对GTM模型进行扩展,通过实验说明了该广义分子计算机能够在多项式时间内求解NP完全的整数规划问题,该模型具有编码简单、错误率低等特点.     

少儿图灵测试和常识处理

This talk presents our research work on children Turing test. It is implemented in a conversation system supported by a commonsense knowledge base. This system can talk to school children in a more or less natural way. The main difference between it and many other conversation programs is its knowledgebased character. In this talk, motivation of children Turing test and the analysis of its results will be described. We will analyze the achievements and failures of children Turing test, its main bottlenecks, its modified versions and its relation to commonsense knowledge processing. In addition, we will propose some conjectures on Turing test under certain hypotheses and give some concluding remarks.     

Towards molecular computers that operate in a biological environment

Even though electronic computers are the only computer species we are accustomed to, the mathematical notion of a programmable computer has nothing to do with electronics. In fact, Alan Turing’s notional computer [L.M. Turing, On computable numbers, with an application to the entcheidungsproblem, Proc. Lond. Math. Soc. 42 (1936) 230-265], which marked in 1936 the birth of modern computer science and still stands at its heart, has greater similarity to natural biomolecular machines such as the ribosome and polymerases than to electronic computers. This similarity led to the investigation of DNA-based computers [C.H. Bennett, The thermodynamics of computation — Review, Int. J. Theoret. Phys. 21 (1982) 905-940; A.M. Adleman, Molecular computation of solutions to combinatorial problems, Science 266 (1994) 1021-1024]. Although parallelism, sequence specific hybridization and storage capacity, inherent to DNA and RNA molecules, can be exploited in molecular computers to solve complex mathematical problems [Q. Ouyang, et al., DNA solution of the maximal clique problem, Science 278 (1997) 446-449; R.J. Lipton, DNA solution of hard computational problems, Science 268 (1995) 542-545; R.S. Braich, et al., Solution of a 20-variable 3-SAT problem on a DNA computer, Science 296 (2002) 499-502; Liu Q., et al., DNA computing on surfaces, Nature 403 (2000) 175-179; D. Faulhammer, et al., Molecular computation: RNA solutions to chess problems, Proc. Natl. Acad. Sci. USA 97 (2000) 1385-1389; C. Mao, et al., Logical computation using algorithmic self-assembly of DNA triple-crossover molecules, Nature 407 (2000) 493-496; A.J. Ruben, et al., The past, present and future of molecular computing, Nat. Rev. Mol. Cell. Biol. 1 (2000) 69-72], we believe that the more significant potential of molecular computers lies in their ability to interact directly with a biochemical environment such as the bloodstream and living cells. From this perspective, even simple molecular computations may have important consequences when performed in a proper context. We envision that molecular computers that operate in a biological environment can be the basis of “smart drugs”, which are potent drugs that activate only if certain environmental conditions hold. These conditions could include abnormalities in the molecular composition of the biological environment that are indicative of a particular disease. Here we review the research direction that set this vision and attempts to realize it.