Clueless on TM Calculations & Proving Infinitude

In summary, the machine is supposed to create a string of numbers that are the sum of the digits in the input string. For example, if the input is "1, 2, 3", the output would be "1+2+3".
  • #1
calcnd
20
0
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.
 
Physics news on Phys.org
  • #2
calcnd said:
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?
 
  • #3
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...
 
  • #4
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.
 
  • #5
calcnd said:
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.
 

Related to Clueless on TM Calculations & Proving Infinitude

1. What is TM calculation and how is it used?

TM calculation refers to the process of determining a molecule's topological polar surface area (TPSA) and its molecular weight. It is often used in drug discovery and design to predict a molecule's solubility, permeability, and other properties that are important in drug development.

2. How is infinitude proven in TM calculations?

Infinitude is proven in TM calculations by showing that there is an infinite number of possible molecular structures that can be derived from a given chemical formula. This is done by calculating the TPSA for different molecular structures and demonstrating that there is no upper limit to the TPSA value.

3. What are the main limitations of TM calculations?

The main limitations of TM calculations include the assumption that all atoms in a molecule contribute equally to its molecular weight, the neglect of 3-dimensional molecular structures, and the inability to accurately predict properties for highly complex molecules.

4. How do TM calculations contribute to drug discovery?

TM calculations play a crucial role in drug discovery by providing valuable information about a molecule's properties that can help in optimizing its drug-like characteristics. This can lead to the development of more effective and safe drugs.

5. What tools or software are commonly used for TM calculations?

Some commonly used tools and software for TM calculations include ChemDraw, ChemAxon, and ACD/ChemSketch. These programs use various algorithms and databases to calculate TPSA and molecular weight for a given chemical structure.

Similar threads

  • Programming and Computer Science
Replies
4
Views
1K
Replies
3
Views
180
  • Introductory Physics Homework Help
2
Replies
41
Views
4K
  • Engineering and Comp Sci Homework Help
Replies
7
Views
2K
  • Engineering and Comp Sci Homework Help
Replies
14
Views
2K
  • Introductory Physics Homework Help
Replies
11
Views
786
  • Programming and Computer Science
Replies
1
Views
697
  • Engineering and Comp Sci Homework Help
Replies
5
Views
2K
  • Calculus and Beyond Homework Help
Replies
1
Views
2K
  • Engineering and Comp Sci Homework Help
Replies
1
Views
2K
Back
Top