Semi Infinite Tape Turing Machine: Difference between revisions
Jump to navigation
Jump to search
Loader3229 (talk | contribs) No edit summary |
Loader3229 (talk | contribs) No edit summary |
||
| (9 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
A semi infinite tape Turing Machine is a Turing Machine that use a tape that only one direction is infinite instead. | A semi infinite tape Turing Machine is a Turing Machine that use a tape that only one direction is infinite instead. | ||
The tape has a left bound, and the pointer is initially located at the cell right to the bound. | The tape has a left bound, and the pointer is initially located at the first cell right to the bound. | ||
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. | 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. | ||
If the machine's head stay on the first cell when the head is on the first cell and try to go left, the function BB_SI(n,m) is maximum number of steps taken by a halting n-state, m-symbol semi infinite tape Turing Machine starting from a blank (all 0) semi-infinite tape. | If the machine's head stay on the first cell when the head is on the first cell and try to go left (like [https://morphett.info/turing/turing.html] does), the function BB_SI(n,m) is maximum number of steps taken by a halting n-state, m-symbol semi infinite tape Turing Machine starting from a blank (all 0) semi-infinite tape. | ||
{| class="wikitable" | {| class="wikitable" | ||
| Line 47: | Line 47: | ||
|≥ 1,429 | |≥ 1,429 | ||
|<code>{{TM|0RB4RB3LA2RA2LB2LA_1LA2RB5RA1RA3RA5RA}}</code> | |<code>{{TM|0RB4RB3LA2RA2LB2LA_1LA2RB5RA1RA3RA5RA}}</code> | ||
|- | |||
|BB_SI(1) | |||
|≥ 2 | |||
|<code>{{TM|1LA1RZ}}</code> | |||
|- | |||
|BB_SI(2) | |||
|≥ 10 | |||
|<code>{{TM|1LB1RZ_1LA0RB}}</code> | |||
|- | |||
|BB_SI(3) | |||
|≥ 30 | |||
|<code>{{TM|1RC0LA_1LA0RA_1RB1RZ}}</code> | |||
|- | |||
|BB_SI(1,3) | |||
|≥ 4 | |||
|<code>{{TM|1LA2RA1RZ}}</code> | |||
|- | |||
|BB_SI(2,3) | |||
|≥ 48 | |||
|<code>{{TM|2LA2LB1LA_1RB1RZ0RA}}</code> | |||
|- | |||
|BB_SI(1,4) | |||
|≥ 5 | |||
|<code>{{TM|1LA2RA3LA1RZ}}</code> | |||
|- | |||
|BB_SI(1,5) | |||
|≥ 9 | |||
|<code>{{TM|1LA2RA3LA4RA1RZ}}</code> | |||
|} | |} | ||
[[Category:Functions]] | [[Category:Functions]] | ||
Latest revision as of 06:46, 25 October 2026
A semi infinite tape Turing Machine is a Turing Machine that use a tape that only one direction is infinite instead. The tape has a left bound, and the pointer is initially located at the first cell right to the bound.
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.
If the machine's head stay on the first cell when the head is on the first cell and try to go left (like [1] does), the function BB_SI(n,m) is maximum number of steps taken by a halting n-state, m-symbol semi infinite tape Turing Machine starting from a blank (all 0) semi-infinite tape.
| 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 | |
| BB_SI(1) | ≥ 2 | |
| BB_SI(2) | ≥ 10 | |
| BB_SI(3) | ≥ 30 | |
| BB_SI(1,3) | ≥ 4 | |
| BB_SI(2,3) | ≥ 48 | |
| BB_SI(1,4) | ≥ 5 | |
| BB_SI(1,5) | ≥ 9 | |