3 ms·

> By the end of this post, you will know: > • What can and cannot be computed. I don’t think it delivered on the “can” part. (And I don’t think we really know

by layer8 2y ago

> By the end of this post, you will know: > • What can and cannot be computed. I don’t think it delivered on the “can” part. (And I don’t think we really know that well.)

samwho 2y ago
When I was working on this post I found the way that Turing defined “computable numbers” I bit unsatisfying as well. What would you suggest I do to deliver on this?
- layer8 2y ago
  I would suggest to not promise it. ;) Maybe rather: • That some truths cannot be computed.
  - samwho 2y ago
    I’m not sure I understand. I do explain what can be computed, don’t I? > Something is said to be "computable" if there exists an algorithm that can get from the given input to the expected output. For example, adding together 2 integers is computable. I could probably have dug into some of the restrictions, like how it has to be a finite number of steps.
    - layer8 2y ago
      This defines the term “computable”, but it doesn’t give you a sense of what things can be computed. Defining a term is entirely different from the above promise. At the level you’re describing Turing machines, it’s also not clear that readers would have a precise notion of what an algorithm is. At no point (unless I missed it) do you explain that any algorithm is supposed to be implementable as a Turing machine, or the assumption of what is otherwise known as the Church–Turing thesis.
      - samwho 2y ago
        That’s true, there’s no explicit definition of what an algorithm is. I may revisit this. Thank you for the feedback.
voidhorse 2y ago
Unless I am missing something, as far as the work of Turing and Church is concerned, their answers are actually quite clear on this question of "can", namely the class of partial recursive functions. This is precisely what a Turing machine can compute. It is also possible to build up to these functions in a concrete way using the simpler class of primitive recursive functions. Rogers book on recursive functions and computability is a great reference on this topic.

by layer8 2y ago

> By the end of this post, you will know: > • What can and cannot be computed. I don’t think it delivered on the “can” part. (And I don’t think we really know that well.)

samwho 2y ago

When I was working on this post I found the way that Turing defined “computable numbers” I bit unsatisfying as well. What would you suggest I do to deliver on this?

layer8 2y ago
I would suggest to not promise it. ;) Maybe rather: • That some truths cannot be computed.
- samwho 2y ago
  I’m not sure I understand. I do explain what can be computed, don’t I? > Something is said to be "computable" if there exists an algorithm that can get from the given input to the expected output. For example, adding together 2 integers is computable. I could probably have dug into some of the restrictions, like how it has to be a finite number of steps.
  - layer8 2y ago
    This defines the term “computable”, but it doesn’t give you a sense of what things can be computed. Defining a term is entirely different from the above promise. At the level you’re describing Turing machines, it’s also not clear that readers would have a precise notion of what an algorithm is. At no point (unless I missed it) do you explain that any algorithm is supposed to be implementable as a Turing machine, or the assumption of what is otherwise known as the Church–Turing thesis.
    - samwho 2y ago
      That’s true, there’s no explicit definition of what an algorithm is. I may revisit this. Thank you for the feedback.

voidhorse 2y ago

Unless I am missing something, as far as the work of Turing and Church is concerned, their answers are actually quite clear on this question of "can", namely the class of partial recursive functions. This is precisely what a Turing machine can compute. It is also possible to build up to these functions in a concrete way using the simpler class of primitive recursive functions. Rogers book on recursive functions and computability is a great reference on this topic.