Timeline for What is the probability a random Turing machine is isomorphic to a DFA?
Current License: CC BY-SA 2.5
4 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 13, 2017 at 12:58 | history | edited | CommunityBot |
replaced http://mathoverflow.net/ with https://mathoverflow.net/
|
|
| Aug 24, 2010 at 15:12 | comment | added | Joel David Hamkins | Thanks, I'm glad that you appreciate the answer. Unfortunately, these measures are sensitive to the computational model. To see this issue plainly, consider how the notion of a random C++ program changes, depending on whether you allow ill-formed programs with syntax errors. If you allow them, then almost every program is junk, since there are far more junk strings than well-formed programs. Similar issues surround almost every particular notion of computation. | |
| Aug 24, 2010 at 14:40 | comment | added | Mikola | Wow! Great answer! Thank you for taking the time to type all of this out. I am curious though, does the asymptotic density only make sense with respect to some fixed model for computation? For example if you pick a different encoding scheme (such as lambda expressions, C programs, etc.) would you still compute the same asymptotic probabilities? Intuitively, I would expect that this is not the case since you could always create some silly prefix which would reweight probabilities. | |
| Aug 24, 2010 at 0:00 | history | answered | Joel David Hamkins | CC BY-SA 2.5 |