mersenneforum.org

mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Computer Science & Computational Number Theory (https://www.mersenneforum.org/forumdisplay.php?f=116)
-   -   2-symbol, 5-state Turing machine (https://www.mersenneforum.org/showthread.php?t=24061)

tetramur 2019-02-09 08:24

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

xilman 2019-02-09 21:54

[QUOTE=tetramur;508101]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[/QUOTE]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 [url]https://oeis.org/A028444[/url], 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=xilman;508149]Could you expand on this please? At present I don't know what S (2,5) and Sigma (2,5) mean.[/QUOTE]
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


All times are UTC. The time now is 08:21.

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.