mersenneforum.org  

Go Back   mersenneforum.org > Math Stuff > Computer Science & Computational Number Theory

Reply
 
Thread Tools
Old 2019-02-09, 08:24   #1
tetramur
 
"unknown"
Jan 2019
anywhere

1710 Posts
Default 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
tetramur is offline   Reply With Quote
Old 2019-02-09, 21:54   #2
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

22·3·11·83 Posts
Default

Quote:
Originally Posted by tetramur View Post
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
xilman is offline   Reply With Quote
Old 2019-02-09, 22:34   #3
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

149410 Posts
Default

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.
R. Gerbicz is offline   Reply With Quote
Old 2019-02-10, 04:04   #4
tetramur
 
"unknown"
Jan 2019
anywhere

17 Posts
Default

Quote:
Originally Posted by xilman View Post
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.
tetramur is offline   Reply With Quote
Old 2019-02-10, 07:25   #5
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

22×3×11×83 Posts
Default

Thanks both. I'd heard of the busy beaver problem bu not the S & Sigma notation.
xilman is offline   Reply With Quote
Old 2021-07-11, 13:26   #6
tetramur
 
"unknown"
Jan 2019
anywhere

17 Posts
Default

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
tetramur is offline   Reply With Quote
Reply

Thread Tools


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

All times are UTC. The time now is 01:31.


Sat Oct 23 01:31:07 UTC 2021 up 91 days, 20 hrs, 0 users, load averages: 1.08, 1.08, 1.10

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

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.