20190209, 08:24  #1 
"unknown"
Jan 2019
anywhere
21_{8} Posts 
2symbol, 5state 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 
20190209, 21:54  #2 
Bamboozled!
"πΊππ·π·π"
May 2003
Down not across
37·293 Posts 
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 20190209 at 21:54 
20190209, 22:34  #3 
"Robert Gerbicz"
Oct 2005
Hungary
1489_{10} 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. 
20190210, 04:04  #4  
"unknown"
Jan 2019
anywhere
11_{16} Posts 
Quote:
Sigma (2,5)  the highest number of nonzero 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. 

20190210, 07:25  #5 
Bamboozled!
"πΊππ·π·π"
May 2003
Down not across
37×293 Posts 
Thanks both. I'd heard of the busy beaver problem bu not the S & Sigma notation.

20210711, 13:26  #6 
"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 20210711 at 13:33 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Symbol used for scaling in Fractal Dimensions  stephensmedley  Math  6  20150104 15:12 
Turing test result  xilman  Science & Technology  13  20140610 12:26 
The cmd Turing test  cmd  cmd  113  20110206 15:46 
What is Legendre Symbol? slowing down sr2sieve?  cipher  Software  3  20090520 13:35 
Simplest universal Turing machine  davieddy  Science & Technology  4  20071126 04:59 