Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Computability theory essay - advice before I begin

  1. May 7, 2012 #1

    I have to write an ~10 pages essay on Computabilty theory as part of my PhD logic course. Given that that is a very broad topic and that I found very little information on the internet, I would like to ask if anybody has had any experience with that?

    My primary issue would be which subtopics should I focus on, i.e. the structure of my essay. What would you suggest a ~10 pages essay about Computability Theory should contain?

    But any other help, including good sites, e-books, journal articles, ... is very welcome.

    Thanks a lot
  2. jcsd
  3. May 7, 2012 #2
    Is it supposed to be more mathematical, or more philosophical? Perhaps after developing the background of what computable numbers are; you can spend some time delving into the non-computable ones. These are the vast, uncountable set of real numbers that cannot be characterized in any way using finite strings of symbols.

    So these are numbers that can never be programmed into computers, appear to be totally random and meaningless strings of bits ... and yet, without them, the continuum would be full of holes.

    So this is the boundary between the discrete and the continuous. The computable and the ineffable.

    A lot of people who come to set theory from computer science really dislike uncountable sets and noncomputable numbers.

    So five pages general background; and five pages on the nature of uncomputable numbers; the ways in which some computer scientists don't like them very much; the way they're essential to the notion of the mathematical continuum; and the philosophical problem of the existence of important entities -- the noncomputable numbers -- that cannot possibly be programmed into our algorithmic machines? Perhaps there's something important about the noncomputable numbers.

    I think this would be a pretty cool paper.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook