4 ms·

I see your universal predictor and raise you one non-halting program (in a language of your choice).

Vecr 3y ago
Yes that's why it would be something like a Gödel machine[0]. Ignore everything it can't prove is not malicious (won't halt, runs too long, takes too many resources, etc.). [0]: https://en.wikipedia.org/wiki/G%C3%B6del_machine https://en.wikipedia.org/wiki/G%C3%B6del_machine
riku_iki 3y ago
is halting program something can happen in infinite space? If space is finite, you can just memorize all processed internal states of the program, there are two options: - program gets into infinite loop, which will be detected by checking that internal program state was observed in the past already - program will actually halt
Xcelerate 3y ago
I see your pathological proof of existence and raise you an asymptotic probability of one: “The halting problem for Turing machines is perhaps the canonical undecidable set. Nevertheless, we prove that there is an algorithm deciding almost all instances of it.” https://arxiv.org/pdf/math/0504351.pdf https://arxiv.org/pdf/math/0504351.pdf
- riku_iki 3y ago
  "almost all" is very speculative term. What is "almost all" of natural numbers for example?..
  - drdeca 3y ago
    A subset with asymptotic density of 1?
    - riku_iki 3y ago
      in common math/geometry, all natural numbers altogether I think will have density 0..
      - drdeca 3y ago
        The asymptotic density of a subset of the natural numbers, is defined as the limit of (number of elements of the set which are less than N)/N , as N goes to infinity.
        riku_iki 3y ago
        Ok, by this definition I believe if you consider set of natural number without say n^2 numbers, then density will be 1, or "almost all", while class we ignored and similar classes are quite large and important.
        drdeca 3y ago
        Yes, the asymptotic density of “natural numbers which are not perfect squares” is 1. I.e. “almost all natural numbers are not perfect squares”. And similarly for many other important classes. Almost all natural numbers are not prime. Etc. etc.

Vecr 3y ago

Yes that's why it would be something like a Gödel machine[0]. Ignore everything it can't prove is not malicious (won't halt, runs too long, takes too many resources, etc.). [0]: https://en.wikipedia.org/wiki/G%C3%B6del_machine https://en.wikipedia.org/wiki/G%C3%B6del_machine

riku_iki 3y ago

is halting program something can happen in infinite space? If space is finite, you can just memorize all processed internal states of the program, there are two options: - program gets into infinite loop, which will be detected by checking that internal program state was observed in the past already - program will actually halt

Xcelerate 3y ago

I see your pathological proof of existence and raise you an asymptotic probability of one: “The halting problem for Turing machines is perhaps the canonical undecidable set. Nevertheless, we prove that there is an algorithm deciding almost all instances of it.” https://arxiv.org/pdf/math/0504351.pdf https://arxiv.org/pdf/math/0504351.pdf

riku_iki 3y ago
"almost all" is very speculative term. What is "almost all" of natural numbers for example?..
- drdeca 3y ago
  A subset with asymptotic density of 1?
  - riku_iki 3y ago
    in common math/geometry, all natural numbers altogether I think will have density 0..
    - drdeca 3y ago
      The asymptotic density of a subset of the natural numbers, is defined as the limit of (number of elements of the set which are less than N)/N , as N goes to infinity.
      - riku_iki 3y ago
        Ok, by this definition I believe if you consider set of natural number without say n^2 numbers, then density will be 1, or "almost all", while class we ignored and similar classes are quite large and important.
        drdeca 3y ago
        Yes, the asymptotic density of “natural numbers which are not perfect squares” is 1. I.e. “almost all natural numbers are not perfect squares”. And similarly for many other important classes. Almost all natural numbers are not prime. Etc. etc.