News for hackers. Stuff that matters.
Re:Church-Turing Thesis Cannot Possibly Be True [video] by daveFNbuck on Friday October 19, 2018 @02:14AM (#18254543)
I'm having a hard time understanding the difference between outputting something and representing it. Can you explain the difference, or is that just your best understanding of the argument here?
Re:Church-Turing Thesis Cannot Possibly Be True [video] by rocqua on Friday October 19, 2018 @03:41AM (#18254833)
The point is that we can represent sqrt(2) symbolically (as I just did there) but it cannot be represented as a binary (or decimal) expansion.

Computers can also work symbolically rather than based on some direct binary representation. I think equality and especially comparison become more difficult to determine, but it remains possible.

Re:Church-Turing Thesis Cannot Possibly Be True [video] by vidarh on Friday October 19, 2018 @06:19AM (#18255567)
But this merely a product of the choice of representation.

Here is a fully expanded representation: 1.

Of course my choice of base is a bit exotic, but the point is that no matter what, we're working on symbols. We're just used to seeing some as more direct analogues of numbers than others.

Re:Church-Turing Thesis Cannot Possibly Be True [video] by daveFNbuck on Friday October 19, 2018 @10:00AM (#18256763)
What's a direct binary representation? If that means having each digit explicitly written out, no model of computation could possibly do that in finite time. If it means having the ability to output arbitrary bits in finite time, Turing machines can do that.
Re:Church-Turing Thesis Cannot Possibly Be True [video] by obastani on Friday October 19, 2018 @11:04AM (#18257163)
It's probably easier to give an example of a number that I can't represent symbolically. However, I can't give you a specific example, since if I uniquely define a number then that definition is itself a symbolic representation of that number. But here is an example: a uniformly random real number on [0, 1]. Or, computationally speaking, uniformly sample an infinite number of Bernoulli random variables, and write down the binary representation. Of course, this process takes infinite time, which suggests that they are not representable.

For a proof, consider the fact that every representable number, by definition (I know I haven't given a formal definition), is represented by some finite string. But the number of finite strings is countable. So it must be a measure zero subset of [0, 1], so a random sample is representable with probability zero.

Re:Church-Turing Thesis Cannot Possibly Be True [video] by jacobush on Friday October 19, 2018 @02:46AM (#18254650)
Or put differently:

How long is that piece of string?

a) Here, have a look at it. It's exactly that long.

b) 4.51 inches

both answers are correct. "a" is correct by definition. "b" may be totally correct if we add a precision to the answer, like +- 0.01 or whatever we find true.

Re:Church-Turing Thesis Cannot Possibly Be True [video] by grey-area on Friday October 19, 2018 @04:47AM (#18255165)
How long is that piece of string?

With how much precision can you measure it?

With how much precision can you describe it?

The answers are pretty similar for humans or turing machines IMO.

Re:Church-Turing Thesis Cannot Possibly Be True [video] by joe_the_user on Friday October 19, 2018 @02:32AM (#18254608)
An output would be a physical extent in space (a line of some length, the turning of a dial, etc), a representation would be an description.
Re:Church-Turing Thesis Cannot Possibly Be True [video] by daveFNbuck on Friday October 19, 2018 @10:17AM (#18256875)
Under that definition, can Turing machines produce output at all? It seems that the Church-Turing thesis is about representations and not outputs.
Re:Church-Turing Thesis Cannot Possibly Be True [video] by roywiggins on Friday October 19, 2018 @10:32AM (#18256966)
The original formulation of the machine just operates on a tape, the closest thing to an output it has is moving the tape into a particular state (such as writing down the digits of the calculated function on successive cells of the tape). But there's no "output" function to spit out a number. You can just tack that onto the specification if you want, but it doesn't change the power of the device really.
Re:Church-Turing Thesis Cannot Possibly Be True [video] by daveFNbuck on Friday October 19, 2018 @11:05AM (#18257174)
I'm specifically asking about joe_the_user's definition of output as being a physical object rather than a number.