User talk:Christopher J. Reiss: Difference between revisions
imported>Christopher J. Reiss (→Sandbox for sketch of Halting proof: new section) |
imported>Christopher J. Reiss |
||
| Line 27: | Line 27: | ||
== Sandbox for sketch of Halting proof == | == Sandbox for sketch of Halting proof == | ||
This is by no means faithful to the historical development of the Church-Turning theorem, rather. Rather, this is provided as a sketch to elucidate the truth of the theorem from a modern perspective. | |||
Suppose we have a programming language 'like' (isomorphic to) Lisp. While programming languages differ in terms of style, all 'sufficiently powerful' languages are identical in terms of which computations can be performed. (The weaker languages are not of interest for the purposes of this discussion.) | Suppose we have a programming language 'like' (isomorphic to) Lisp. While programming languages differ in terms of style, all 'sufficiently powerful' languages are identical in terms of which computations can be performed. (The weaker languages are not of interest for the purposes of this discussion.) | ||
::a) 'Quine' Lemma : Any program can assign its own source code to a variable name. | |||
We omit the proof here; this is a common puzzle posed to computer science students. In other words, "Write a program which prints out its own source code." To thwart 'cheating' by, say, reading the disk for the source code we add a condition : "where the only memory locations referenced by an instruction was populated by a previous instruction." That is, no scanning the disk or RAM for the incidental presence of the source code, the program must assemble its code 'by hand'. | We omit the proof here; this is a common puzzle posed to computer science students. In other words, "Write a program which prints out its own source code." To thwart 'cheating' by, say, reading the disk for the source code we add a condition : "where the only memory locations referenced by an instruction was populated by a previous instruction." That is, no scanning the disk or RAM for the incidental presence of the source code, the program must assemble its code 'by hand'. | ||
This lays the groundwork for a self-referential paradox under the assumption that the Halting Problem is solvable. | |||
::Suppose a halting detector, H(P), exists. H reads any program P, and returns True only if P halts. | |||
::We construct a program, Spite, which defies H by design. | |||
::Define Spite thus : | |||
:::If H(Spite) is True, hang in an infinite loop. | |||
:::If H(Spite) is False, terminate. | |||
Spite uses the Quine trick to make a liar of H. Hence H cannot exist. | |||
Revision as of 00:38, 14 July 2008
Welcome!
| Citizendium Getting Started | |||
|---|---|---|---|
| Quick Start | About us | Help system | Start a new article | For Wikipedians | |||
Welcome to the Citizendium! We hope you will contribute boldly and well. You'll probably want to know how to get started as an author. Just look at CZ:Getting Started for other helpful "startup" links, and CZ:Home for the top menu of community pages. Be sure to stay abreast of events via the Citizendium-L (broadcast) mailing list (do join!) and the blog. Please also join the workgroup mailing list(s) that concern your particular interests. You can test out editing in the sandbox if you'd like. If you need help to get going, the forums is one option. That's also where we discuss policy and proposals. You can ask any constable for help, too. Me, for instance! Just put a note on their "talk" page. Again, welcome and have fun! Stephen Ewen 03:11, 10 February 2008 (CST)
DNA
Great to see you're interested in improving the narrative. Thanks. Chris Day (talk) 13:23, 8 March 2008 (CST)
- I saw Gareths recent comments and a DNA/Student Level would be a good collaboration. I think the goals of trying to spark some imagination into the writing is important. The DNA article was taken from wikipedia and massaged into its current form. The wikipedia article is excellent. Chris Day (talk) 23:47, 9 March 2008 (CDT)
- I'd be up for collaborating on that, currently at work on some articles in math and comp sci, but shd have some time in a couple of weeks. Just give a shout when it's underway ... Christopher J. Reiss 23:52, 9 March 2008 (CDT)
Pandora
I wouldn't worry. --Robert W King 16:51, 9 March 2008 (CDT)
hi, welcome
Christopher, welcome to CZ, and thank you for helping out around the Computers Workgroup. I enjoyed reading your user page; I cannot do anything such as read or think when music is playing (and when SOME people are talking). Don't know if I'm autistic or what, but it has always been troubling since I so often hear music in public places where I do not want it (such as in train stations during my commute or in the shopping mall). Anyway, welcome to the CZ, a very satisfying project.Pat Palmer 18:55, 20 April 2008 (CDT)
A belated response
Hi, I'm cleaning up my talk: page, and replying to messages I'd put off until later (much later, it turned out :-). Sorry this is so late... too much to do!
I never worked at BBN, although I knew a lot of people who did work there, especially in the early days of the Internet (since they were one of the principal contractors).
I had a look at Halting problem, and it's not too bad, but I felt it could use a bit more explanation, which I added. In particular, I felt that you 'buried the lede', and felt that it should say right up top basically what the HP is. I also added a part which mentions the analogy to the inability to reliably predict the future operation of a cellular automaton (such as Life patterns). And I explained why H needs to halt, since it might not be intuitively obvious to lay readers. (I got a bit distracted when I found that Kurt Godel didn't exist, and wrote that inter alia, so I forget exactly what else I did to HP.) I also added a bunch of links - link away, that's the advantage of a hyper-text encyclopaedia! Anyway, take a look and see what you think. J. Noel Chiappa 09:35, 4 June 2008 (CDT)
- Wow - you made some stunningly clarifying edits. It's much better now. If your time permits, I'd like to collaborate w/ you in the future; at least to have you take a pass at new material I added. More l8r ... Christopher J. Reiss 12:21, 4 June 2008 (CDT)
- Good. Sure! J. Noel Chiappa 14:01, 4 June 2008 (CDT)
Sandbox for sketch of Halting proof
This is by no means faithful to the historical development of the Church-Turning theorem, rather. Rather, this is provided as a sketch to elucidate the truth of the theorem from a modern perspective.
Suppose we have a programming language 'like' (isomorphic to) Lisp. While programming languages differ in terms of style, all 'sufficiently powerful' languages are identical in terms of which computations can be performed. (The weaker languages are not of interest for the purposes of this discussion.)
- a) 'Quine' Lemma : Any program can assign its own source code to a variable name.
We omit the proof here; this is a common puzzle posed to computer science students. In other words, "Write a program which prints out its own source code." To thwart 'cheating' by, say, reading the disk for the source code we add a condition : "where the only memory locations referenced by an instruction was populated by a previous instruction." That is, no scanning the disk or RAM for the incidental presence of the source code, the program must assemble its code 'by hand'.
This lays the groundwork for a self-referential paradox under the assumption that the Halting Problem is solvable.
- Suppose a halting detector, H(P), exists. H reads any program P, and returns True only if P halts.
- We construct a program, Spite, which defies H by design.
- Define Spite thus :
- If H(Spite) is True, hang in an infinite loop.
- If H(Spite) is False, terminate.
- Define Spite thus :
Spite uses the Quine trick to make a liar of H. Hence H cannot exist.