image thumbnail

Computation of Rado-function

version 1.0.2 (6.69 KB) by Thomas
Recursive computation of the "uncomputable" Rado-function.

7 Downloads

Updated 26 Jan 2020

View License

Recursive computation of the Rado-function. Mainly following: Heiner Marxen, Jürgen Buntrock: Attacking the Busy Beaver 5. In: Bulletin of the EATCS. 40, Februar 1990, ISSN 0252-9742, S. 247–251.
if the database toolbox is not available, simply comment out all related code lines.

rado(noStates, noLetters, tape_length, outputmin)
noStates = number of possible states of touring machine
noLetters = number of letters used by touring machine
tape_length is maximal length of tape
outputmin is the min number of ones from which on a touring machine is considered 'interesting'. Touring machines with smaller numbers of written ones are ignored in the result list.

examples about how to use:
>> rado(2,2,200,4)
terminated : [1 0 2 1 -1;2 0 1 1 1;1 1 2 1 1;2 1 Inf 1 -1] , sigma = 4 , n = 6
Elapsed time is 0.264846 seconds.
>> rado(2,2,200,3)
terminated : [1 0 2 1 -1;2 0 1 1 1;1 1 1 1 1;2 1 Inf 1 -1] , sigma = 3 , n = 5
terminated : [1 0 2 1 -1;2 0 1 1 1;1 1 2 0 1;2 1 Inf 1 -1] , sigma = 3 , n = 6
terminated : [1 0 2 1 -1;2 0 1 1 1;1 1 2 1 1;2 1 Inf 1 -1] , sigma = 4 , n = 6
terminated : [1 0 2 1 -1;2 0 2 1 1;1 1 Inf 1 -1;2 1 1 1 1] , sigma = 3 , n = 6
Elapsed time is 0.088483 seconds.
>> rado(3,2,200,8)
Elapsed time is 3.009735 seconds.
>> rado(2,3,200,8)
terminated : [1 0 2 1 -1;2 0 1 2 1;1 1 2 0 1;2 1 2 1 -1;1 2 Inf 1 -1;2 2 1 1 -1] , sigma = 8 , n = 29
terminated : [1 0 2 1 -1;2 0 1 2 1;1 1 2 2 1;2 1 2 2 -1;1 2 Inf 1 -1;2 2 2 1 1] , sigma = 9 , n = 38
Elapsed time is 2.358087 seconds.
>> rado(4,2,200,10)
terminated : [1 0 2 1 -1;2 0 1 1 1;3 0 Inf 1 -1;4 0 4 1 -1;1 1 2 1 1;2 1 3 0 1;3 1 4 1 1;4 1 1 0 -1] , sigma = 13 , n = 107
terminated : [1 0 2 1 -1;2 0 1 1 1;3 0 Inf 1 -1;4 0 4 1 1;1 1 3 0 -1;2 1 1 1 -1;3 1 4 1 -1;4 1 2 0 1] , sigma = 13 , n = 96
terminated : [1 0 2 1 -1;2 0 1 1 1;3 0 2 1 1;4 0 Inf 1 -1;1 1 3 0 1;2 1 4 1 -1;3 1 2 1 -1;4 1 3 1 -1] , sigma = 10 , n = 40
terminated : [1 0 2 1 -1;2 0 3 0 -1;3 0 3 1 1;4 0 2 0 -1;1 1 Inf 1 -1;2 1 4 0 -1;3 1 4 1 1;4 1 1 1 1] , sigma = 10 , n = 47
terminated : [1 0 2 1 -1;2 0 3 0 -1;3 0 4 1 -1;4 0 1 1 1;1 1 4 1 1;2 1 2 1 -1;3 1 Inf 1 -1;4 1 4 0 1] , sigma = 10 , n = 40
terminated : [1 0 2 1 -1;2 0 3 1 -1;3 0 1 1 1;4 0 3 1 -1;1 1 4 1 1;2 1 Inf 1 -1;3 1 1 0 -1;4 1 4 0 1] , sigma = 11 , n = 59
terminated : [1 0 2 1 -1;2 0 3 1 -1;3 0 2 1 1;4 0 Inf 1 -1;1 1 1 0 1;2 1 2 1 1;3 1 4 1 -1;4 1 1 0 -1] , sigma = 12 , n = 63
terminated : [1 0 2 1 -1;2 0 3 1 -1;3 0 4 1 1;4 0 2 1 1;1 1 1 0 1;2 1 Inf 1 -1;3 1 1 0 -1;4 1 4 1 1] , sigma = 11 , n = 43
terminated : [1 0 2 1 -1;2 0 3 1 1;3 0 Inf 1 -1;4 0 3 1 1;1 1 4 1 1;2 1 3 0 -1;3 1 1 1 -1;4 1 1 1 1] , sigma = 10 , n = 51
terminated : [1 0 2 1 -1;2 0 3 1 1;3 0 4 1 -1;4 0 Inf 1 -1;1 1 2 0 1;2 1 1 1 1;3 1 1 1 1;4 1 3 1 -1] , sigma = 10 , n = 30
terminated : [1 0 2 1 -1;2 0 3 1 1;3 0 4 1 1;4 0 Inf 1 -1;1 1 3 1 1;2 1 4 0 -1;3 1 1 1 1;4 1 1 1 -1] , sigma = 10 , n = 45
terminated : [1 0 2 1 -1;2 0 3 1 1;3 0 1 1 -1;4 0 Inf 1 -1;1 1 2 1 1;2 1 4 1 -1;3 1 1 1 1;4 1 3 0 -1] , sigma = 12 , n = 53
terminated : [1 0 2 1 -1;2 0 3 1 1;3 0 1 0 -1;4 0 3 1 -1;1 1 3 1 -1;2 1 4 0 1;3 1 2 1 1;4 1 Inf 1 -1] , sigma = 10 , n = 63
terminated : [1 0 2 1 -1;2 0 3 1 1;3 0 1 1 -1;4 0 Inf 1 -1;1 1 4 0 -1;2 1 1 0 1;3 1 2 1 1;4 1 3 0 -1] , sigma = 12 , n = 78
terminated : [1 0 2 1 -1;2 0 3 1 1;3 0 4 1 -1;4 0 1 0 -1;1 1 Inf 1 -1;2 1 2 0 1;3 1 2 1 1;4 1 4 1 -1] , sigma = 10 , n = 32
terminated : [1 0 2 1 -1;2 0 3 1 1;3 0 4 0 1;4 0 1 1 1;1 1 4 0 -1;2 1 1 1 -1;3 1 3 1 1;4 1 Inf 1 -1] , sigma = 10 , n = 30
terminated : [1 0 2 1 -1;2 0 3 1 1;3 0 3 0 -1;4 0 4 1 -1;1 1 Inf 1 -1;2 1 1 1 -1;3 1 4 0 1;4 1 2 0 1] , sigma = 10 , n = 68
terminated : [1 0 2 1 -1;2 0 3 1 1;3 0 1 1 -1;4 0 1 1 -1;1 1 3 0 -1;2 1 Inf 1 -1;3 1 4 1 1;4 1 2 1 1] , sigma = 11 , n = 46
Elapsed time is 522.186494 seconds.

I used: David Fass (2020). CARTPROD: Cartesian product of multiple sets (https://www.mathworks.com/matlabcentral/fileexchange/5475-cartprod-cartesian-product-of-multiple-sets), MATLAB Central File Exchange. Retrieved January 26, 2020.
and a modification of: Daniel Drucker (2020). Turing machine emulator (https://www.mathworks.com/matlabcentral/fileexchange/23006-turing-machine-emulator), MATLAB Central File Exchange. Retrieved January 26, 2020.

Cite As

Thomas (2021). Computation of Rado-function (https://www.mathworks.com/matlabcentral/fileexchange/74030-computation-of-rado-function), MATLAB Central File Exchange. Retrieved .

MATLAB Release Compatibility
Created with R2019a
Compatible with any release
Platform Compatibility
Windows macOS Linux

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!