- #1

- 20

- 0

Define a TM that for every n duplicates a string of the form 1^n, creating 1^n 0 1^n. Does the machine calculate any function?

We're using the notion that a string of n+1 n's represents n.

Basically, I've surmised that I need a machine that does the following:

n= 0 input string = 010 output string --> 0000 **note the 0s to the left/right go on infinitely.

n=1 input string = 0110 output string --> 01010

n=2 input string = 01110 output string --> 0110110

etc.

I really have no idea how I'm supposed to keep track of the number of 1s encountered.

The machine must start at the left of the string. We're defining the machines in terms of quadruples, q_i 0/1 L/R/0/1 q_f (e.g. q1 0 1 q2 means state q1 read 0 write 1 enter state q2).

Also, I'm supposed to prove that there are infinitely many different TMs that calculate TM computable functions.

I get the idea in terms of how I could always append some useless quadruple to the instruction set of the TM, thus always ensuring that I have a different TM. I have no idea how to formalize this, though.