Serendip is an independent site partnering with faculty at multiple colleges and universities around the world. Happy exploring!

Reply to comment

Paul Grobstein's picture

more on the limitations of formal systems

From a conversation with Bill Huber re The conjecture, for which many thanks ....

The possible outputs of a classical one-dimensional cellular automata with an infinite number of cells are countably infinite, regardless of its rules and starting conditions (since they occur sequentially they can be associated one to one with the positive integers).  Among such CA's is a universal Turing machine.  Using the diagonalization argument, it can be shown that the number of possible states of an infinite number of cells are always greater than countably infinite, ie that there were always be possible states of an infinite linear array that are not among the outputs of a classical one-dimensional infinitely long cellular automaton, or among the possible outputs of a univeral Turing machine. 

From this it follows that

  • no single deterministic "formal system" can serve as an adequate basis for "inquiry" understood not as discovering what is but conceiving what might be
  • there now exist in the universe things that cannot be accounted for in terms of any formal system: the infinite number of possible states of an infiinitely long classical CA that are not generated by a universal Turing machine (and an associated infinite number of non-compressible real numbers) 

Reply

The content of this field is kept private and will not be shown publicly.
To prevent automated spam submissions leave this field empty.
2 + 4 =
Solve this simple math problem and enter the result. E.g. for 1+3, enter 4.