121–130 of 146 posts
BB(3,3) is busy beaver (BB) problem, a subset of Turing machines (TM) [0], with 3 states (A,B,C) and three symbols (0,1,2) that can be written onto the infinitely long tape. An additional criteria for a Busy Beaver-like Turing machine is that there is a "halt" state, which can be seen in the article's table for state C reading input 0. The table in the article (under "The Machine" section) describes the state on the…
BB(3,3) is busy beaver (BB) problem, a subset of Turing machines (TM) [0], with 3 states (A,B,C) and three symbols (0,1,2) that can be written onto the infinitely long tape. An additional criteria for a Busy Beaver-like Turing machine is that there is a "halt" state, which can be seen in the article's table for state C reading input 0. The table in the article (under "The Machine" section) describes the state on the…
[deleted]
Earlier quoted context omitted.
No, if you had an algorithm that (you could prove) halts iff ZFC is consistent, then if that algorithm halts, you’ll have a proof that ZFC is consistent, which isn’t possible. Thus, the existence of such an algorithm would be a contradiction that proves the inconsistency of ZFC. The problem with your construction is that it relies on knowing the value of BB(754), which is impossible to know so long as ZFC is consiste…
> The problem with your construction is that it relies on knowing the value of BB(754) Eh, this doesn’t really matter. That busy beaver number is just an integer, so there is some TM that does exactly as I have described. Thus, there I have proved that there is a turing machine that halts iff ZFC is consistent.
I can define another integer N which is 1 if there exists a proof of the inconsistency of ZFC and 0 if there doesn’t (note that BB(754) already encodes this information). Then I can define a program that determines the consistency of ZFC thusly: if N=1, I define the program to immediately return false. If N=0, I define the program to immediately return true. Thus, there exists a program that can determine the consistency of ZFC, it’s one of the two programs I’ve defined.
The fact that there exists a program that returns the consistency of ZFC isn’t in question. The trick is proving that a particular program does so. Or if you like, proving that there exists a program along with a proof that it does so. What you’ve defined is an oracle: it depends on already knowing the answer to what you’re asking so it doesn’t have to compute it.
I'm hoping someone can enlighten me here. My understanding is that there is a turing machine of 748 states [0], which halts iff ZFC is inconsistent (Thm 1). But this machine is a "physical" object, in the sense that we can materialize it on a computer and run it. Though we don't have the computing power for this currently, there is nothing in principle stopping us from running this machine for BB(748) steps: if it ha…
So if it's inconsistent, it's straight forward to prove. It's only if it's consistent that we can't prove it in any finite time.
Earlier quoted context omitted.
> if you agree that counting starts at 1 I argue that counting really starts at 0 in https://news.ycombinator.com/item?id=33022031
I guess it is the difference between measuring the size of a set, and labelling the elements of the set with a number. Both can be called "counting", but the meaning is different. The first of something should always be labelled 1, but obviously the empty set has size 0. That's the main problem I have with using ℕ for {0, 1, 2, ...}. It's easy to get into the habit of writing stuff like x_0, ..., x_{n-1} for n elemen…
I think it's no better than using N and N^+ [1]. Note that all formal definitions on that Wikipedia page take ℕ = ℕ₀
Earlier quoted context omitted.
> The problem with your construction is that it relies on knowing the value of BB(754) Eh, this doesn’t really matter. That busy beaver number is just an integer, so there is some TM that does exactly as I have described. Thus, there I have proved that there is a turing machine that halts iff ZFC is consistent.
It’s an unknown integer, whose value depends on the consistency of ZFC. Let me show you why this is circular. I can define another integer N which is 1 if there exists a proof of the inconsistency of ZFC and 0 if there doesn’t (note that BB(754) already encodes this information). Then I can define a program that determines the consistency of ZFC thusly: if N=1, I define the program to immediately return false. If N=0…
What we’ve seen is that there plainly exists a Turing machine which halts iff ZFC is consistent.
All of the other window dressing you’ve added hasn’t changed that simple fact.
I agree that finding busy beaver numbers is the issue. I do not agree that the existence of a TM that halts iff ZFC is consistent is hard.
Earlier quoted context omitted.
I guess it is the difference between measuring the size of a set, and labelling the elements of the set with a number. Both can be called "counting", but the meaning is different. The first of something should always be labelled 1, but obviously the empty set has size 0. That's the main problem I have with using ℕ for {0, 1, 2, ...}. It's easy to get into the habit of writing stuff like x_0, ..., x_{n-1} for n elemen…
> I think ℕ and ℕ₀ is a good way out of this dilemma. I think it's no better than using N and N^+ [1]. Note that all formal definitions on that Wikipedia page take ℕ = ℕ₀ [1] https://en.wikipedia.org/wiki/Natural_number#Notation
Logic likes to unify things, so formal definitions usually start with 0, and conflate sizing and labelling. Note that Peano first started counting from 1. Later on he changed it to 0. Doesn't mean that's the right thing to do, though. Maybe these two concepts should be kept separate: ℕ for (default) labelling, and ℕ₀ for sizing.
Earlier quoted context omitted.
BB(n) refers to Turing machines that have n states and 2 symbols. The version with two arguments lets you specify the number of states and the number of symbols respectively. So BB(n) = BB(n, 2) .
Are they fundamentally different or could you always map a BB(x,y) to a BB(z), where presumably z is much larger than x?
I would say a better question is to determine if there's some type of polynomial time/space reduction from BB(x,y) to BB(z), in construction and runtime. I suspect yes though I wouldn't be able to rattle off a proof without a lot of effort. See [1] which might answer this question.
[0] https://en.wikipedia.org/wiki/Universal_Turing_machine
[1] https://cs.stackexchange.com/questions/63136/does-the-amount...
Earlier quoted context omitted.
It’s an unknown integer, whose value depends on the consistency of ZFC. Let me show you why this is circular. I can define another integer N which is 1 if there exists a proof of the inconsistency of ZFC and 0 if there doesn’t (note that BB(754) already encodes this information). Then I can define a program that determines the consistency of ZFC thusly: if N=1, I define the program to immediately return false. If N=0…
It is not circular. Such a Turing machine clearly exists. What we’ve seen is that there plainly exists a Turing machine which halts iff ZFC is consistent. All of the other window dressing you’ve added hasn’t changed that simple fact. I agree that finding busy beaver numbers is the issue. I do not agree that the existence of a TM that halts iff ZFC is consistent is hard.
Is this what we mean when we says BB are uncomputable? That as BB grows they incompass all of maths, requiring us to prove everything?
Sort of . Uncomputable functions exist because the halting problem exists. So any function whose definition includes anything to do with halting also becomes uncomputable. e.g. BB is uncomputable because you have to determine all the TMs that would halt given n and m. The entire rest of mathematics is smuggled into BB via the halting problem: you can write programs that only halt if arbitrary mathematical conjectures…
Uncomputable functions exist because there are only countably many Turing machines. There are problems that stay uncomputable even if the halting problem were computable.