News for hackers. Stuff that matters.
Re:On Two Views of Computation in Computer Science by TelmoMenezes on Wednesday August 31, 2016 @09:08PM (#12402565)
Yes but the real number that cannot be pinned down using a formula can also not be pinned down using a computation, and we are talking of models of computation.
Re:On Two Views of Computation in Computer Science by catnaroek on Wednesday August 31, 2016 @10:35PM (#12402798)
> Yes but the real number that cannot be pinned down using a formula can also not be pinned down using a computation,

Undefinable real numbers exist, whether you can compute them or not.

> and we are talking of models of computation.

A theory of computation that rejects the existence of things that can't be computed is like a logic that rejects the existence of FALSE because it can't be proved. Where does the busy beaver function sit in your conceptual model?

Re:On Two Views of Computation in Computer Science by TelmoMenezes on Thursday September 01, 2016 @06:47AM (#12404261)
> Undefinable real numbers exist, whether you can compute them or not.

I agree with you, but as you probably know this is a deep ontological question. The meaning of something "existing" has been debated for many centuries, especially for cases such as this.

> A theory of computation that rejects the existence of things that can't be computed is like a logic that rejects the existence of FALSE because it can't be proved. Where does the busy beaver function sit in your conceptual model?

There is a difference between rejecting and classifying. I am not proposing a new computational model. Turing's model classifies the busy beaver function as non-computable. Correct?

I thought we were discussing Church-Turing. This assumes Turing Machines, and what they can compute. Of course you can break everything by assuming an imaginary machine that can compute functions that are not computable by Turing Machines...

Re:On Two Views of Computation in Computer Science by catnaroek on Thursday September 01, 2016 @07:49AM (#12404499)
> Turing's model classifies the busy beaver function as non-computable. Correct?

Yep.

> I thought we were discussing Church-Turing. This assumes Turing Machines, and what they can compute. Of course you can break everything by assuming an imaginary machine that can compute functions that are not computable by Turing Machines...

Turing never redefined the concept of “countable”, which belongs in set theory. If you had asked him what the cardinality is of the set of functions from the naturals to the naturals, he would've answered you “uncountable, of course”.