Can a Turing machine that can only write only 1 or 0 simulate any algorithm?

I came up with this way to encode an input-output Turing machine, though I'm sure I'm not the only one who has thought of it. It's either well-known already, or perhaps I'm missing something and it doesn't work.

We'll start with a two-state machine, so you only need 1 bit to encode the states 0 and 1. In this case, the 1st 9 bits tell the machine what to do in state 0, and the next 9 bits tell the machine what to do in state 1. We need to tell the machine what to do when it sees a ⊔, 0, or 1. It looks like this, where w is write, m is move and q is state:

0: {⊔ => wmq, 0 => wmq, 1 => wmq}

The machine: 000 110 001, means:

$$ Q = \{0,1\} $$ $$ \Sigma = \{0,1\} $$ $$ \Gamma = \{0,1,⊔\} $$ Delta can be described like this: on ⊔ write 0, move right, stay in state 0. On 0 write 1, move left, stay in state 0. On 1 write 0 move right, and move to state 1. Since state 1 isn't defined, it halts. $$ \text{Start State} = 0 $$ $$ \text{Halt} = 1 $$

If the string had exactly 18 bits, it would never halt because every action is defined and there is no halt state. If the string is larger than 18 bits it will need more bits to encode the states. Up to 48 bits, 2 bits are used so each state definition is 4*3=12 bits long. Up to 120 bits, 3 bits are needed. This follows the formula:

$$3(2^x)(2+x)=L$$

where x is the number of bits used to encode the state and L is the length of the string. (This can't be solved algebraically, so numerical methods will need to be used.)

Some advantages of this encoding is that every string is a valid Turing machine. (This was the whole purpose of me thinking of this.)

Some things it can't do is write a blank. It also can't take any input as it doesn't have a way of knowing which part of the string should be the input. I figure that any finite input could be generated by the first part of the Turing machine, and the machine could then move to the next phase where it acts on the input.

My question is, given the limitations of this encoding, is it Turing complete? Can a machine written this way do everything a Turing machine can?

We could expand upon this model. Rather than just 1 and 0 you could theoretically expand the string alphabet to include more symbols by designating more bits to represent each symbol and expanding each state to account for the additional symbols. So you can write 00,01,10,or 11, thus giving you 4 symbols. One of them could represent a blank and another could be used as a marker.

Edit: my guess is this isn't turning complete because you can't mark any symbols. This could be fixed by using the 4 symbol version.

Can a Turing machine that can only write only 1 or 0 simulate any algorithm?

I came up with this way to encode an input-output Turing machine, though I'm sure I'm not the only one who has thought of it. It's either well-known already, or perhaps I'm missing something and it doesn't work.

We'll start with a two-state machine, so you only need 1 bit to encode the states 0 and 1. In this case, the 1st 9 bits tell the machine what to do in state 0, and the next 9 bits tell the machine what to do in state 1. We need to tell the machine what to do when it sees a ⊔, 0, or 1. It looks like this, where w is write, m is move and q is state:

0: {⊔ => wmq, 0 => wmq, 1 => wmq}

The machine: 000 110 001, means:

$$ Q = \{0,1\} $$ $$ \Sigma = \{0,1\} $$ $$ \Gamma = \{0,1,⊔\} $$ Delta can be described like this: on ⊔ write 0, move right, stay in state 0. On 0 write 1, move left, stay in state 0. On 1 write 0 move right, and move to state 1. Since state 1 isn't defined, it halts. $$ \text{Start State} = 0 $$ $$ \text{Halt} = 1 $$

If the string had exactly 18 bits, it would never halt because every action is defined and there is no halt state. If the string is larger than 18 bits it will need more bits to encode the states. Up to 48 bits, 2 bits are used so each state definition is 4*3=12 bits long. Up to 120 bits, 3 bits are needed. This follows the formula:

$$3(2^x)(2+x)=L$$

where x is the number of bits used to encode the state and L is the length of the string. (This can't be solved algebraically, so numerical methods will need to be used.)

Some advantages of this encoding is that every string is a valid Turing machine. (This was the whole purpose of me thinking of this.)

Some things it can't do is write a blank. It also can't take any input as it doesn't have a way of knowing which part of the string should be the input. I figure that any finite input could be generated by the first part of the Turing machine, and the machine could then move to the next phase where it acts on the input.

My question is, given the limitations of this encoding, is it Turing complete? Can a machine written this way do everything a Turing machine can?

We could expand upon this model. Rather than just 1 and 0 you could theoretically expand the string alphabet to include more symbols by designating more bits to represent each symbol and expanding each state to account for the additional symbols. So you can write 00, 01, 10, or 11, thus giving you 4 symbols. One of them could represent a blank and another could be used as a marker.

Edit: my guess is this isn't Turing complete because you can't mark any symbols. This could be fixed by using the 4 symbol version.

Can a Turing machine that can only write only 1 or 0 simulate any algorithm?

I came up with this way to encode an input-output Turing machine, though I'm sure I'm not the only one who has thought of it. It's either well-known already, or perhaps I'm missing something and it doesn't work.

We'll start with a two-state machine, so you only need 1 bit to encode the states 0 and 1. In this case, the 1st 9 bits tell the machine what to do in state 0, and the next 9 bits tell the machine what to do in state 1. We need to tell the machine what to do when it sees a ⊔, 0, or 1. It looks like this, where w is write, m is move and q is state:

0: {⊔ => wmq, 0 => wmq, 1 => wmq}

The machine: 000 110 001, means:

$$ Q = \{0,1\} $$ $$ \Sigma = \{0,1\} $$ $$ \Gamma = \{0,1,⊔\} $$ Delta can be described like this: on ⊔ write 0, move right, stay in state 0. On 0 write 1, move left, stay in state 0. On 1 write 0 move right, and move to state 1. Since state 1 isn't defined, it halts. $$ \text{Start State} = 0 $$ $$ \text{Halt} = 1 $$

If the string had exactly 18 bits, it would never halt because every action is defined and there is no halt state. If the string is larger than 18 bits it will need more bits to encode the states. Up to 48 bits, 2 bits are used so each state definition is 4*3=12 bits long. Up to 120 bits, 3 bits are needed. This follows the formula:

$$3(2^x)(2+x)=L$$

where x is the number of bits used to encode the state and L is the length of the string. (This can't be solved algebraically, so numerical methods will need to be used.)

Some advantages of this encoding is that every string is a valid Turing machine. (This was the whole purpose of me thinking of this.)

Some things it can't do is write a blank. It also can't take any input as it doesn't have a way of knowing which part of the string should be the input. I figure that any finite input could be generated by the first part of the Turing machine, and the machine could then move to the next phase where it acts on the input.

My question is, given the limitations of this encoding, is it Turing complete? Can a machine written this way do everything a Turing machine can?

We could expand upon this model. Rather than just 1 and 0 you could theoretically expand the string alphabet to include more symbols by designating more bits to represent each symbol and expanding each state to account for the additional symbols. So you can write 00,01,10,or 11, thus giving you 4 symbols. One of them could represent a blank and another could be used as a marker.

Can a Turing machine that can only write only 1 or 0 simulate any algorithm?

I came up with this way to encode an input-output Turing machine, though I'm sure I'm not the only one who has thought of it. It's either well-known already, or perhaps I'm missing something and it doesn't work.

We'll start with a two-state machine, so you only need 1 bit to encode the states 0 and 1. In this case, the 1st 9 bits tell the machine what to do in state 0, and the next 9 bits tell the machine what to do in state 1. We need to tell the machine what to do when it sees a ⊔, 0, or 1. It looks like this, where w is write, m is move and q is state:

0: {⊔ => wmq, 0 => wmq, 1 => wmq}

The machine: 000 110 001, means:

$$ Q = \{0,1\} $$ $$ \Sigma = \{0,1\} $$ $$ \Gamma = \{0,1,⊔\} $$ Delta can be described like this: on ⊔ write 0, move right, stay in state 0. On 0 write 1, move left, stay in state 0. On 1 write 0 move right, and move to state 1. Since state 1 isn't defined, it halts. $$ \text{Start State} = 0 $$ $$ \text{Halt} = 1 $$

If the string had exactly 18 bits, it would never halt because every action is defined and there is no halt state. If the string is larger than 18 bits it will need more bits to encode the states. Up to 48 bits, 2 bits are used so each state definition is 4*3=12 bits long. Up to 120 bits, 3 bits are needed. This follows the formula:

$$3(2^x)(2+x)=L$$

where x is the number of bits used to encode the state and L is the length of the string. (This can't be solved algebraically, so numerical methods will need to be used.)

Some advantages of this encoding is that every string is a valid Turing machine. (This was the whole purpose of me thinking of this.)

Some things it can't do is write a blank. It also can't take any input as it doesn't have a way of knowing which part of the string should be the input. I figure that any finite input could be generated by the first part of the Turing machine, and the machine could then move to the next phase where it acts on the input.

My question is, given the limitations of this encoding, is it Turing complete? Can a machine written this way do everything a Turing machine can?

We could expand upon this model. Rather than just 1 and 0 you could theoretically expand the string alphabet to include more symbols by designating more bits to represent each symbol and expanding each state to account for the additional symbols. So you can write 00,01,10,or 11, thus giving you 4 symbols. One of them could represent a blank and another could be used as a marker.

Edit: my guess is this isn't turning complete because you can't mark any symbols. This could be fixed by using the 4 symbol version.

Can a Turing machine that can only write only 1 or 0 simulate any algorithm?

I came up with this way to encode an input-output Turing machine, though I'm sure I'm not the only one who has thought of it. It's either well-known already, or perhaps I'm missing something and it doesn't work.

We'll start with a two-state machine, so you only need 1 bit to encode the states 0 and 1. In this case, the 1st 9 bits tell the machine what to do in state 0, and the next 9 bits tell the machine what to do in state 1. We need to tell the machine what to do when it sees a ⊔, 0, or 1. It looks like this, where w is write, m is move and q is state:

0: {⊔ => wmq, 0 => wmq, 1 => wmq}

The machine: 000 110 001, means:

$$ Q = \{0,1\} $$ $$ \Sigma = \{0,1\} $$ $$ \Gamma = \{0,1,⊔\} $$ Delta can be described like this: on ⊔ write 0, move right, stay in state 0. On 0 write 1, move left, stay in state 0. On 1 write 0 move right, and move to state 1. Since state 1 isn't defined, it halts. $$ \text{Start State} = 0 $$ $$ \text{Halt} = 1 $$

If the string had exactly 18 bits, it would never halt because every action is defined and there is no halt state. If the string is larger than 18 bits it will need more bits to encode the states. Up to 48 bits, 2 bits are used so each state definition is 4*3=12 bits long. Up to 120 bits, 3 bits are needed. This follows the formula:

$$3(2^x)(2+x)=L$$

where x is the number of bits used to encode the state and L is the length of the string. (This can't be solved algebraically, so numerical methods will need to be used.)

Some advantages of this encoding is that every string is a valid Turing machine. (This was the whole purpose of me thinking of this.)

Some things it can't do is write a blank. It also can't take any input as it doesn't have a way of knowing which part of the string should be the input. I figure that any finite input could be generated by the first part of the Turing machine, and the machine could then move to the next phase where it acts on the input.

My question is, given the limitations of this encoding, is it Turing complete? Can a machine written this way do everything a Turing machine can?

We could expand upon this model. Rather than just 1 and 0 you could theoretically expand the string alphabet to include more symbols but designating more bits to represent each symbol and expanding each state to account for the additional symbols. So you can write 00,01,10,or 11.

Can a Turing machine that can only write only 1 or 0 simulate any algorithm?

I came up with this way to encode an input-output Turing machine, though I'm sure I'm not the only one who has thought of it. It's either well-known already, or perhaps I'm missing something and it doesn't work.

We'll start with a two-state machine, so you only need 1 bit to encode the states 0 and 1. In this case, the 1st 9 bits tell the machine what to do in state 0, and the next 9 bits tell the machine what to do in state 1. We need to tell the machine what to do when it sees a ⊔, 0, or 1. It looks like this, where w is write, m is move and q is state:

0: {⊔ => wmq, 0 => wmq, 1 => wmq}

The machine: 000 110 001, means:

$$ Q = \{0,1\} $$ $$ \Sigma = \{0,1\} $$ $$ \Gamma = \{0,1,⊔\} $$ Delta can be described like this: on ⊔ write 0, move right, stay in state 0. On 0 write 1, move left, stay in state 0. On 1 write 0 move right, and move to state 1. Since state 1 isn't defined, it halts. $$ \text{Start State} = 0 $$ $$ \text{Halt} = 1 $$

If the string had exactly 18 bits, it would never halt because every action is defined and there is no halt state. If the string is larger than 18 bits it will need more bits to encode the states. Up to 48 bits, 2 bits are used so each state definition is 4*3=12 bits long. Up to 120 bits, 3 bits are needed. This follows the formula:

$$3(2^x)(2+x)=L$$

where x is the number of bits used to encode the state and L is the length of the string. (This can't be solved algebraically, so numerical methods will need to be used.)

Some advantages of this encoding is that every string is a valid Turing machine. (This was the whole purpose of me thinking of this.)

Some things it can't do is write a blank. It also can't take any input as it doesn't have a way of knowing which part of the string should be the input. I figure that any finite input could be generated by the first part of the Turing machine, and the machine could then move to the next phase where it acts on the input.

My question is, given the limitations of this encoding, is it Turing complete? Can a machine written this way do everything a Turing machine can?

We could expand upon this model. Rather than just 1 and 0 you could theoretically expand the string alphabet to include more symbols by designating more bits to represent each symbol and expanding each state to account for the additional symbols. So you can write 00,01,10,or 11, thus giving you 4 symbols. One of them could represent a blank and another could be used as a marker.