(Can someone change the name of the blog post? I made a typo)
What are they?[]
Not Turing Machines are networks of computers.
Each computer has 3 states (the + state, the - state, and the 0 state), an infinite tape of cells (which can store any integer, which starts at 0), and a pointer. Each computer can either be active or inactive. There is also a group of computers (which can be made up of one or more computers) that are active at the start.
When a computer is active, it can be on one of it's 3 states, depending on the integer stored by the cell that the pointer is on:
- If the integer stored by the cell that the pointer is on is positive, the computer will be in the + state.
- If the integer stored by the cell that the pointer is on is negative, the computer will be in the - state.
- Else, the computer will be in the 0 state.
When a computer is active, that computer has to do 3 actions, which depend on the state that the computer is in:
- Increasing (+), decreasing (-), or doing nothing (*) to the integer stored by the cell that the pointer is on
- Moving the pointer to the left (-), to the right (+), or keeping its position the same (*)
- Becoming inactive (halt) or making some computers active and then becoming inactive ([list of computers that are made active])
The last computers that become inactive will output the integer stored by the cell that their pointers were on before becoming inactive. NBB(x) (NBB() = Not Busy Beaver function) is the largest possible output of a Not Turing Machine with x computers.
Values[]
We can prove that NBB(1) = 2. Here is the proof:
At the start, the pointer will point at a cell that stores 0, so the computer goes into the 0 state. It can change the number to -1 or +1, or keep it the same. Then, it can move the pointer and become inactive or become active again. So we have 2 cases:
- Case 1: The computer becomes inactive when it's in the 0 state. The best option would be to increase the number that the cell that the pointer is on is storing and not moving the pointer. The output would be 1.
- Case 2: [WIP]