Googology Wiki
Googology Wiki
Forums: Index > Googology > Sigma project

We should create a central hub page (in the project namespace probably) for the ongoing project of evaluating Sigma(5). (As a sidenote, I think we should devise a more concise TM notation that doesn't take up, like, 20 lines.) Where is the most up-to-date content on this subject? it's vel time 02:48, September 28, 2014 (UTC)

I think I'd be a good idea to make sections here about proofs. There is no up-to-date content, all proofs are invalid. Wythagoras (talk) 08:27, September 28, 2014 (UTC)


HNR #3

HNR -3 81 billion steps.jpg

Simulated up to 81.8 billion steps. Let me know today if you need to know anything about simulation. Also, there is no reason why the machine's name is 5-state BB (4098), I dunno how it came there. Wythagoras (talk) 10:44, September 28, 2014 (UTC)

Confession (and proofs for 14 HNRs)

On around November of last year, I picked Sigma(5) as the subject of an R&E project for my school. I have proven 14 of the 42 HNRs to loop using Heiner Marxen's AWK script, and on this year I used the result for my graduation paper. The professor suggested to post the results here, which I hesitated to do until now.

The proven HNRs are #02, #05, #06, #08, #11, #14, #18, #20, #21, #22, #25, #27, #30 and #38. Download the results here.

Let me know if you need to know more about this. (I might release it as a blog post.) -- ☁ I want more clouds! ⛅ 11:17, September 28, 2014 (UTC)

Wow, great job! Wythagoras (talk) 11:26, September 28, 2014 (UTC)
This is really awesome! Finally a result about which we can be sure. Just curious, how much time did the evaluation take for all these machines? LittlePeng9 (talk) 11:28, September 28, 2014 (UTC)
Daniel Briggs also proved some machines are non-halting or gave clues to prove some. Machines #02-#13, #15, #17, #18, #21, #23, #25-36, #38 and #39 are proven or given some clues. Also, #01 was almost completely proven (see below). Daniel Briggs and univerz prove some machines are non-halt. So, we left with #16, #19, #24, #37 and #40-42 (43?). Under ten machines are holdouts now. Tetramur (talk) 09:56, May 5, 2019 (UTC)

Observation for HNR#1

I've tried to simulate it for different inputs - it exhibits quite weird behavior for a while, then it either halts or falls to simple loop with states 4-1-3-4-2-3-4-2-3-0-4 and quickly appending ones to the right. The latter situation happens if we have ..._111 at the tape, where head is place at the last 1 and state is 3 or 4.

Also, from my experiments, it halts only when head is placed to the left of all sequences of 1's.

Ikosarakt1 (talk ^ contribs) 04:35, February 2, 2015 (UTC)

This machine also halts if ran on input __1 with initial state 0. Note that at one point machine is in state 0 between some 1's, so observation from your experiments seems to be incorrect. LittlePeng9 (talk) 11:27, February 2, 2015 (UTC)