Semi Infinite Tape Turing Machine: Difference between revisions
Jump to navigation
Jump to search
Added links |
Loader3229 (talk | contribs) No edit summary |
||
| 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. | |||
The tape has a left bound, and the pointer is initially located at the 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. | |||
{| class="wikitable" | {| class="wikitable" | ||
|+ | |+ | ||
Revision as of 05:23, 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 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, 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 | |