Show finite conundrumless computer cycling

General Justification: [June 97]

Particular case of CYCLING: [Nov96]

Computer's finite memory implies finite number of states; implies some state must be repeated if it runs long enough(2 multiplied once for each memory bit). Deterministic, unique change from one state to the next and use of only one input starting state, requires repetition of same states after first repetition. Computers cannot generate irrational numbers, only a finite number of rationals, even if run forever.For example: program to 'compute square root of 2', may output the first million digits of square root, but then whenit ultimately overflows, resets and starts over(repeatedly) making a long, unending rational number. Also any materialistic computer can only make a finite number of different rational numbers because it can only receive a finite number of different starting input data & programs. The integers of Peano(human) arithmetic are not materialistic integers defined under a maximum bound.To demonstrate, you can use default symbolic hardware input/output LOGIC TABLE or retype it. Each digit represents for each time the complete binary state of all memories: disk, ROM, registers & clock(program, data & time). Inputs must include result state output digits&start digit in completely defined program logic table(see below for complete explanation). Practical computers are designed to respond the same way to the same FINITE INPUT NUMBER using their FINITE MEMORY and FINITE HARDWARE. Non-deterministic finite automata are obviously equivalent to deterministic finite automata with non-deterministic or random input; but they repeat the same output when the input happens to repeat giving a random but finite 'period' between.
You can click 'run program' to use displayed symbolic hardware logic table. Then note results. You can click 'cycle period' to compute cycle length . 

I hope this demonstrates the mechanical generality and mechanical clarity of defining a computer's 'halting' as the first repeat of a total internal state - it computes nothing new after this time. All material computers thus will halt sometime. It only takes a computer with larger memory to record & compare another's total internal states to find the other's 'halt' time. Only a supernatural computer with infinite memory like the Turing machine may have an infinite period(not halt) and be confusing. A simple non-halting case[supernatural] would be just repeatedly running down its infinite tape memory, writing ones. After A. Turing, R. Penrose in 'Shadows of the mind' asks: 'let this computational system find its own halt'. But, this clearly workable computational system for deciding if another computational system halts may require a larger memory and so may not be able to find its own halt state. If somehow it 'finds' a repeated total internal state, it would not respond any differently since halting implies a repetition of what has been done before!

Material computers cannot compute a non-rational diagonal of an infinite table - they loose count when it exceeds the largest number they can remember and compute a rational.
But back to traditional human logic, Cantor's diagonal method of generating numbers not in an infinite table, can equally well be applied to a tableof binary integers which can[traditionally] all be put in in order in one table - a contradiction. A similar problem occurs with a table of ALL possible rational numbers output by an infinite speed  but finite memory computer: this includes all infinite repeating decimals up to the maximum possible cycle period permitted by the memory size, so any 'other program' to compute any 'other' number[a modified diagonal, etc.] with this computer will only make one of the numbers already in the [finite]table. Only human brains 'generate' infinite, supernatural numbers, or the number of angels on a pin head as they did for hundreds of years in the dark ages.

Super-logic(lessons for the negative feedback neural net) is the source of rigorous definition and proof because their exact effect on a simple, well defined(12 pages of JavaScript) intelligence is completely demonstrable by full, exact disclosure of its internal activity.

Some may object that all computer algorithms can be reduced to a static entity that can be examined(somehow) without running them; but algorithms by definition are sequential and logic machines require exact use of timing counts. I propose this simple example: wire the output of an inverter(a computer 'not') to its input. When power is applied it simply oscillates . This mechanically implements 'p is not p' which old human 'logic' shuns as 'contradiction' but the oscillations may be used as a timer usually stabilized by a crystal.

Some would try to condemn non-human mechanization of human traditional logic. I see this objection as part of a historical transition period from accepting human logic to accepting mechanical logic. It is obvious to me that 'definitions' made for an unknown, unreliable destination(a human brain) are not only not rigorous but fraudulent! See computer 'proofs' in 'higher' logic below. By itself, human logic has had an impossible task of trying to develop itself by looking from the inside out of a biased and inaccurate mechanism. As long as there are unknowns about a mind and its program, arguments that depend on 'given' intuitive basic ideas are suspect. It takes a reliable mechanical proof for reliable material meaning. The javascript implementation of -nn shows reliable self-generated mechanical proof is practical. Human logic may benefit by trying to simulate the super logic of machines. And machines may benefit from human suggestions!

start 
input 
output 
results 
length 

Discussion

The above symbolic hardware table must contain a symbolic digit for each possible whole state to be changed(input) and a symbolic digit for each resulting state(output): the usual process of computer work is to turn on the power which starts the internal clock, to load programs & data in the memory, to give a starting instruction for the desired problem then to wait. For ease of use, many parts of a program are to be repeated(for loops, reentrance, etc.); so the computer is designed to respond (in a unique way) to the current instructions & data and generate new instructions or data to be automatically used as input for another output. It continues in this way until a prearranged signal is output so the user knows it is finished. Usually this signal is presented in an apparently 'fixed' way as 'DONE' for example. But actually the computer is just in a tight loop processing its clock into the same output. Usually the computer hardware is designed to give a unique response to any input bit pattern or its compiler is designed to permit only inputs to the hardware that do so. Otherwise, more than the usual unexpected results may occur and errors are more difficult to decipher. Users most often select computers that have a minimum of unpredictable output. 'Disallowed' instructions preferably notify the user with a reliable message. But philosophically, this is then just another reliable output which generalizes the computer by having it actually respond UNIQUELY to ANY INPUT!
For a finite memory, the above generality, reliability & efficiency require the variety of inputs to contain whatever the computer is expected to reenter input from its output in solving its given problem. That means these outputs that may become inputs may only be rearranged subsets of possible inputs. Here for simplifying the apparent complexity of having relatively slow memories like disk which are not usually thought of as input at any clock pulse, we can think of slowing all operations down to the slowest. Thus all bytes may be thought of as available input at each clock pulse. And as the above general implementation demonstrates, this causes results to cycle with a finite period whose number of clock cycles is no more than the 'maximum number' the computer can remember. This 'maximum number' is made by concatenating ALL the stored bytes that may be input at some time during the program run: clock memory, registers, IC memory, disk memory. This cycle period of common computers may be incredibly long, way more than the expected life of our solar system. All cycle periods are less than 2 multiplied by itself once for each total memory bit = P. The hardware(characteristics of the machine under discussion) is represented by the input/output table. For a universal machine, one that allows all possible hardware having distinct results using inputs of size P, must have a hardware input/output table size of P*P. The computer that computes its period must have a memory of P*P+P+ program.
Yet this cycle period makes clear meaning for general definitions of 'computer halt' or 'non-halt' and shows the emptiness of the idea of infinite and contradictory results from a finite machine. For a Turing machine, this 'maximum number' is all the bytes describing its states and all the possible bytes in its tape memory which are assumed infinite - this Turing machine may not 'halt'( it could just endlessly make 1's on its infinite tape).

Only Supernatural Computers have Supernatural Output!

Any deterministic, finite memory computer can only output a finite number of rationals(fractions) or cycling integers given one fixed, finite instruction input, even if it could run forever.
PROOF: (mostly obvious) finite memory allows only a finite Number of different internal states(N); so letting the computer run for N state changes, it must Repeat at least one State(RS). Then without changing the input, the determinism of having only one unique state follow any possible one, RS, means the same Sequence of internal States will repeat, Cycle(CS) exactly as it did the first time. Since a deterministic computer's outputs are a unique transform of a unique subset of these finite number of internal states, each output sequence must repeat or cycle and consist of only a finite number of different outputs. Finally, outputs considered as decimals must have digits that become unending repetitions and so are equivalent to a ratio of 2 finite integers.
DISCUSSION: There are many careless, common beliefs about computers. For example: "it can 'compute the square root of 2' to as many places as desired." The ancients were the first to show that the exact square root of 2 can not be the ratio of 2 finite integers and so cannot be a repeating decimal. But just let the program run long enough and it will start repeating trailing digit sequences - fast computers of today with large memories may take longer than the age of the universe before they find their most exact but still RATIONAL approximation. Just let it run long enough and it will cease finding more places in square root of 2! Many famous AI theorists(Turing, Penrose, Chaitin, etc.) have over looked this limitation of material computers. There is too much awe for the supernatural: IF a computer like the Turing machine with INFINITE memory can't do it no material computer can!But there are simple things that a material computer can do that finite speed computers with infinite memory cannot do: like setting their memory to zero. They have gone on to supernaturally demonstrate that a Turing machine causes a contradiction if it could solve all problems (see Penrose 'Shadows of the mind' or Chaitin's IBM site) and claim this result for supernatural computers applies to material computers. If one could get around the infinity contradictions it might prove some weird human logic limitations. Penrose wants to believe that since humans can reveal these 'higher' arguments, humans have supernatural, Platonic power. But the more likely conclusion is that humans can believe in foolish things. Godel's 'proof' of a conundrum in [human traditional]arithmetic requires 'infinite recursive substitution' as available in Turing machines(infinite memory & infinite speed) and optimistic humans but not material computers. G.Cantor's 'diagonal argument' requires infinite recursion to 'generate' a number not in any table of numbers. If this process is applied to a table of ALL the rationals that can be generated by a material computer(do n=n+1 until n=2^mem bits), and the same computer is used to generate in any way 'another' number, it must already be in the table! See my demo of super-logic as exact lessons(ASCII) for an exactly defined(javascript) neural net and my humanistic proof of the contradiction in human math of mathematical induction, the set of all integers and 1-1 mapping next.

Contradictory Infinity

Computer 'proofs' in 'higher' logic

As super-logic is lessons for a neural net, any 'higher' logic should be also. But this 'lesson' concept needs to be clarified:

Inputs that do not change any synapses may be considered variables - change only nerve stimulation states - set or reset 'flip-flops'. Any logic simulation that is in variables is not a proof in or by the net since the net structure is independent. A good test is whether only variable changes are required in the net to change the 'higher' logic assumptions. A generalization of this uses tautologies. A super-tautology is 2 'nor' formulas that map the same inputs into the same outputs. So different inputs that activate tautologies may be lessoned to use the same nor-formula and be considered variables.

Proofs based on variables do not have the reliability of super-logic!

Computer and Brain Limitations:

E-mail author: R Massey
top/home (25k)