2-symbol, 5-state Turing machine

tetramur · 2019-02-09, 08:24

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

xilman · 2019-02-09, 21:54

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.

R. Gerbicz · 2019-02-09, 22:34

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.

tetramur · 2019-02-10, 04:04

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.

xilman · 2019-02-10, 07:25

Thanks both. I'd heard of the busy beaver problem bu not the S & Sigma notation.

tetramur · 2021-07-11, 13:26

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

2019-02-09, 08:24	#1
tetramur "unknown" Jan 2019 anywhere 10001₂ 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

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
Symbol used for scaling in Fractal Dimensions	stephensmedley	Math	6	2015-01-04 15:12
Turing test result	xilman	Science & Technology	13	2014-06-10 12:26
The cmd Turing test	cmd	cmd	113	2011-02-06 15:46
What is Legendre Symbol? slowing down sr2sieve?	cipher	Software	3	2009-05-20 13:35
Simplest universal Turing machine	davieddy	Science & Technology	4	2007-11-26 04:59

2019-02-09, 22:34	#3
R. Gerbicz "Robert Gerbicz" Oct 2005 Hungary 625₁₆ 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, 07:25	#5
xilman Bamboozled! "𒉺𒌌𒇷𒆷𒀭" May 2003 Down not across 2·5,689 Posts	Thanks both. I'd heard of the busy beaver problem bu not the S & Sigma notation.