[Tutor] OT self-implementation?

[Brian van den Broek]

Michael P. Reilly said unto the world upon 01/07/2005 22:18:
> On 7/1/05, Brian van den Broek <bvande at po-box.mcgill.ca> wrote:

<snip>

>>A recent thread on comp.lang.python has touched on to what extent C
>>was written in C. I know PyPy aims to implement Python in Python. I
>>believe I've heard that many lisp fans think you don't have a language
>>unless you can write the language's interpreter in the language
>>itself. (Perhaps one or more of these claims is a bit inaccurate, but
>>the substance seems right.)
>>
>>This sounds, to the untutored, rather like magic.

<snip>

>>Naively, one thinks that to write
>>anything in C, you'd have to *have* C to write in, etc.

<snip me (Brian) asking for refs>


> If you are interested in a more abstract explanation on this, you can read 
> up on one reason why lisp programmers are such fans of writting lisp 
> interpreters in lisp: Turing Machines (TM). Abstract computer constructs 
> that, arguably, are equivalent to your desktop computer in terms of 
> programming. They are really for theoretical research, especially good for 
> algorithm creation. But one of the early algorithms was to create a TM with 
> a TM.
> 
> http://en.wikipedia.org/wiki/Turing_machine
> http://plato.stanford.edu/entries/turing-machine/


Thanks to Max, Michael, and Sean for the replies.

Max's stepwise explanation, which I will distort in summary  by 
simplifying to "Write a complier in a lower level language and use 
that to compile your C compiler written in C" was very helpful. Seeing 
it on screen makes me wonder how I didn't work it out for myself, but 
there you go :-)

Max's and Sean's pointing toward compiler design gives me something to 
start looking for. Having a search term is key to good googling!

Once we get down to Turing Machines and away from real-world 
messiness, I'm much more happy. I have often found that there is, for 
me, quite a gap between the abstract mathematical foundations of 
recursion theory, formal logic, etc. that I have a good handle on, and 
the real world use and applications of the theory. A prime motive for 
tackling Python was to try to close that gap.

A fun point about Turing machines:
The Church-Turing Thesis (roughly, the claim that any intuitively 
computable function is computable by a Turing machine has, as far as I 
know, the distinction of being the first mathematically significant 
claim widely accepted yet know to be insusceptible of proof.

(Goedel had earlier shown that any formalism based on a language 
adequate for arithmetic could formulate propositions not decidable by 
the formalism, but it wasn't until much later that any natural 
examples of independent mathematical interest arose. Early on in my 
graduate career, I spent an excited few days thinking I'd found a 
refutation of the Thesis employing something similar to the Godel 
construction. What a let down when I found the fallacy :-( )

The Thesis has, however, much empirical confirmation in that every 
well defined abstract notion of computability put forth has been 
proven to be co-extensive with Turing Machine computability. The entry 
of empirical methods into mathematical argument in this way has made 
many mathematicians and philosophers of math quite uncomfortable.

And, that's more than enough ramble :-)

Thanks again.

Brian vdB