[HN Gopher] Rosser's Theorem via Turing Machines (2011)
___________________________________________________________________
Rosser's Theorem via Turing Machines (2011)
Author : dargscisyhp
Score : 62 points
Date : 2024-06-20 03:24 UTC (19 hours ago)
(HTM) web link (scottaaronson.blog)
(TXT) w3m dump (scottaaronson.blog)
| waldrews wrote:
| This seems like a good place to ask - if your knowledge of
| (computation/complexity) theory is at the level of the Sipser
| Introduction to the Theory of Computation book, what's a good
| learning path to get current?
| eru wrote:
| Disclaimer: I have no clue of a complete learning path. But
| here are some suggestions you might find interesting.
|
| If you want to go heavy on complexity, you could try
| 'Combinatorial Optimization: Polyhedra and Efficiency' by
| Alexander Schrijver. But it's basically the equivalent of
| Knuth's Art of Computer Programming for complexity (in terms of
| rigour and breadth of approach).
|
| I have the three volumes of Schrijver's book on my desk, and
| even occasionally look into them. But I admit I never read the
| whole thing. I love the historical context he gives, eg
| explaining how maximum flow / minimum cut problems were first
| formally investigated in the Cold War when Western boffins
| wanted to work out how to most efficiently cut the Soviet rail
| network's ability to move stuff to Western Europe.
|
| If you want something much lighter, you could check out some of
| Scott Aaronson's backlog. Eg
| https://www.scottaaronson.com/papers/philos.pdf 'Why
| Philosophers Should Care About Computational Complexity'. You
| can follow his bibliography for more background. Scott's blog
| backlog is also good.
|
| If you like randomised algorithms, you might also like 'The
| Discrepancy Method Randomness and Complexity' by Bernard
| Chazelle. It's available for free online. Eg at
| https://api.pageplace.de/preview/DT0400.9781316047804_A25932...
|
| Apropos Bernard Chazelle, I'm working on a little paper myself.
| It's about how to simulate the outcome of a series of heap
| operations (like insert and delete-minimum) in O(n) time,
| instead of the trivial to achieve O(n log n) you get from a
| naive implementation. I'm looking for some collaborators, if
| you are interested.
| ccppurcell wrote:
| The next step book wise is Arora and Barak, Computational
| Complexity: a modern approach. Of course that book is already
| out of date. The breakthrough that comes to mind is Ryan
| Williams' circuit lower bounds. He wrote a nice explanation of
| the proof here: https://arxiv.org/abs/1111.1261 He defines all
| the key terms pretty well but probably requires a bit of
| "maturity" to understand. There are also various breakthroughs
| to do with interactive proofs.
| calf wrote:
| Not OP but while I aced my class that used Sipser's book,
| nevertheless I still lacked the mathematical comfort/maturity
| to do Arora and Barak. The first class started talking about
| "random functions" and I had no background for that at the
| time. I don't know if some kind of advanced discrete math
| class would have helped fill in the gaps at the time, at
| least for myself. Or maybe a remedial discrete math class, I
| was mainly an engineer not originally intending to be a CS
| major.
| ggm wrote:
| There is more than one "Rosser's theorem" to wit:
| In number theory, Rosser's theorem states that the
| {\displaystyle n}th prime number is greater than log
| {\displaystyle n\log n}, where log{\displaystyle \log } is the
| natural logarithm function. It was published by J. Barkley Rosser
| in 1939.
|
| (wikipedia)
|
| Wiki refers to what Scott Aaronson is calling Rosser's theorem as
| "Rosser's trick" Rosser's trick uses a formula
| that says "If this sentence is provable, there is a shorter proof
| of its negation".
|
| Not that wiki is the cite beyond all reproach, having more than
| one theorem named after you is also a good thing.
| anandkulkarni wrote:
| When I TA'd computability & complexity as a graduate student, I
| always loved giving this proof of Godel's Theorem as an easy
| corollary of the Halting Problem as a homework assignment.
|
| It's beautiful, elegant, and easy to understand. I was introduced
| to the proof by a note in Sipser's text.
| Joker_vD wrote:
| > a basically-similar argument in Kleene's 1967 textbook.
|
| This textbook is an astonishing piece of work of an astonishing
| mathematical genius. The amount of all kinds of weird (and
| useful? I'm not much of a logician myself) logical stuff in it is
| just mind-boggling, just as its writing style. You can keep come
| back to this book for years and find something new in it every
| time.
|
| Barendregt's book on lambda calculus is another example of such a
| book.
| babarjaana wrote:
| My professor in college also referred us to read Kleene's book
| whenever we could, but the darn thing was (and still is) so
| hard to find.
___________________________________________________________________
(page generated 2024-06-20 23:02 UTC)