Wait is, by definition, a mapping function and the author of the wiki article has commented as not being a programming language. Without a specification on the vague requirements of the mapping function definition, it can't claim to be turing-complete "process" (since language doesn't seem to fit) itself. Most programming languages (and I believe all TC ones) have to allow for unbounded program length, and not all mapping functions (namely any that take a finite number of bits of entropy input) can map to the entire number line (and hence provide unbounded output). This fails to meet the Arbitrary effect at an arbitrary point requirement, and even foregoing that problem, the mapping function STILL gives no guarantee of being able to find a suitable time slice to achieve an effect within the programmer's lifetime or the lifetime of the universe.
- Well, it is designed so you have to wait forever before starting compiling! )The mapping function could be any function.) --Zzo38 03:55, 14 Sep 2005 (GMT)
- 1. The mapping function is not meant to require too much computation itself; I think I will revise the spec to say it must be implementable with a finite automaton, which I think implies that the mapping process will take time proportional to the logarithm of time_t at most.
- 2. The mapping function is required to produce every program in the reference language at some time. As you mention, this implies that the mapping function's domain must be infinite.
- 3. Different mapping functions produce different wait dialects; it is a definitional question whether these are different languages with the same grammar ( <program> ::= "" ) or different semantics for the same language.
- 4. It is also a definitional question whether this language, or these languages, are Turing-complete. For any wait dialect and any computation a Turing machine can perform, there is a program in that wait dialect (indeed, THE program in that wait dialect) that performs that computation (if run at the right time).
- 5. Yes, the right time might well be after the heat-death of the universe. But then, lots of things are Turing-computable without being computable within the lifetime of the universe; for instance, a brute-force solution to Go.
- 6. By the way...no, not all Turing-complete programming languages need to allow for unbounded program length...the bound on program length just needs to be wide enough to emulate some other Turing-complete language within it.
- DanielCristofani 06:24, 4 Mar 2006 (GMT)
An interesting problem is given a suitably simplistic PRNG (maybe a rule 30 CA?) seeded with the date/time and using a suitable process to determine the program from the output of the PRNG, would it be possible to determine the specific point of time at which a specific program would need to be (or need to have been) compiled? --Wildhalcyon 02:38, 14 Sep 2005 (GMT)