Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss

Turing machine counting

2 views
Skip to first unread message

spellbound

unread,
Jun 1, 2008, 11:11:57 AM6/1/08
to
Hey! I'm very sorry if this is the wrong place to post, but i have a
problem with turing machine.
I need to build a TM that counts the difference between number of ones
and zeros written on the track. The result needs to be in decimal
system. I was thinking about making the machine with four tapes, where
i'd write ones and zeros on separate tapes, and the result would be on
fourth tape. I don't really have an idea how to use the tapes to get
result. If there's a better way to solve this problem, or if anyone
has a link to explanation how to do it, i'd be really grateful!
Thanks in advance!

Jym

unread,
Jun 2, 2008, 4:25:41 AM6/2/08
to

This is usually not the place where answers to homework are given...

However, you can try the following things (just thinking out loud, might
not be the best way to do it):
1/ Build a single tape TM that adds 1 to the number written on the tape
(in binary).
2/ Same but in decimal.
3/ Build a TM that substract 1 to the number written on its tape, if it's
bigger than 0.
4/ Build a 2-tapes TM that tells which number (written on both tapes) is
the larger.
5/ Build a multi-tapes (don't know how many) TM that perform substraction
of two numbers (written in 2 tapes) by repeatidly substracting one to both
of them.
6/ Build a multi-tapes TM that read its input, counting the numbers of 0
and 1 on two different tapes and then perform substraction of the two
numbers.
7/ (if needed) fold back the latest TM into a single tape TM.

--
Hypocoristiquement,
Jym.

0 new messages