Undecidability in an Adaptive System

Hutson, Jan E. “Undecidability in an adaptive system.” In 1990 Lectures in Complex Systems , pp. 521-526. CRC Press, 2018.
URL1

In this chapter, the authors describe a general introduction to undecidability, Turing machines, and Turing gases, and then give a formal proof of the undecidability of the membership problem for Turing gases. They explore the Turing gases model, the authors want to investigate is that of objects acting on objects. Models of adaptive behavior are used in many areas such as biology, chemistry, economics, and computer science. The authors shows that the general problem under investigation is undecidable, there are always particular instances that happen to be decidable. An example of a known undecidable problem is that of whether a Turing machine will accept. To run the Turing machine, the tape starts with a string of non-blank symbols in the middle, surrounded by blanks on the rest of the tape. Of course, symbols used for states must be different from the tape symbols.

Cited by 1
Related articles