Re: Can Turing machines do arithmetic?

From: Will Twentyman (wtwentyman_at_read.my.sig)
Date: 03/03/05 

Date: Thu, 03 Mar 2005 15:36:14 -0500

mensanator@aol.com wrote:
> Will Twentyman wrote:
>
>>mensanator@aol.com wrote:
>>
>>>Will Twentyman wrote:
>>>
>>>
>>>>mensanator@aol.com wrote:
>>>>
>>>>
>>>>>I am having trouble accepting the following argument:
>>>>>
>>>>><quote>
>>>>>Turing machines (with 0, 1, and bounding marks),
>>>>>though they deal exclusively in bitstrings,
>>>>>are nevertheless able to perform arithmetic.
>>>>></quote>
>>>>>
>>>>>I would have thought that what a Turing machine
>>>>>does to a pair of bit strings is an abstraction
>>>>>that is equivalent to arithmetic.
>>>>
>>>>As opposed to what we do on paper, which is a similar type of
>>>
>>>abstraction?
>>>
>>>
>>>>>For instance, appending a 0 to a string of bits
>>>>>
>>>>>101 -> 1010
>>>>>
>>>>>is an abstraction equivalent to multiplication by 2.
>>>>>But appending a 0 is NOT arithmetic.
>>>>
>>>>If the input was 101#10 and the output was 1010, I would be happy
>
> to
>
>>>>call that arithmatic in binary.
>>>>
>>>>
>>>>
>>>>>The source of the argument is the abstraction
>>>>>
>>>>>2. Add the original string to a copy of the original
>>>>> string with a '1' appended.
>>>>>
>>>>>original: 101
>>>>>copy: 1011
>>>>>result: 10000
>>>>>
>>>>>I say that at an abstract level, you cannot 'Add'
>>>>>because that is arithmetic. My argument is that you
>>>>>must further define the abstraction 'Add' in terms
>>>>>of string manipulation, such as concatenating a bit
>>>>
>>>>>from each operand along with the previous carry, and
>>>>
>>>>>looking them up in a Full Adder hash table (or whatever
>>>>>the equivalent Turing machine operation would be).
>>>>>
>>>>>Am I all wet?
>>>>
>>>>Well, If you said take a number, double it and add 1, then add the
>>>>results, I would get:
>>>>
>>>>original: 5
>>>>copy: 11
>>>>result: 16
>>>>
>>>>All of which are operations that I do by string manipulations that
>>>
>>>I've
>>>
>>>
>>>>learned so well that I do them by rote. I view a lot of arithmatic
>>>
>>>and
>>>
>>>
>>>>algebra as string manipulations, so don't see where the distinction
>>>
>>>is.
>>>
>>>The original formula is to take n and return (3*n + 1).
>>>
>>>I said that
>>>
>>>n = (n << 1) + n # n left shifted 1 position added to itself = *3
>>>n += 1 # n incremented
>>>
>>>was an abstraction. He said no, you're still doing arithmetic, the
>>>abstraction must use strings only. That's ok with me and I have no
>>>problem with getting (2*n + 1) by appending a 1 to the string of
>>>binary digits representing n. But then he simply 'adds' n and
>
> claims
>
>>>that is still an abstraction.
>>>
>>>To which I said no, you can't 'add' strings because they are not
>>>numbers. I said you must define the abstract concept of 'add' using
>>>strings just like you did when you multiplied by 2 and added 1.
>>>
>>>And that's what led to the above quote. I'm not so concerned about
>>>right versus wrong but about consistency. If you want do define
>
> math
>
>>>at an abstract level that only involves string manipulation, I
>
> can't
>
>>>see how you are allowed to 'add' strings.
>>
>>If I understand you right, it's an issue of defining the string
>>manipulations necessary to represent addition. The effect is
>
> addition,
>
>>through string manipulation. How about representing it as follows:
>>
>>"101 1011 " is the initial string.
>>"0101 1011 " is the string formatted to have the same digits
>>"010 101 1 0" is the result of adding the 1's digits and noting a
>
> carry.
>
>>"01 10 1 00" is the result of adding the 2's digits and noting a
>
> carry.
>
>>"0 1 1 000" is the result of adding the 4's digits and noting a
>
> carry.
>
>>" 1 0000" is the result of adding the 8's digits and noting a
>
> carry.
>
>>" 0 10000" is the result of adding the 16's digits and noting
>
> no
>
>>carry.
>>
>>Where the rules for prepend and setting the carry digit are as
>
> follows,
>
>>given the last digits and carry digit:
>>
>>0 0 0 yields 0 0 for carry and prepend
>>0 0 1 yields 0 1
>>0 1 0 yields 0 1
>>0 1 1 yields 1 0
>>1 0 0 yields 0 1
>>1 0 1 yields 1 0
>>1 1 0 yields 1 0
>>1 1 1 yields 1 1
>> 1 yields 0 1
>> 0 yields stop
>>
>>Does that seem more like what you were looking for?
>
>
> Yes, very nice. I wasn't really asking if it was possible,
> what I'm trying to get at is consistency. If I have to speak
> of multiplication by 2 as the string operation "append 0", then
> I should have to explicitly describe the string manipulations
> involved in "addition".
>
> My point is that if I'm allowed to say I can "add" because a
> Turing machine can do arithmetic, then why can't I multiply
> also? Surely I can simply repeatedly invoke the "add" function.
> Why all the fuss about appending 0s?
>
> I think the problem is my opponent can't describe string addition
> in ten words or less and he's trying to weasel out of this dilemma
> and I'm not going to let him.
>

Ah, I misunderstood what you were getting at in the original post. It
appears that you don't feel his argument is consistent, in that he wants
to deal with the abstraction at one point, but not at another. I take
it you want him to make up his mind one way or the other and be done
with it. It reminds me of this thread in sci logic
http://groups-beta.google.com/group/sci.logic/browse_frm/thread/cc02a70bba452722/91f19d9e9f01230c?q=primitive+recursive+function+group:sci.logic+author:twentyman&_done=%2Fgroups%3Fas_q%3Dprimitive+recursive+function%26num%3D10%26scoring%3Dr%26hl%3Den%26ie%3DUTF-8%26as_epq%3D%26as_oq%3D%26as_eq%3D%26as_ugroup%3Dsci.logic%26as_usubject%3D%26as_uauthors%3Dtwentyman%26lr%3D%26as_drrb%3Dq%26as_qdr%3D%26as_mind%3D1%26as_minm%3D1%26as_miny%3D1981%26as_maxd%3D3%26as_maxm%3D3%26as_maxy%3D2005%26safe%3Doff%26&_doneTitle=Back+to+Search&&d#91f19d9e9f01230c
where Herc wanted me to prove primitive recursive functions were enough
to define arithmatic. For the most part, it's just tedious.

What is it this guy's trying to accomplish, anyway?

Relevant Pages