Special issue of
INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE
on
Frontier between Decidability and Undecidability and Related Problems
Computability is one of the fundamental domains of computer
science. Many questions remain open in this area and their solution
is of great importance both for the advance of knowledge and for
possible applications.
Many problems of real life in their present mathematical or
theoretical modeling are undecidable. Most often, this means a lack of
information. If enough information can be supplied, the problem may
become decidable and then, the question arises of the complexity of
solving algorithms.
How much information has to be supplied? This is an important
question and we are at the beginning of an era where partial answers
can be approached if not completely given. This is the main motivation
of the topic {\bf Frontier between decidability and
undecidability}. At the present moment, the syntactic aspects of the
limitation of information are considered. In this regard, substantial
progress has been obtained recently, for instance, in the number of
states and or symbols needed to construct a universal Turing
machine. Important results about the same question and similar
criteria have also been obtained in other models of discrete
computations such as register machine, cellular automata and other
abstract devices, some of them being connected with biology.
The same question can be attacked from a very different point of
view starting from the old approach of analog computations. Recent
progress was achieved in this trend which is vividly developing. Other
trends also try to obtain super-Turing computations which also
constitute another look at the same question.
Accordingly, the special issue is planned to focus on the
state-of-the art solutions about the frontier between decidability and
undecidability and related problems. Topics of interest include but
are not limited to:
Digital Computations:
Turing machines, register machines, cellular automata,
other automata, tiling of the plane, polyominoes, snakes,
neural networks, molecular computations, word processing
(groups and monoids), molecular computing and other machines
Analog and Hybrid Computations:
BSS machines, infinite cellular automata, real machines,
quantum computing
In both cases:
frontiers between a decidable halting problem and an
undecidable one in the various computational settings,
minimal universal codes:
size of such a code, namely, for Turing machines, register
machines, cellular automata, tilings, neural nets,
Post systems, P systems...
computation complexity of machines with a decidable halting
problem as well as universal machines,
self-reproduction and other tasks,
universality and decidability in the real field
Please, submit an electronic version of your submission as a .ps or
.pdf file to be sent electronically to one of the guest editors by
December 31, 2010:
J\'er\^ome Durand-Lose Maurice Margenstern Klaus Sutner
jerome.durand-lose@univ-orleans.fr margens@univ-metz.fr
sutner@cs.cmu.edu
Universite d'Orleans, LIFO Universite Carnegie Mellon
Paul-Verlaine - Metz, University,
LITA Department of
Computer
Science
Schedule:
Deadline for submission: December, 31, 2010
Notification of acceptance or rejection: May, 1st, 2011
Deadline for receiving corrected version for revised versions:
July 1st, 2011
Final decision for revised papers: October 1st, 2011
Instructions for submissions:
Your submission should be prepared by using the LaTeX style file of
the International Journal of Foundations of Computer Science to be
found at:
http://www.cs.ucsb.edu/~ijfcs/
and should not exceed 20 pages in this format, including figures,
tables and possible appendices. Your submission should not have been
previously published, nor currently submitted elsewhere for
publication. All submitted papers will be refereed in accordance with
the usual criteria of IJFCS.
**********************************************************
*
* Contributions to be spread via DMANET are submitted to
*
* DMANET@zpr.uni-koeln.de
*
* Replies to a message carried on DMANET should NOT be
* addressed to DMANET but to the original sender. The
* original sender, however, is invited to prepare an
* update of the replies received and to communicate it
* via DMANET.
*
* DISCRETE MATHEMATICS AND ALGORITHMS NETWORK (DMANET)
* http://www.zaik.uni-koeln.de/AFS/publications/dmanet/
*
**********************************************************
Posts
