Timeline for What computational problems would be good proof-of-work problems for cryptocurrency mining?
Current License: CC BY-SA 3.0
14 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 4, 2017 at 23:06 | comment | added | Douglas Zare | Are you saying the person has to run the program that might take $10^{10^{100}}$ steps to halt and submit a transcript? There is a big problem here, and if you don't see it I'm done. Further, you still have not addressed the other fatal flaw. | |
| Jul 4, 2017 at 16:51 | comment | added | Douglas Zare | You still have not addressed the issue that the vast majority of programs can be simple to analyze while a tiny proportion is uncomputably difficult to analyze. Do you not think this is an issue? To me, this invalidates the idea that this is a proof-of-work. | |
| Jul 4, 2017 at 16:48 | comment | added | Douglas Zare | I'm referring to computing the halting probability. You say the network can validate the halting. We can prove that some programs halt though we can't expect to run the program long enough to observe that it halts. For example, we can write a short program that verifies unique prime factorization up to $10^{10^100}$ by trial division. This will halt. Do you submit the progam that halts, or do you submit a proof that it halts? There is no computable upper bound on the length of a proof of halting.There is a huge difference between verifying a long proof and computing a hash function. | |
| Jul 3, 2017 at 21:09 | comment | added | Douglas Zare | I don't understand what you mean by a proof on the lower bound of the length of the proof. That sounds much worse. What do you mean? And how do you address the issue that the vast majority of programs might halt quickly or quickly enter an obvious loop, while a tiny percentage are why the problem is unsolvable? | |
| Jul 3, 2017 at 17:45 | comment | added | Douglas Zare | Is this supposed to include a method for validating mathematical proofs? Suppose I prove that some program halts within $2^{2^{2^{100}}}$ steps. This is not that uncommon. How is this supposed to be verified? How do you address the fact that it is easy to determine whether a program halts for the vast majority of programs, but uncomputably hard on a few? | |
| Jun 5, 2017 at 21:18 | comment | added | John Tromp | While Chaitin would argue that his LISP is a great language for making Algorithmic Information Theory concrete (I argued the same for Binary Lambda Calculus, see tromp.github.io/cl/cl.html), I don't think he considers it "canonical". He knows that the choice of language is somewhat arbitrary. | |
| May 27, 2017 at 5:20 | history | edited | Mark S | CC BY-SA 3.0 |
provided more detail.
|
| May 26, 2017 at 18:33 | comment | added | Joseph Van Name | Carlos. If we wanted to use cryptocurrency proof-of-work problems to learn how to compress data better, then an appropriate proof-of-work problem would be to compress data directly (such as data from the blockchain). The winner in this problem is the user who compresses the data the most in 10 minutes. | |
| May 21, 2017 at 19:40 | comment | added | user76284 | Universal inductive inference and compression are applications. | |
| May 21, 2017 at 18:37 | history | edited | Mark S | CC BY-SA 3.0 |
refined answer, provided more detail.
|
| May 20, 2017 at 4:22 | comment | added | Joseph Van Name | While this proof-of-work problem may have "intrinsic value" to a few theoretical mathematicians, I doubt that the cryptocurrency community will embrace this proof-of-work problem since I do not see any practical real-world applications coming from this problem. | |
| May 19, 2017 at 20:06 | comment | added | Jason Rute | The exact value of $\Omega$ is highly dependent on how it is encoded via a universal machine, just like the Halting Problem. (In computability theory, we [or at least I] have a habit of calling any left c.e. Martin-Löf random $\Omega$.) While I think Chaitin has a strong opinion that his encoding of $\Omega$ is the canonical one, I don't think that opinion is shared by many in the field. | |
| May 19, 2017 at 0:28 | history | edited | Mark S | CC BY-SA 3.0 |
simplified response
|
| May 18, 2017 at 2:28 | history | answered | Mark S | CC BY-SA 3.0 |