18 ms·
"What we are missing is the ability to re-enter old states." That's deadly. Any machine with a finite number of states that cannot re-enter a state it has pre
by lisper 13y ago
"What we are missing is the ability to re-enter old states."
That's deadly. Any machine with a finite number of states that cannot re-enter a state it has previously been in must necessarily halt on all input. That makes it strictly less powerful than even an FSM.
- caf 13y agoIt is worth noting that must necessarily halt on all input is quite a desirable property in a macro language evaluated at compile time.
- gus_massa 13y agoOn the other hand, in Lisp/Scheme/... language family you have a Turing complete language for macro language, Lisp/Scheme/... respectively. In those languages, macros are powerful and must be used with care. The advantage is that complex macros are easy to write.
- lisper 13y agoThat is arguable. All else being equal it might be true, but all else is not equal. The benefit of never having your compiler enter an infinite loop may not be worth the cost in terms of lost expressive power.
- mtdewcmu 13y agoHas it been proven that the ability to write undecidable programs confers expressive power such that you can't have one without the other? It seems self-evident that running forever can't be useful, so you should be able to say WLOG that useful programs always halt. So the set of all useful programs is strictly smaller than the set of Turing machines. Is there a formal reason why Turing machines are desirable?
- lisper 13y ago> Has it been proven that the ability to write undecidable programs confers expressive power such that you can't have one without the other? Yes. > It seems self-evident that running forever can't be useful Really? Do you not think that it might be useful for, say, an operating system to run forever?
- mtdewcmu 13y ago>> Has it been proven that the ability to write undecidable programs confers expressive power such that you can't have one without the other? Yes. Can you provide a reference? >> It seems self-evident that running forever can't be useful Really? Do you not think that it might be useful for, say, an operating system to run forever? It's nice when the OS has the option of shutting down deterministically.
- caf 13y agoDo you think it is useful to implement an operating system entirely at compile-time, in an implementation which uses separate compile and run phases?
- mtdewcmu 13y agoI'm not sure I follow what you're talking about. Operating Systems are tangential to the point, though. When I said all useful programs halt, the kinds of programs I meant are the kind used to prove things about computation. Those programs are simplified abstractions of real programs, and they generally compute one result and then halt (if they halt). Being simple makes those programs easier to use in proofs than real programs. However, the proofs still generalize to real programs; a real-world program with multiple functions is equivalent to several single-function programs glued together together. So my point in saying that all useful programs halt was really to argue that all useful programs must have the constraint that they their behavior is always predictable, or controllable, in some sense. In a trivial way, computers are always predictable, but Turing proved that there are cases where it's impossible to predict the eventual outcome of a program in advance, i.e., the halting problem. In precise terms, the outcome (halt/not halt) of some programs is said to be undecidable or uncomputable. Undecidability is a hallmark of Turing machines. But since real programs are written by humans, who can't solve undecidable problems, real programs will never be able to gain any advantage from undecidable behavior.
- caf 13y agoIt's still a desirable property, it's just that it's a property in essential tension with another desirable property.
- ithinkso 13y agoIt is not that simple. I have a little problem with finding comprehensive definition of Turing completeness - in order to decide if certain machine is turing complete does one have to prove that it can also simulate infinite, not halting algorithms? If yes, then not being able to re-enter old states disqualifies C preprocessor as a turing complete machine by considering simple machine that goes left and right till the end of time. However, is it really an algorithm? If there is no output one could simply replace that with just empty machine that halts for sure, therefore it can be simulated in C preprocessor. On the other hand, if this is not requirement then we know that every algorithm we have to simulate to prove turing completeness halts eventually, there is no ability to re-enter old states but if algorithm halts we could just add enough more states (finitely many) that allows it to finish.
- throwaway82740 13y agoI would look at it a slightly different way. It's not that the definition of Turing completeness explicitly says that a language must be able to simulate "infinite" algorithms. It's that it must be able simulate what a Turing machine can do. Turing machines are quite capable of running non-halting algorithms, so the language must be able to as well. Contrived example: One algorithm a Turing machine could perform would be to write the characters "TM" every two cells on its entire tape. The tape is unbounded, so this algorithm is, colloquially speaking, infinite. Clearly, you cannot simulate this with a halting machine like the C preprocessor.
- ithinkso 13y agoThis is exactly the problem I was talking about. In every definition I've read there was strict condition that set of all possible states Q is non-empty (and finite). But there is difference in definition of set of final states. In [1] there is a comparison - in columns labeled "Peter Linz" and "Wikipedia" F is defined as subset of Q. This implies that it also could be empty, although in column labeled "Michael Sipser" there is a special state q_accept that explicitly exist in Q, therefore F is not-empty. Unfortunately there is no information if q_accept has to be reachable from start state. But consider this: How one could say that this machine is actually writing "TM" every two cells? If you investigate tape states while machine is still running it might change (on meta-level you my expect that this is actually true but you might for example make some bug that you're not aware of). The only way to be able to see that "TM" has been written is after the machine halts. [1] http://www.cis.upenn.edu/~matuszek/cit596-2012/NewPages/turing-machine-definitions.html http://www.cis.upenn.edu/~matuszek/cit596-2012/NewPages/turi...