1253
this one goes out to the arts & humanities (mander.xyz)
submitted 2 years ago by to c/science_memes@mander.xyz
246 comments fedilink hide all child comments
 
you are viewing a single comment's thread
view the rest of the comments
[–] 25 points 2 years ago (4 children)

Turing Incompleteness is a pathway to many powers the Computer Scientists would consider incalculable.

  • permalink
  • fedilink
  • source
  • hideshow 8 child comments
    •
  • [–] 4 points 2 years ago* (last edited 2 years ago) (1 child)

    In fact, there's infinite problems that cannot be solved by Turing machnes!

    (There are countably many Turing-computable problems and uncountably many non-Turing-computable problems)

  • permalink
  • fedilink
  • source
  • parent
  • hideshow 2 child comments
    •
  • [–] -1 points 2 years ago (2 children)

    Infinite seems like it's low-balling it, then. 0% of problems can be solved by Turing machines (same way 0% of real numbers are integers)

  • permalink
  • fedilink
  • source
  • parent
  • hideshow 4 child comments
    •
  • [–] 2 points 2 years ago (1 child)

    Infinite seems like it's low-balling it

    Infinite by definition cannot be "low-balling".

    0% of problems can be solved by Turing machines (same way 0% of real numbers are integers)

    This is incorrect. Any computable problem can be solved by a Turing machine. You can look at the Church-Turing thesis if you want to learn more.

  • permalink
  • fedilink
  • source
  • parent
  • hideshow 2 child comments
    •
  • [–] 1 point 2 years ago (1 child)

    Infinite by definition cannot be “low-balling”.

    I was being cheeky! It could've been that the set of non-Turing-computible problems had measure zero but still infinite cardinality. However there's the much stronger result that the set of Turing-computible problems actually has measure zero (for which I used 0% and the integer:reals thing as shorthands because I didn't want to talk measure theory on Lemmy). This is so weird, I never got downvoted for this stuff on Reddit.

  • permalink
  • fedilink
  • source
  • parent
  • hideshow 2 child comments
    •