Computation of Rado-function

版本 1.0.2 (6.7 KB) 作者: Thomas
Recursive computation of the "uncomputable" Rado-function.
8.0 次下载
更新时间 2020/1/26

查看许可证

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.

引用格式

Thomas (2024). Computation of Rado-function (https://www.mathworks.com/matlabcentral/fileexchange/74030-computation-of-rado-function), MATLAB Central File Exchange. 检索来源 .

MATLAB 版本兼容性
创建方式 R2019a
兼容任何版本
平台兼容性
Windows macOS Linux
类别
Help CenterMATLAB Answers 中查找有关 Simultaneous and Synchronized Operations 的更多信息

Community Treasure Hunt

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

Start Hunting!
版本 已发布 发行说明
1.0.2

The function "rado(noStates, noLetters, tape_length, outputmin)" was not yet uploaded.

1.0.1

the main function "rado(noStates, noLetters, tape_length, outputmin)" was missing in the first upload

1.0.0