mersenneforum.org 2-symbol, 5-state Turing machine
 Register FAQ Search Today's Posts Mark Forums Read

 2019-02-09, 08:24 #1 tetramur   "unknown" Jan 2019 anywhere 1710 Posts 2-symbol, 5-state Turing machine Does anyone have the current records for Sigma (2,5) & S (2,5)? I want to obtain full decimal expansion for they... At the moment we have: Sigma (2,5) > 1.7 * 10^352 S (2,5) > 1.9 * 10^704
2019-02-09, 21:54   #2
xilman
Bamboozled!

"πΊππ·π·π­"
May 2003
Down not across

101010011101002 Posts

Quote:
 Originally Posted by tetramur Does anyone have the current records for Sigma (2,5) & S (2,5)? I want to obtain full decimal expansion for they... At the moment we have: Sigma (2,5) > 1.7 * 10^352 S (2,5) > 1.9 * 10^704
Could you expand on this please? At present I don't know what S (2,5) and Sigma (2,5) mean.

Last fiddled with by xilman on 2019-02-09 at 21:54

 2019-02-09, 22:34 #3 R. Gerbicz     "Robert Gerbicz" Oct 2005 Hungary 1,489 Posts See https://oeis.org/A028444, this is a quite famous sequence, though it is giving much smaller lower bounds (check the sequences in the comment). You are attacking very hard problems.
2019-02-10, 04:04   #4
tetramur

"unknown"
Jan 2019
anywhere

17 Posts

Quote:
 Originally Posted by xilman Could you expand on this please? At present I don't know what S (2,5) and Sigma (2,5) mean.
Of course!
Sigma (2,5) - the highest number of non-zero symbols that Turing machine with 2 symbols and 5 states can print.
S (2,5) - the same definition, but in this time we have the highest number of steps.

 2019-02-10, 07:25 #5 xilman Bamboozled!     "πΊππ·π·π­" May 2003 Down not across 22×11×13×19 Posts Thanks both. I'd heard of the busy beaver problem bu not the S & Sigma notation.
 2021-07-11, 13:26 #6 tetramur   "unknown" Jan 2019 anywhere 17 Posts Actually, several months ago I got precise decimal expansion of both numbers via Haskell "hindu" program. I write them below (broken into lines 50 digits each): Ξ£(2,5) β₯ 178083742761148271794091655011100943474589539255242 \01057539295445498984038114371347629489952511050406 \04300658539050730359421281353664516290407557557220 \69878657458339321171570193549665230376935273282384 \15191227013720305505859015489988006341788486725058 \46129050880896047805123102410645674244611381449872 \05215702722941274887160306180600286029831809670717 \13 ~ 1.78 * 10^352 S(2,5) β₯ 190282916614912976971178894914993423154449611310999 \55608252209158039802498817987126397677115261703932 \46874220736747275560337653658152498141492793244408 \68411015096012479322048511264818866734215557976327 \24586053098707032286213426062000275084793122693330 \52154491789214302942545113315933805795655964622502 \51756508571695291245917982611765119501158512949469 \89732867385018429962423103022237243715421350332113 \68778778966065868513960191851598348793870006009550 \87580733165363673666786112829270952177017805116456 \27872254635842924918819451697802281836597207382658 \83100157248705840429589508654425831370619075419828 \78261306211149968318903489501309660869300105000568 \50366820482398263216481505169529870792418673460493 \4655 ~ 1.90 * 10^704 Last fiddled with by tetramur on 2021-07-11 at 13:33

 Similar Threads Thread Thread Starter Forum Replies Last Post stephensmedley Math 6 2015-01-04 15:12 xilman Science & Technology 13 2014-06-10 12:26 cmd cmd 113 2011-02-06 15:46 cipher Software 3 2009-05-20 13:35 davieddy Science & Technology 4 2007-11-26 04:59

All times are UTC. The time now is 20:33.

Tue Sep 28 20:33:29 UTC 2021 up 67 days, 15:02, 3 users, load averages: 1.13, 1.22, 1.39

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.