Logik wrote: ↑
Fri Mar 01, 2019 12:21 am
Scott Mayers wrote: ↑
Fri Mar 01, 2019 12:06 am
Note, if you opt to read Turing's paper, his pre-requisite is that the system is "circle-free". The author of Turing Essentials didn't seem to understand what he meant correctly but it refers to dismissing repeat decimals as rationals, such as 1/3 = 0.33333.... To do this, he required the tape he used to not be connected in a literal circle which would force it to be 'finitely' limited.
This is not a relevant detail. A circle-free tape in a finite universe is still finite. It is actually a worse design because it makes memory-access latency way worse than it needs to be.
If it's a circle you can go clock-wise or counter-clock-wise. Shortest path optimization.
Sorry, you missed my meaning. The proof he uses requires having an initial Turing Universal Machine (a general purpose computer) that can solve an infinite set of problems. If you begin with a finite machine (a limited memory space), it can't technically ever be able to solve all problems. So he set up an imaginary tape that is not linked end to end to represent an infinity of INPUTS and OUTPUT possibilities. We can do this finitely only if we reconstruct our computers in real life in a similar way to biology (component neurons that are 'born', 'grow', 'shrink', or 'die' where needed.) Our computers are actually 'finite machines' that are 'universal' but limited to the sizes of their fixed registers. The fixed registers limit the maximum size of memory space, which acts to both hold data AND act as portals (ports) as 'inputs and outpusts'.
The proof required listing all possible programs to infinity with infinite data spaces for memory that act as both input and output. You can't allow the data to alter such as a normal ports or you can't quantify all possible programs without running into possible repeats. For instance, if you allow the internet to be included in the design, you technically only require one REAL input space, such as our cable line provides serially as data input and output. But because such relatively unpredictable inputs can have repeats, we cannot count all possibilities without running into repeats (meaning we'd count what may be only one unique program as a potential infinite separate programs.
The use of a non-cycling tape also permits you to count each FINITE instance of repeated data. So, we count, 0.30000... as distinct from 0.33000...., etc, rather than confuse them all for meaning 0.33333... . If we allowed the tape to loop, the computer might be programmed to write 0.3 once, but when re-read, it might come out as 0.333333.... without being able to halt. It would not appropriately thus be able to print out what we actually put in.
So the 'circle-free' limitation is to mean that the tape used in his machine is an imaginary infinite one in both directions. Then, a number like ....00003000... is uniquely counted as ONE program, not an infinity of them.
Sorry if this is only adding to the confusion. But Turing was using language that we would mistranslate today for lacking the same identical background he assumed other readers of his day already knew within the field of logic. Even Bertrand Russell is now a tougher read today without learning a lot of their era's terminology and common educational prerequisites assumed. [They used that bottom-up approach we don't use today and a top-down strategy, though more practical now, uses a different approach that we can relate to better to our own era's expectations.]