Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.prolog > #15099

Busy Beaver and Theory Consistency (Was: A logical calculus in nervous activity [McCulloch & Pitts 1943])

Cross-posted to 3 groups.

Show all headers | View raw

Hi,

If you know BB(N), you have a halting decision procedure
for N-turing machines. Since if BB(N) is maximum number
S(N) of steps before halting,

you can just run an arbitrary turing machine, and when
its steps exceeds S(N), you know its not a halting
turing machine.

So knowing BB(N) makes the halting problem decidable.
But the halting problem is not decidable. So there
must be some M maybe where BB(M) has no S(N) , no

maximum. Idea is to construct turing machines that
relate to consistency problems, consistency problems
can be even harder than halting problems, we might

ask for the opposite, does a program never halt.
Since never halt could be interpreted that no
inconsistency is derived. Again knowing BB(N) would

help, since dedidability via S(N) is established both
ways, saying "Yes" to halt, and saying "No" to not halt.
So we can show a reducibility from consistency

to busy beaver, I guess.

Bye

Back to comp.lang.prolog | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

What is analog computing nowadays? (Re: An old Busy Beaver ASIC (Application-Specific Integrated Circuit) (Was: Could AlphaEvolve find the sixth busy beaver ?) Mild Shock <janburse@fastmail.fm> - 2025-12-01 11:25 +0100
  Wake-up call until everybody gets ear-bleeding (Re: What is analog computing nowadays?) Mild Shock <janburse@fastmail.fm> - 2025-12-01 12:01 +0100
    BB(745) is independent of ZFC (Was: Wake-up call until everybody gets ear-bleeding) Mild Shock <janburse@fastmail.fm> - 2025-12-01 12:07 +0100
      Write ZFC formulas on a tape (of a Turing machine) (Re: BB(745) is independent of ZFC ) Mild Shock <janburse@fastmail.fm> - 2025-12-02 17:18 +0100
        Turing machines have neurons (Re: Write ZFC formulas on a tape (of a Turing machine)) Mild Shock <janburse@fastmail.fm> - 2025-12-02 17:19 +0100
          A logical calculus in nervous activity [McCulloch & Pitts 1943] (Re: Turing machines have neurons) Mild Shock <janburse@fastmail.fm> - 2025-12-02 17:20 +0100
            Busy Beaver and Theory Consistency (Was: A logical calculus in nervous activity [McCulloch & Pitts 1943]) Mild Shock <janburse@fastmail.fm> - 2025-12-02 17:39 +0100
            Busy Beaver and Theory Consistency (Was: A logical calculus in nervous activity [McCulloch & Pitts 1943]) Mild Shock <janburse@fastmail.fm> - 2025-12-02 17:43 +0100
              Re: Busy Beaver and Theory Consistency (Was: A logical calculus in nervous activity [McCulloch & Pitts 1943]) Mild Shock <janburse@fastmail.fm> - 2025-12-02 23:18 +0100
  Re: What is analog computing nowadays? (Re: An old Busy Beaver ASIC (Application-Specific Integrated Circuit) (Was: Could AlphaEvolve find the sixth busy beaver ?) Maciej Woźniak <mlwozniak@wp.pl> - 2025-12-01 12:09 +0100
    parallel random-access machine (parallel RAM or PRAM (Was: What is analog computing nowadays?) Mild Shock <janburse@fastmail.fm> - 2025-12-01 12:15 +0100
      Re: parallel random-access machine (parallel RAM or PRAM (Was: What is analog computing nowadays?) Maciej Woźniak <mlwozniak@wp.pl> - 2025-12-01 13:23 +0100
        Nope, you can't, because of the CRCW instuction (Was: parallel random-access machine) Mild Shock <janburse@fastmail.fm> - 2025-12-01 17:12 +0100
          Algorithm introduced in Hogwild! SGD (Niu et al., 2011) (Was: Nope, you can't, because of the CRCW instuction) Mild Shock <janburse@fastmail.fm> - 2025-12-01 17:31 +0100
            PRAMs might be closer to physics: Boltzman machines, etc.. (Was: Algorithm introduced in Hogwild! SGD) Mild Shock <janburse@fastmail.fm> - 2025-12-01 18:02 +0100
          Re: Nope, you can't, because of the CRCW instuction (Was: parallel random-access machine) Maciej Woźniak <mlwozniak@wp.pl> - 2025-12-01 17:59 +0100
            PRAMs might be closer to physics: Boltzman machines, etc.. (Re: Nope, you can't, because of the CRCW instuction) Mild Shock <janburse@fastmail.fm> - 2025-12-01 18:05 +0100
            PRAMs might be closer to physics: Boltzman machines, etc.. (Re: Nope, you can't, because of the CRCW instuction) Mild Shock <janburse@fastmail.fm> - 2025-12-01 18:08 +0100
              Physics more difficult than Rasperry LED cube? (Was: PRAMs might be closer to physics: Boltzman machines, etc..) Mild Shock <janburse@fastmail.fm> - 2025-12-01 18:25 +0100
        Re: parallel random-access machine (parallel RAM or PRAM (Was: What is analog computing nowadays?) Thomas Heger <ttt_heg@web.de> - 2025-12-03 07:17 +0100
          Re: parallel random-access machine (parallel RAM or PRAM (Was: What is  analog computing nowadays?) Python <python@cccp.invalid> - 2025-12-03 06:46 +0000
          Re: parallel random-access machine (parallel RAM or PRAM) Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2025-12-03 08:02 +0100
      Linux kernel's RCU-protected hash tables (Re: Algorithm introduced in Hogwild! SGD (Niu et al., 2011)) Mild Shock <janburse@fastmail.fm> - 2025-12-01 22:26 +0100
        String interning is HashSet and not HashMap (Was: Linux kernel's RCU-protected hash tables) Mild Shock <janburse@fastmail.fm> - 2025-12-01 22:40 +0100
      POINT OF VIEW OF AN ALGORITHM (Re: Algorithm introduced in Hogwild! SGD (Niu et al., 2011)) (Re: parallel random-access machine) Mild Shock <janburse@fastmail.fm> - 2025-12-01 23:12 +0100
        Introduction to AMBA® 4 ACE™ (2011) (Was: POINT OF VIEW OF AN ALGORITHM) Mild Shock <janburse@fastmail.fm> - 2025-12-01 23:37 +0100
          Sputnik Schock: Academia is Disposable [I. J. Good Ultraintelligence] (Was: Introduction to AMBA® 4 ACE™ (2011)) Mild Shock <janburse@fastmail.fm> - 2025-12-01 23:53 +0100

csiph-web