Oracle TMs: Difference between revisions
Jump to navigation
Jump to search
Fixed Table |
Loader3229 (talk | contribs) No edit summary |
||
| (3 intermediate revisions by 2 users not shown) | |||
| Line 1: | Line 1: | ||
This is a work in progress. Oracle Turing Machines are like normal TMs but have 3 extra states. Those are ask, yes and no. When it reaches an ask state, it counts the number of 1s on the tape (which we will call y) and simulates TM#y if it halts go to the yes state and if not go to the no state. | This is a work in progress. Oracle Turing Machines are like normal TMs but have 3 extra states. Those are ask, yes and no. When it reaches an ask state, it counts the number of 1s on the tape (which we will call y) and simulates TM#y if it halts go to the yes state and if not go to the no state. Looking [https://googology.fandom.com/wiki/User:Wythagoras/Rado's_sigma_function/Oracle_TMs/Numbering_for_TMs here] can also be useful for explaining. | ||
'''Champions''' | '''Champions'''<ref>https://googology.fandom.com/wiki/User:Wythagoras/Rado%27s_sigma_function/Oracle_TMs</ref> | ||
{| class="wikitable" | {| class="wikitable" | ||
|+ | |+ | ||
| Line 18: | Line 18: | ||
| | | | ||
| | | | ||
|} | |||
'''Number to TM''' | |||
{| class="wikitable" | |||
|+ | |||
!Number | |||
!TM | |||
|- | |||
|0 | |||
|The 0-state TM. It will halt. | |||
|- | |||
|1 | |||
|{{TM|0LA0LA}} | |||
|- | |||
|2 | |||
|{{TM|1LA0LA}} | |||
|- | |||
|3 | |||
|{{TM|0RA0LA}} | |||
|- | |||
|4 | |||
|{{TM|1RA0LA}} | |||
|- | |||
|5 | |||
|{{TM|0LZ0LA}} | |||
|- | |||
|6 | |||
|{{TM|1LZ0LA}} | |||
|- | |||
|7 | |||
|{{TM|0RZ0LA}} | |||
|- | |||
|8 | |||
|{{TM|1RZ0LA}} | |||
|- | |||
|9 | |||
|{{TM|0LA1LA}} | |||
|- | |||
|10 | |||
|{{TM|1LA1LA}} | |||
|- | |||
|16 | |||
|{{TM|1RZ1LA}} | |||
|- | |||
|64 | |||
|{{TM|1RZ1RZ}} | |||
|- | |||
|65 | |||
|{{TM|0LA0LA_0LA0LA}} | |||
|- | |||
|66 | |||
|{{TM|1LA0LA_0LA0LA}} | |||
|- | |||
|67 | |||
|{{TM|0RA0LA_0LA0LA}} | |||
|- | |||
|69 | |||
|{{TM|0LB0LA_0LA0LA}} | |||
|- | |||
|71 | |||
|{{TM|0RB0LA_0LA0LA}} | |||
|- | |||
|73 | |||
|{{TM|0LZ0LA_0LA0LA}} | |||
|} | |} | ||
Latest revision as of 16:11, 1 November 2026
This is a work in progress. Oracle Turing Machines are like normal TMs but have 3 extra states. Those are ask, yes and no. When it reaches an ask state, it counts the number of 1s on the tape (which we will call y) and simulates TM#y if it halts go to the yes state and if not go to the no state. Looking here can also be useful for explaining.
Champions[1]
| Sigma | Value for Sigma | S | Value for S |
|---|---|---|---|
| Sigma2 (1) | >= 10 | S2 (1) | >= 22 |
| Sigma2 (2) | >= 445 but could be above 25,000 |
Number to TM
| Number | TM |
|---|---|
| 0 | The 0-state TM. It will halt. |
| 1 | 0LA0LA (bbch)
|
| 2 | 1LA0LA (bbch)
|
| 3 | 0RA0LA (bbch)
|
| 4 | 1RA0LA (bbch)
|
| 5 | 0LZ0LA (bbch)
|
| 6 | 1LZ0LA (bbch)
|
| 7 | 0RZ0LA (bbch)
|
| 8 | 1RZ0LA (bbch)
|
| 9 | 0LA1LA (bbch)
|
| 10 | 1LA1LA (bbch)
|
| 16 | 1RZ1LA (bbch)
|
| 64 | 1RZ1RZ (bbch)
|
| 65 | 0LA0LA_0LA0LA (bbch)
|
| 66 | 1LA0LA_0LA0LA (bbch)
|
| 67 | 0RA0LA_0LA0LA (bbch)
|
| 69 | 0LB0LA_0LA0LA (bbch)
|
| 71 | 0RB0LA_0LA0LA (bbch)
|
| 73 | 0LZ0LA_0LA0LA (bbch)
|