Re: What is complexity?

In article <5EQif.6768$6e5.5733@trnddc09>,
R. Baldwin <res0k7yx@xxxxxxxxxxxxxxxxxxxx> wrote:
>"Kim G. S. Øyhus" <kim@xxxxxxxxxxx> wrote in message
>news:dmeukq$mts$1@xxxxxxxxxxxxxxxxxxxxx
>> You have often lately asked me to study stuff I already know.
>>
>> None of what you have said contradicts my statement that it is not
>> necessary to have an infinite tape in a physical Turing machine, as
>> long as the tape can grow.
>>
>> You still misunderstand me, even when I write it simply and directly.
>>
>
>I understand that you are wrong.

Sigh. You are quite stupid. Look here:

This is a simple representation of 3 Turing compatible machines.
One with an infinite tape:
A: H00000000000000000000000000000000000000.....................
And two with a finite tape
B: H00000000000000000000000000000000000
C: H00000000000000000000000000000000000

After a while running the same program, they have made some output,
and moved the head, H:
A: 100010111100000101111H00000000000000000.....................
B: 100010111100000101111H00000000000000
C: 100010111100000101111H00000000000000

Note, that they have made the same output, even though one are
infinite, while the others are finite.

A while later, the head reaches the end of the finite tape:
A: 10001011110000010111100010011100000H000.....................
B: 10001011110000010111100010011100000H
C: 10001011110000010111100010011100000H

The B machine then grows:
A: 10001011110000010111100010011100000H000.....................
B: 10001011110000010111100010011100000H00000000000
C: 10001011110000010111100010011100000H

And they both continue, while C has halted:
A: 10001011110000010111100010011100000111100H00.....................
B: 10001011110000010111100010011100000111100H00000
C: 10001011110000010111100010011100000H

And each time the head of the B machine reaches the end of the tape,
the tape grows bigger. And since the heads on both machines will
encounter precisely the same data, both machines will give the same
output.

This is how a finite growing machine can be a perfect Turing
machine. Since a true Turing machine always only uses a finite amount
of its infinite tape, because the head can only move 1 step at a time,
it does not matter wether the unused portion of the tape is there or
not, as long as it is there when it is needed, and the infinite ends
of the tape are never needed in a finite amount of time.

Kim0

.

Relevant Pages

  • Re: [QUIZ] The Turing Machine (#162)
    ... This week's task is to build a Turing Machine, ... An infinite tape of memory cells that can hold one character ... head of the tape. ...
    (comp.lang.ruby)
  • Re: Any Compact Cassette experts left?
    ... Ben Stratford wrote in message ... ... session with various tapes, I tape the first side - all ok. ... A stereo cassette head will have either two tracks or four tracks. ... the erase head is partially erasing the wrong part of the tape as well ...
    (rec.audio.tech)
  • Re: OT: Gangbusters - light receptors dont & car motor rusted
    ... replacements are hard to find. ... Make sure the game is properly grounded. ... two stereo tape heads and a 3-channel preamp. ... The tape head alignment mechanism on those decks is real crap. ...
    (rec.games.pinball)
  • Re: OT: Gangbusters - light receptors dont & car motor rusted
    ... Make sure the game is properly grounded. ... two stereo tape heads and a 3-channel preamp. ... The tape head alignment mechanism on those decks is real crap. ... I also carry optos that should work for your game - if you can tell me what the dark resistance is as well as the light resistance I can likely match them up. ...
    (rec.games.pinball)
  • Re: DIY multi-track with cassette recorders?
    ... So I guess I'm left with using VHS or some other wide, single tape ... If you don't mind building a bit of stuff, a reversing deck with a 4 gap head will let you use all four tracks at once. ... You'll either need two sets of electronics as used by the original makers or you'll need to build four sets of playback and record amplifiers, and get hold of a full width erase head, or, preferably, a four gap erase head. ... If all you want is cheap analogue multitrack, then something like a second hand cassette portstudio may well be available for next to nothing, but even the cheapest digital multitrack setup will sound better than *any* cassette setup. ...
    (rec.audio.pro)