bio | website | |
---|---|---|
location | Seattle WA USA | |
age | ||
visits | member for | 2 years, 8 months |
seen | May 5 at 3:52 | |
stats | profile views | 227 |
May 5 |
comment |
Comparing the Kolmogorov complexity of theories - Part 2
Busy beaver emulators already exist and they are smaller than $10^9$ bits. A better choice of a large number might be the binary number defined by someone's 500GB disk drive. |
May 5 |
comment |
Comparing the Kolmogorov complexity of theories - Part 2
This link explains how busy beavers (BB) can be used to define the Kolmogorov complexity of a number. $K(43572578434728593772315)$ may not have been the best choice considering there is a six state BB that writes $10^{36534}$ 1's. I think we both agree a relatively small program can enumerate all BB's and emulate them. |
May 5 |
revised |
Comparing the Kolmogorov complexity of theories - Part 2
fix a mis-spelling |
May 3 |
revised |
Comparing the Kolmogorov complexity of theories - Part 2
clear up confusion |
May 3 |
comment |
Comparing the Kolmogorov complexity of theories - Part 2
The 23 digit number was assuming a busy beaver computational model. For a modern x86 microprocessor model we would need $10^9$ digits like I said in my earlier comment. |
May 2 |
comment |
Comparing the Kolmogorov complexity of theories - Part 2
How are you encoding a number with $10^9$ digits? My disk drive has over 300GB of files. Can the contents of my disk drive be compressed to the point the decompression program and compressed data combined are less the 1GB? |
May 2 |
awarded | Curious |
May 2 |
comment |
Comparing the Kolmogorov complexity of theories - Part 2
@Joel David Hamkins: I was thinking of an n state busy beaver which writes a string of 43572578434728593772315 consecutive 1's and halts. If our model of computation is a modern x86 microprocessor we would probably need a number with more than $10^9$ digits. |
May 1 |
revised |
Comparing the Kolmogorov complexity of theories - Part 2
respond to comments |
May 1 |
asked | Comparing the Kolmogorov complexity of theories - Part 2 |
Mar 25 |
awarded | Yearling |
Mar 25 |
revised |
Is there a natural bijection from $\mathbb{N}$ to $\mathbb{Q}$?
fix typo |
Mar 24 |
answered | Is there a natural bijection from $\mathbb{N}$ to $\mathbb{Q}$? |
May 25 |
awarded | Good Question |
Feb 23 |
comment |
Can a Decidable Theory Have Non-recursive Models?
This is what I thought, too. We can encode a set of ordered triples proving addition and multiplication are total over a finite field. I don't see the significance of the algorithm being "nonstandard". All algorithms are nonstandard in a nonstandard model. |
Feb 21 |
comment |
Can a Decidable Theory Have Non-recursive Models?
Assume there is an algorithm that can prove if a finite field is recursive. It would prove all standard finite fields are recursive. Using overspill we could then prove there must exist a recursive nonstandard finite field violating Tennenbaum's theorem. I don't see how we could prove all finite fields are recursive. |
Feb 15 |
comment |
Can a Decidable Theory Have Non-recursive Models?
OK. Could a finite field be an input to an algorithm? |
Feb 15 |
comment |
Can a Decidable Theory Have Non-recursive Models?
Tao's blog talks about decidable subsets of nonstandard finite fields. It seems reasonable to ask if such a subset can encode a recursively inseparable set. It makes sense this might require defining non-computable constants. I hadn't thought about non-recursive models of Presburger arithmetic. Does this mean there is no algorithm to tell which models of Presburger arithmetic are recursive? |
Feb 15 |
accepted | Can a Decidable Theory Have Non-recursive Models? |
Feb 15 |
revised |
Can a Decidable Theory Have Non-recursive Models?
fix a mistake |