Semi Infinite Tape Turing Machine: Difference between revisions
Jump to navigation
Jump to search
Created page and added current champions. |
Added links |
||
| Line 8: | Line 8: | ||
|BBt(2) | |BBt(2) | ||
|≥ 3 | |≥ 3 | ||
|<code>1RB---_1LB0RB</code> | |<code>{{TM|1RB---_1LB0RB}}</code> | ||
|- | |- | ||
|BBt(3) | |BBt(3) | ||
|≥ 12 | |≥ 12 | ||
|<code>0RB0LB_0RC1RC_1LA0LC</code> | |<code>{{TM|0RB0LB_0RC1RC_1LA0LC}}</code> | ||
|- | |- | ||
|BBt(4) | |BBt(4) | ||
|≥ 168 | |≥ 168 | ||
|<code>1RB1LD_1RC0RC_1RD0LA_1LA0RD</code> | |<code>{{TM|1RB1LD_1RC0RC_1RD0LA_1LA0RD}}</code> | ||
|- | |- | ||
|BBt(5) | |BBt(5) | ||
|≥ 4,300 | |≥ 4,300 | ||
|<code>0RB0RC_0RC0RE_0RD1LE_1LA1RD_1LC1RB</code> | |<code>{{TM|0RB0RC_0RC0RE_0RD1LE_1LA1RD_1LC1RB}}</code> | ||
|- | |- | ||
|BBt(2,3) | |BBt(2,3) | ||
|≥ 17 | |≥ 17 | ||
|<code>1RB0RA0RB_2LA2RB1LB</code> | |<code>{{TM|1RB0RA0RB_2LA2RB1LB}}</code> | ||
|- | |- | ||
|BBt(3,3) | |BBt(3,3) | ||
|≥ 10,053 | |≥ 10,053 | ||
|<code>0RB1LA1LB_0RC2LB1RB_1LA2LC2RC</code> | |<code>{{TM|0RB1LA1LB_0RC2LB1RB_1LA2LC2RC}}</code> | ||
|- | |- | ||
|BBt(2,4) | |BBt(2,4) | ||
|≥ 88 | |≥ 88 | ||
|<code>1RB2RB3LA2RA_1LA3LB0RB3RB</code> | |<code>{{TM|1RB2RB3LA2RA_1LA3LB0RB3RB}}</code> | ||
|- | |- | ||
|BBt(2,5) | |BBt(2,5) | ||
|≥ 415 | |≥ 415 | ||
|<code>0RB2LA1LB4RA2RB_1LA1RB3RB4LA1LA</code> | |<code>{{TM|0RB2LA1LB4RA2RB_1LA1RB3RB4LA1LA}}</code> | ||
|- | |- | ||
|BBt(2,6) | |BBt(2,6) | ||
|≥ 1,429 | |≥ 1,429 | ||
|<code>0RB4RB3LA2RA2LB2LA_1LA2RB5RA1RA3RA5RA</code> | |<code>{{TM|0RB4RB3LA2RA2LB2LA_1LA2RB5RA1RA3RA5RA}}</code> | ||
|} | |} | ||
Latest revision as of 10:15, 21 August 2026
The function BBt(n,m) returns the maximum number of right steps a Turing Machine with a semi infinite tape performs before its head leaves the tape. The head starts in the first cell and halting transition is not required.
| Domain | Value | Champion |
|---|---|---|
| BBt(2) | ≥ 3 | |
| BBt(3) | ≥ 12 | |
| BBt(4) | ≥ 168 | |
| BBt(5) | ≥ 4,300 | |
| BBt(2,3) | ≥ 17 | |
| BBt(3,3) | ≥ 10,053 | |
| BBt(2,4) | ≥ 88 | |
| BBt(2,5) | ≥ 415 | |
| BBt(2,6) | ≥ 1,429 | |