smryan@garth.UUCP (Steven Ryan) (06/01/88)
In article <15422@brl-adm.ARPA> dsill@nswc-oas.arpa (Dave Sill) writes: >>Also, please do not assume the Church-Turing Hypothesis. > >Huh? I think it's quite safe to assume the Church-Turing *Thesis*. >And what does it have to do with optimization, anyway? > The reference was back to somebody saying AI will come up with the ultimate optimiser. AI implicitly assumes CT. For those not in the know, the Church-Turing(-Curry-...) Hypothesis in its restricted form states that all formal systems (programming, type 0 grammars, Turing machines, lambda calculus, operators, ...) are all equally powerful. This is a hypothesis because this characterisations applies to all systems existing and yet to be created. The most unrestricted form of the hypothesis states any "computable function" can be expressed in any of these notations. It is important to note that all the formal systems share common properties: discrete and finite number of transistions, fixed and finite number of states, and a discrete and finite store. Formal systems have a very aleph-null character. It is not safe to assume the unrestricted hypothesis because space-time may be continuous and aleph-one. If so, there may exist some process characterised by an arbritrarily long and complex path, that is continuous transistions, infinite number of states, and an infinite store, which is all very aleph-one. If such a process exists, it cannot be described by any aleph-null formal system. I do not claim such a process exists nor, unlike AI proponents, do I deny its existence. As long as these questions remain unsettled, I feel it is unsafe to declare the hypothesis resolved. If someone wishes to use it as working hypothesis, fine, but just be honest. By the way, if you want to see how complicated aleph-one sets can get, read about fractals. I think, however, that fractals only cover a tiny chunk of all sets. The set of sets which can only be characterised by a negation remains larger than all other sets. Hafa an godne daege. sm ryan "Wow, and like every atom in my thumbnail might a complete universe...." - Pinto