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 #3Simulated 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.
- 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.