Skip to main content
Typo.
Source Link
Joseph O'Rourke
  • 150.8k
  • 36
  • 358
  • 958

(a) I think that "no human understands" what the current busiest $6$-state Busy Beaver $2$-symbol Turing Machine is doing while it prints out $3.5 \times 10^{18267}$ $1$'s before halting.

(b) This does not quite address your 2nd question as you phrased it, but there are several $5$-state quite-Busy Beavers that are believed to loop, but no one can prove they loop, or prove they halt. A list of these irregular Turing Machines is maintained here.

Incidentally, just to illustrate the complexity of Busy-Beaver questions, a $4888$-state Turing Machine has been constructed which halts if and only if there is a counterexamnplecounterexample to Goldbach's conjecture.

Yedidia, Adam, and Scott Aaronson. "A Relatively Small Turing Machine Whose Behavior Is Independent of Set Theory." arXiv:1605.04343 (2016). (arXiv Abstract.)

(a) I think that "no human understands" what the current busiest $6$-state Busy Beaver $2$-symbol Turing Machine is doing while it prints out $3.5 \times 10^{18267}$ $1$'s before halting.

(b) This does not quite address your 2nd question as you phrased it, but there are several $5$-state quite-Busy Beavers that are believed to loop, but no one can prove they loop, or prove they halt. A list of these irregular Turing Machines is maintained here.

Incidentally, just to illustrate the complexity of Busy-Beaver questions, a $4888$-state Turing Machine has been constructed which halts if and only if there is a counterexamnple to Goldbach's conjecture.

Yedidia, Adam, and Scott Aaronson. "A Relatively Small Turing Machine Whose Behavior Is Independent of Set Theory." arXiv:1605.04343 (2016). (arXiv Abstract.)

(a) I think that "no human understands" what the current busiest $6$-state Busy Beaver $2$-symbol Turing Machine is doing while it prints out $3.5 \times 10^{18267}$ $1$'s before halting.

(b) This does not quite address your 2nd question as you phrased it, but there are several $5$-state quite-Busy Beavers that are believed to loop, but no one can prove they loop, or prove they halt. A list of these irregular Turing Machines is maintained here.

Incidentally, just to illustrate the complexity of Busy-Beaver questions, a $4888$-state Turing Machine has been constructed which halts if and only if there is a counterexample to Goldbach's conjecture.

Yedidia, Adam, and Scott Aaronson. "A Relatively Small Turing Machine Whose Behavior Is Independent of Set Theory." arXiv:1605.04343 (2016). (arXiv Abstract.)

Added link.
Source Link
Joseph O'Rourke
  • 150.8k
  • 36
  • 358
  • 958

(a) I think that "no human understands" what the current busiest $6$-state Busy Beaver $2$-symbol Turing Machine is doing while it prints out $3.5 \times 10^{18267}$ $1$'s before halting.

(b) This does not quite address your 2nd question as you phrased it, but there are several $5$-state quite-Busy Beavers that are believed to loop, but no one can prove they loop, or prove they halt. A list of these irregular Turing Machines is maintained here.

Incidentally, just to illustrate the complexity of Busy-Beaver questions, a $4888$-state Turing Machine has been constructed which halts if and only if there is a counterexamnple to Goldbach's conjecture.

Yedidia, Adam, and Scott Aaronson. "A Relatively Small Turing Machine Whose Behavior Is Independent of Set Theory." arXiv:1605.04343 (2016). (arXiv Abstract.)

(a) I think that "no human understands" what the current busiest $6$-state Busy Beaver $2$-symbol Turing Machine is doing while it prints out $3.5 \times 10^{18267}$ $1$'s before halting.

(b) This does not quite address your 2nd question as you phrased it, but there are several $5$-state quite-Busy Beavers that are believed to loop, but no one can prove they loop, or prove they halt. A list of these irregular Turing Machines is maintained here.

Incidentally, just to illustrate the complexity of Busy-Beaver questions, a $4888$-state Turing Machine has been constructed which halts if and only if there is a counterexamnple to Goldbach's conjecture.

Yedidia, Adam, and Scott Aaronson. "A Relatively Small Turing Machine Whose Behavior Is Independent of Set Theory." arXiv:1605.04343 (2016).

(a) I think that "no human understands" what the current busiest $6$-state Busy Beaver $2$-symbol Turing Machine is doing while it prints out $3.5 \times 10^{18267}$ $1$'s before halting.

(b) This does not quite address your 2nd question as you phrased it, but there are several $5$-state quite-Busy Beavers that are believed to loop, but no one can prove they loop, or prove they halt. A list of these irregular Turing Machines is maintained here.

Incidentally, just to illustrate the complexity of Busy-Beaver questions, a $4888$-state Turing Machine has been constructed which halts if and only if there is a counterexamnple to Goldbach's conjecture.

Yedidia, Adam, and Scott Aaronson. "A Relatively Small Turing Machine Whose Behavior Is Independent of Set Theory." arXiv:1605.04343 (2016). (arXiv Abstract.)

Source Link
Joseph O'Rourke
  • 150.8k
  • 36
  • 358
  • 958

(a) I think that "no human understands" what the current busiest $6$-state Busy Beaver $2$-symbol Turing Machine is doing while it prints out $3.5 \times 10^{18267}$ $1$'s before halting.

(b) This does not quite address your 2nd question as you phrased it, but there are several $5$-state quite-Busy Beavers that are believed to loop, but no one can prove they loop, or prove they halt. A list of these irregular Turing Machines is maintained here.

Incidentally, just to illustrate the complexity of Busy-Beaver questions, a $4888$-state Turing Machine has been constructed which halts if and only if there is a counterexamnple to Goldbach's conjecture.

Yedidia, Adam, and Scott Aaronson. "A Relatively Small Turing Machine Whose Behavior Is Independent of Set Theory." arXiv:1605.04343 (2016).