(03-22-2018, 11:08 AM)AnyOldName3 Wrote: Lambda calculus is at its heart an incredibly simplified macro expansion system, and that was approximately the first thing to be shown to be Turing-complete (as it was probably the first thing to be shown to be equivalent to a Turing machine). Turing completeness can come from very simple places.
Like I said, if it doesn't have control flow, those kinds of macros can't be Turing Complete (at least I don't see how they could be), but Lamda Calculus does that so it's fine. A good example of what I was trying to illustrate would the C/C++ preprocessor and its macros, which AFAIK are not really Turing Complete.