5 ms·

I'll bite. You can make a program the maps from integers (expressed in binary) to the real interval between 0 to 1. No matter what bit string the program output

I'll bite. You can make a program the maps from integers (expressed in binary) to the real interval between 0 to 1. No matter what bit string the program outputs, it is meant to be (and thus interpreted as) the binary digits of the number that come after the decimal point. Thus there is no need for a proof of convergence, by the very nature of the representation it is impossible for the machine to output something that isn't a number somewhere on the interval from 0-1. All that matters then is proving it won't halt. But I can easily make sure it never halts by having a program that sits on top waiting for it to halt, and then if it does, restarts the program. So I can check the mapping from the integers to the interval, and by extension from the integers to the real number line.

Viliam1234 4y ago
I am just guessing here, but I think the problem is that even if you redefine a real number as "that which can be written by a program", you cannot write a program that enumerates all such numbers. That's kinda because different real numbers require programs of different complexity (for any specific complexity, e.g. the number of bytes, there is only a finite number of programs with that complexity), so listing all the real numbers would require infinite complexity, i.e. not a (finite) program. So there is a countable set of integer, and a set of reals (by the new definition) which is countable (by the usual definition) but cannot be enumerated, so it is technically "uncountable" (by the new definition). The trick is that if you are changing definitions, you may accidentally also change the definition of "countable". Because it is defined as "that which can be mapped to integers", but the problem is, which mappings are considered legal and which are not. In the world of "only things written by programs exist", only mappings which can be generated by programs exist; which is not the same as all possible mappings, so a few previously countable things now become "uncountable".
yababa_y 4y ago
… in python?
dreamcompiler 4y ago
You can write a program that will always generate a real number, but you can't write a program that will generate all of the reals, or even any single real that's irrational (like pi). And the vast, vast majority of reals are irrational. The best you can do is a program that generates a crude approximation to an irrational, because you'd need an infinite number of states to write the entire number and every physical computer has a finite number of states. If your program that sits on top restarts the underlying program, then it will generate a repeating binary sequence. And that's a rational number.
- IIAOPSW 4y ago
  >The best you can do is a program that generates a crude approximation to an irrational, because you'd need an infinite number of states to write the entire number and every physical computer has a finite number of states. I can provide you with the requested infinite amount of state, I merely require infinite amounts of time. >If your program that sits on top restarts the underlying program, then it will generate a repeating binary sequence. And that's a rational number. And that would be stupid and obviously wrong. I should have clarified that the program sitting on top interrupting stuff is obviously changing something before restarting. Could be anything. Maybe flips some stateful starting info, maybe swaps to a different program, maybe starts xoring the output with something. Could be anything
  - btilly 4y ago
    Again, the same trap. It doesn't matter what the program sitting on top changes, it does so in a deterministic way. And therefore the emulation of the program changes the same thing, in the same way. Which means that the emulation cannot figure out the next bit of its output faster than the actual program. And therefore the program either never decides to output anything which would have diagonalized itself, or it gets stuck after a finite time by a liar's paradox attempting to figure out the next bit of it would put out so that it can put something different out instead. Either way diagonalization of itself cannot succeed. The reasoning here is very similar to Turing's proof of the Halting Problem - no program exists that is able to take a program + input and reliably determine whether that program will halt. And the reason is that you set up a program which would have to set up a liar's paradox about itself fed input that translates to itself fed input about itself recursively. The only logically consistent result is that this program both cannot halt, and cannot figure out that it doesn't halt.
btilly 4y ago
Yes, you can write your program. And yes, you can guarantee that it will not halt. And yes, you can guarantee that its output is different than any program it managed to emulate. But what happens when it tries to emulate itself? Well, if it produced any output, it would immediately produce a different output. The way out of paradox is that it returns nothing at all. The program that sits on top now has a choice. If it decides to let the program continue to grind away, it NEVER produces that next digit. If it has any kind of logic that will give up after long enough, it WILL give up and move on. Either way your program will fail to produce an output that is different from its own output. And therefore diagonalization fails.
- IIAOPSW 4y ago
  >But what happens when it tries to emulate itself? Well, if it produced any output, it would immediately produce a different output. The way out of paradox is that it returns nothing at all. Why immediately. It only has to differ by one bit somewhere along the infinite chain right? Why waste that perfectly good output when it can just as well output some of the emulation before interrupting it?
  - btilly 4y ago
    You can try many variations on the scheme. All will fall prey to the fact that the program must produce the same output as its emulation of itself. It can never get around this fact. Therefore it either produces a finite amount of input and then stops waiting for its emulated self, or it never gets around to producing something different than itself. Either way it fails to diagonalize itself. The exact cause will vary. The eventual result will not. Classical mathematics gets around this by waving hands over constructions with impossible procedures based on undiscoverable truths. By assumption these procedures can never be the input to themselves. The result is an insane number of possible outputs about whose tenuous existence we can say little but our claim that they exist. No argument of pure logic alone can demonstrate any form of existence for these impossibilities, you must make additional unprovable philosophical assumptions about the nature of truth and existence. I know that these techniques and results seem natural to you. But that is a consequence of your indoctrination into a system of thought which glosses over these complications instead of exploring them.

Viliam1234 4y ago

I am just guessing here, but I think the problem is that even if you redefine a real number as "that which can be written by a program", you cannot write a program that enumerates all such numbers. That's kinda because different real numbers require programs of different complexity (for any specific complexity, e.g. the number of bytes, there is only a finite number of programs with that complexity), so listing all the real numbers would require infinite complexity, i.e. not a (finite) program. So there is a countable set of integer, and a set of reals (by the new definition) which is countable (by the usual definition) but cannot be enumerated, so it is technically "uncountable" (by the new definition). The trick is that if you are changing definitions, you may accidentally also change the definition of "countable". Because it is defined as "that which can be mapped to integers", but the problem is, which mappings are considered legal and which are not. In the world of "only things written by programs exist", only mappings which can be generated by programs exist; which is not the same as all possible mappings, so a few previously countable things now become "uncountable".

yababa_y 4y ago

… in python?

dreamcompiler 4y ago

You can write a program that will always generate a real number, but you can't write a program that will generate all of the reals, or even any single real that's irrational (like pi). And the vast, vast majority of reals are irrational. The best you can do is a program that generates a crude approximation to an irrational, because you'd need an infinite number of states to write the entire number and every physical computer has a finite number of states. If your program that sits on top restarts the underlying program, then it will generate a repeating binary sequence. And that's a rational number.

IIAOPSW 4y ago
>The best you can do is a program that generates a crude approximation to an irrational, because you'd need an infinite number of states to write the entire number and every physical computer has a finite number of states. I can provide you with the requested infinite amount of state, I merely require infinite amounts of time. >If your program that sits on top restarts the underlying program, then it will generate a repeating binary sequence. And that's a rational number. And that would be stupid and obviously wrong. I should have clarified that the program sitting on top interrupting stuff is obviously changing something before restarting. Could be anything. Maybe flips some stateful starting info, maybe swaps to a different program, maybe starts xoring the output with something. Could be anything
- btilly 4y ago
  Again, the same trap. It doesn't matter what the program sitting on top changes, it does so in a deterministic way. And therefore the emulation of the program changes the same thing, in the same way. Which means that the emulation cannot figure out the next bit of its output faster than the actual program. And therefore the program either never decides to output anything which would have diagonalized itself, or it gets stuck after a finite time by a liar's paradox attempting to figure out the next bit of it would put out so that it can put something different out instead. Either way diagonalization of itself cannot succeed. The reasoning here is very similar to Turing's proof of the Halting Problem - no program exists that is able to take a program + input and reliably determine whether that program will halt. And the reason is that you set up a program which would have to set up a liar's paradox about itself fed input that translates to itself fed input about itself recursively. The only logically consistent result is that this program both cannot halt, and cannot figure out that it doesn't halt.

btilly 4y ago

Yes, you can write your program. And yes, you can guarantee that it will not halt. And yes, you can guarantee that its output is different than any program it managed to emulate. But what happens when it tries to emulate itself? Well, if it produced any output, it would immediately produce a different output. The way out of paradox is that it returns nothing at all. The program that sits on top now has a choice. If it decides to let the program continue to grind away, it NEVER produces that next digit. If it has any kind of logic that will give up after long enough, it WILL give up and move on. Either way your program will fail to produce an output that is different from its own output. And therefore diagonalization fails.

IIAOPSW 4y ago
>But what happens when it tries to emulate itself? Well, if it produced any output, it would immediately produce a different output. The way out of paradox is that it returns nothing at all. Why immediately. It only has to differ by one bit somewhere along the infinite chain right? Why waste that perfectly good output when it can just as well output some of the emulation before interrupting it?
- btilly 4y ago
  You can try many variations on the scheme. All will fall prey to the fact that the program must produce the same output as its emulation of itself. It can never get around this fact. Therefore it either produces a finite amount of input and then stops waiting for its emulated self, or it never gets around to producing something different than itself. Either way it fails to diagonalize itself. The exact cause will vary. The eventual result will not. Classical mathematics gets around this by waving hands over constructions with impossible procedures based on undiscoverable truths. By assumption these procedures can never be the input to themselves. The result is an insane number of possible outputs about whose tenuous existence we can say little but our claim that they exist. No argument of pure logic alone can demonstrate any form of existence for these impossibilities, you must make additional unprovable philosophical assumptions about the nature of truth and existence. I know that these techniques and results seem natural to you. But that is a consequence of your indoctrination into a system of thought which glosses over these complications instead of exploring them.