428 reputation
310
bio website
location Seattle WA USA
age
visits member for 2 years, 8 months
seen May 5 at 3:52

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