Clueless on TM Calculations & Proving Infinitude

[calcnd]

I'm so very confused on how to go about these problems.

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.

 

[Hurkyl]

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

You don't have to count them, you could solve the problem in another fashion.

(except for small quantities, I think a human would usually solve similar problems without counting)


But if you want to count, can't you just write the result down someplace on the tape?

 

[calcnd]

Yes, but I need to be able to go back and fourth keeping track of what I encounter.

So, for example, if the input string is 1111 I need to get an output of 1110111.

But I can't "count" the three ones and then tell it to write three, as the machine can't remember what it's encountered other than its current state, no?

It's got to go back and fourth, I though. hrmm...

 

[calcnd]

As for your other point about solving it in another fashion, I could add n 1's to the right of the last 1 on the string, then evenly partition them. But that still requires keeping track of how many 1's have been encountered.

 

[Hurkyl]

But I can't "count" the three ones and then tell it to write three, as the machine can't remember what it's encountered other than its current state, no?

Then count them one at a time, just like humans do!


P.S. can you pick what alphabet you get to use, or do you have to use {0,1}? Obviously you can't choose your alphabet after knowing how many 1's there are, but it's somewhat more convenient to have a third symbol.