3 ms·

I'd argue that the definition of computability is an instance of complexity theory, which easily predates what we'd call "programming".

• j2kun 12y ago
  Definitely not. Nobody in mathematics considered the efficiency of Turing machines until the late 60's.
  • 14113 12y ago
    Did I say anything about efficiency? Computability itself is a topic within computational complexity, as (in many ways) it's one of the "hardest" rungs of the complexity ladder.
    • j2kun 12y ago
      I'm sorry, but you're wrong. Complexity theory is by definition the subfield of computer science that studies the efficiency of algorithms, or the inability for algorithms to meet certain efficiency requirements. This is my field of research, and I assure you computability theory is not a subset of it.
      • 14113 12y ago
        No - complexity theory deals with the "hardness" of problems not of algorithms, and yes, then the bounds on what algorithms we can write to solve them. By that metric (and even by your own argument "the inability for algorithms"), the undecidability of the halting problem definitely fits within the complexity definition.
        • j2kun 12y ago
          If you won't listen to me (someone who does this for a living) maybe you will listen to a quote from wikipedia: > imposing restrictions on the available resources is what distinguishes computational complexity from computability theory And for the record when I say the ability of algorithms to do something I mean the class of all possible algorithms.
          • 14113 12y ago
            That is what I understood you as saying. I still don't see how my phrasing of the decidability of the halting problem as a complexity problem is any less valid. In any case, it's clear from your appeal-to-wikipedia that this conversation is over.
            • j2kun 12y ago
              > I still don't see how my phrasing of the decidability of the halting problem as a complexity problem is any less valid. Because you are not constraining any resources.