Infinite and unbounded

This article was first published on Dr. Craig Wright’s blog, and we republished with permission from the author.

Unfortunately, a major problem stems from a lack of understanding of many common terms today. Turing completeness does not require an infinite tape, and it was not an infinite tape that Turing mentioned in his paper; it was an unbounded system. Importantly, you cannot have a Turing machine with an infinite tape rather than an unbounded tape—by definition. An infinite tape is not related to a problem that can be computed. When both Church and Turing wrote their papers, the computer they discussed was human. The individual who was the mathematician doing the problems was termed a computer. So when we are talking about problems of the same type, we are talking about ones that are computable through a simple algorithmic process, that may be created and used by a simple process that now runs on a machine.

The first thing you need to remember is that a Turing machine can compute any computable problem. Not all algorithms can be computed. Saying that you can run a program that never halts is not creating a Turing machine. It also isn’t an infinite tape; it is an unbounded system. By definition, any unbounded system is always infinitely smaller than the infinite. If you think about it, a process that is run as one that is “unbounded” requires a system in our universe that can run through the existence of time. Admittedly, it would require a very large value for the computation and is mindbogglingly big. Yet, it is anything but infinite.

The next, and arguably more important, component to remember here is that if another number is to be computed in our universe, our universe is not infinite; the time to compute the number must be finite. Unfortunately, computation is an undecidable problem, because a component of mathematics led to what is known as the halting problem (Turing, 1936; Burkholder, 1987). The computation of values may not halt, and the halting problem cannot be solved (Boyer & Moore, 1984). For the same reason, it is infeasible to determine whether any script that can run on a Turing machine will ever end. By its very definition, any computable number, and hence any value that can be solved algorithmically, must end within finite time. What people fail to grasp is that Turing machines do not run programs that cannot be computed algorithmically. Any program that has no algorithmic solution is not a program that is solvable on a Turing machine. Many of them will either fail or, more importantly, continue indefinitely—without ever coming to a solution.

Bitcoin is a Turing-complete system even in script. A Turing machine assumes that you have an unbounded tape. In our instance, it would mean an unbounded script size. Given an arbitrarily long script, you can run any possible computable algorithm. The fact that the size of the script becomes unwieldy is irrelevant. Not all Turing machines are efficient. In fact, there is nothing in the foundations of Turing machines that requires efficiency. Whilst it is possible to run many programs that will take a seemingly considerable time to complete, the process of optimising them through parallel paths or through approximation may be sufficient. Conversely, there exists a set of programs that are not only computationally difficult but infeasible and intractable and that do not come up with more than possible solutions. Such programs may run indefinitely and never halt on algorithmic systems.

The main reason Bitcoin Core attacks the comment that I have made, of Bitcoin being Turing-complete, is related to the introduction of limits that were originally temporarily imposed upon Bitcoin and that have been implemented in more insidious manners within BTC. Whereas I said that Bitcoin would grow to the point where it would end in data centres, they wished to create a separate system, one that was more limited. A limited tape is not one that can run any algorithm. In other words, with a limited transaction size, you can never achieve the same level of computation as you can with an unlimited transaction size. As Rogers (1959) demonstrated, degrees of computational unsolvability exist, but it does little to remove the fact that we don’t know, in many cases, whether a program is solvable or not until it is run. Worse still, as Gaboury (1942) and later Rogers (1958) demonstrated, there is no solution addressing whether we can even find a solution to many problems.

In computer science, there is a problem known as the omega problem (Dantzig, Fulkerson, & Johnson, 1954; Hudzik, 1979). The difficulty with designing algorithms lies in not even knowing how to create algorithms that are provably going to halt. The consequences of the omega problem lead to one of the difficulties in fixing computer bugs. Omega is irreducible. If we ask the probability of the random programmers, and whether that algorithm will eventually halt for a given input, we cannot necessarily even determine whether the question is valid. It is linked to the problem of a theory of everything (TOE) in physics. We cannot create an axiomatic foundation for mathematics, yet we can find a single underlying theory of how the universe works. Unfortunately, since we are incapable of determining the mathematical foundations of computation, seeking to solve the halting problem is merely an empty hole that will take all we can give whilst remaining empty (Jacobs, 1890).

Turing wrote multiple papers detailing the same topic (Turing, 1936; Turing & Church, 1937) and related ones, on computability and lambda definitions (Turing, 1937). If you read them, you will see that he is talking about “‘computable’ numbers” (Turing, 1936, p. 230), which “may be described briefly as the real numbers whose expressions as a decimal are calculable by finite means”. Pi is not a Turing-computable value by the same definition. Rather, an approximation of pi, in finite time and space, can be considered Turing-computable.

There are many good references to the computability of different numerical values, including pi. Nies (2009) provides an excellent research reference associated with the topic, and others, such as Miller (2003), provide suitable adjunct works. I could even link it to works created by lesser known authors such as Khoussainov, Slaman, and Semukhin (2006), yet if I were to do so here, I would be accused of promoting “technobabble”. It is so because such work, while valid and algorithmically and syntactically interesting, is highly specialised and even, in some ways, arcane. So, it is, unfortunately, a rabbit hole I won’t be going down today.

Turing’s paper is premised on Godel’s (1931). Unfortunately, if you do not have the mathematical background in the form of discrete maths that the authors were writing about, you are likely to make one of the many errors that people make when it comes to the definition of a Turing machine. For example, Turing had noted (1936, p.230) that the class of computable numbers was “nevertheless enumerable”. But, he did not say that the Turing machine itself needed to be enumerable for all else to be true.

Turing was extending the research of Church (1936), who was researching the concept of ‘effective calculability’. As Turing noted, effective calculability, whilst separately defined, is functionally equivalent to Turing’s concept of ‘computability’. For the same reason, it has been called the Church-Turing problem. Each author created a solution, with Church deriving his first.

Hennie (1965) investigated the concept of a single-tape, offline Turing machine. Such a machine and tape can be used for computation as needed and created in a structured manner, that can be later produced to validate any single computable number. An example of how such a machine would be reflected in Bitcoin script would be to create a set of rules and mathematical processes that can compute any digital number on a tape that may then be processed. As such, we can analogise the tape to the Bitcoin script. In the same way, you could imagine creating a single transaction as a single tape compiled and produced offline but used online, within finite time.

Hartmanis (1968) provided a discussion around the complexity of single-tape Turing machines. Whilst Hartmanis noted that regular sets of sequences are sharply time-bound, various forms of computational complexity could be used to measure such forms of computation. Simultaneously, it is possible to determine the different complexity levels for such tapes and compare them to those for multiple-tape machines. Various forms of computational complexity have thus been derived. So, the question is now not whether a script presents a Turing-complete system, but whether it is efficient. Of course, a single-tape computation is inefficient, and it is not one that I would recommend, but it is feasible and possible to implement.

Shannon (1956) looked at the concept provided by Turing to make a mechanical or electric machine, and made an error in the description. Unfortunately, Shannon (1956, p. 157) described Turing’s machine as a system that requires “a control element, a reading and writing head, and an infinite tape”. Yet it was not Turing who said a Turing machine had to be infinite, but rather Shannon. Others in the ‘50s and ‘60s who had arallelize in computation also used the terminology of ‘infinite’ when they should have said ‘unbounded’ or ‘unlimited’. The distinction between an unimaginably large number and an infinite one doesn’t matter to most people. To many, an early concept used to simplify discussions in physics and mathematics was termed ‘effectively infinite’. It is used in a paper by Farmer (1935), where the author notes that although the system is not infinite, an approximate value may be obtained by assuming that the value is “effectively infinite”.

Whilst Shannon produced some excellent engineering, he was not a mathematician. The difference between engineering knowledge and computer science and mathematical foundations provides an important distinction, as Turing (1936, p. 230) categorically said that it was a machine that can calculate “the real numbers whose expressions as a decimal are calculable by finite means”. Shannon is an engineer. To an engineer, the mathematics of the system is less relevant, and the difference between an unbounded system and the infinite are seemingly meaningless; in each case, they present bigger numbers than you will ever compute.

Turing noted that the computing machine does not write more than a finite number of symbols (1936, p. 233). As such, the machine is unbounded, but it is not infinite. It is a significant and important distinction, which many non-mathematicians failed to comprehend. The value associated with an unbounded machine is infinitely smaller than any infinite value. Thus, while many engineers have arallel the concept of an “effectively infinite” system, and others have even said that the value 2^256 is itself infinite for all purposes, such values remain computable and usable in real terms.

Moreover, values that are effectively infinite at one point in time may prove to be computable at a later date. The noninclusive sets and concepts of limits, unlimited systems, and infinite systems are important to note. For example, all existing encryption (outside of one-time pads that have never been reused) can be said to have an expiry date and eventually be broken. By the limits of how we educate people today, people fail to understand that there is a vast distinction between a truly infinite system and one that is practically infinite. Importantly, whilst a value can have an error rate that is negligible and can be discarded, Lorenz (1961) demonstrated that small variations could have significant or simultaneously important effects on the outcomes of data-based processes (Lorenz, 1956).

Hopcroft and Ullman (1969, p. 168) investigated tape-bound Turing machines and followed up Shannon’s error of assuming an infinite working tape, rather than an unbounded one. The assumption of infinity when talking about a system without mathematical limits is, unfortunately, laziness, and should not have been made in such a manner. You will note that they discuss the online and offline versions of Turing machines and that in the case of the offline Turing machine I mentioned before, the tape can be assumed not to loop. In their paper (1969, p. 169), you will note that the authors have removed the assumption of the machine halting for every input. Whilst it provides a form of machine, it is not more than a single example, and people take them for more than they are and make them universal. Note that I’m not talking about a universal Turing machine here, which is a different thing again.

Suppose you read the paper in full. If you do, you will see that the definition of a nondeterministic Turing machine that Hopcroft and Ullman (1969, p. 169) presented as a 6-tuple is created using finite states and finite symbols. Therefore, it is not an infinite machine. The creation of finite values in an unbounded system means that the tape can be extended when needed. It does not mean that the tape in such a system is infinite, but rather that any time the end of the tape is being approached, a new tape could be appended. In the formatting of Bitcoin script-based transactions, it would require extra drive space to store the transaction that is being unrolled (Dongarra & Hinds, 1979).

Although people use the terms infinite and unbounded interchangeably, they present different concepts. There is a difference between an unbounded system and an infinite system, as an unbounded system is necessarily finite. Whilst it has no defined limits, it is by and large definable, which differs from an infinite system, which by and large is indefinable. In the process noted by Steele (1980), a series of algorithms are created using unrolled loops. The author thereby extends some of the work of Knuth (1973), and investigates the creation of serial machines. Other investigations, such as the one by Baker (1978), also investigated unrolled loops for linear-machine applications.

The way to think about it is: you create a system that is 100 tape units long, and if you need more space, you add another system of 100 tape units to extend it. You can do so as many times as necessary. It remains a process that takes place within finite time, bound by finite space, and hence never becomes infinite. While modern computers are highly arallelized in the way they process information, early computers ran using serial tapes. Consequently, the move towards register machines in place of serial machines has led to many people believing that computation must be a one-way function. Or even that the creation of a system that does not loop cannot in itself present a Turing machine.

One-way finite-state automata are well documented and have been for many years (Greibach, 1978). Some have also extended their research into investigating one-way functions (Levin, 2003). Others will have investigated the creation of deterministic one-way Turing machines in what is known as sudden linear space and how such can be created more efficiently (Kutrib et al., 2015). But, perhaps the most interesting use of such a system lies in creating what is known as a simplistic universal cellular automaton (Iirgen Albert & Culik II (1987).

Note here that I have said “in <space> finite”, and I have not said it in a manner that says it is a process that is “infinite”. The distinction is not mathematical but rather in noting in <space> finite differs from the English expression infinite. An infeasible problem cannot be solved and has no solution. Yet, an unbounded problem may be calculated given sufficient time and memory space. My personal interest has been in probabilistic one-way Turing machines (Santos, 1969; Kaņeps & Freivalds, 1990). In all of them, as Ablayev (1996) demonstrated, it is possible to discover the lower bounds on the computational complexity for such systems.

In a paper on arallelized computation, Juille and Pollack (1996) documented methodologies to create a multiple-tape Turing machine that would be more efficient than the single-tape transaction type proposed above. Here, rather than using a single transaction, you would run many transactions in parallel and only require that a single path be promoted as a solution. Thus, you would not use a single transaction but rather an unbounded number of transactions that are computed as offline Turing machines where you only leave a single transaction to be recorded on the blockchain, one that has been demonstrated (outside the blockchain) to find the desired solution and to compute the problem correctly.

McCarthy (1956, p. 177) noted that a system such as a Turing machine in a single Bitcoin transaction (and no, he wasn’t describing Bitcoin—but general computational machines of the same type) is extremely inefficient. Consequently, as explained in the paper by Juillé and Pollack (1996), the solution should be found in arallelized systems that compute many possibilities simultaneously, rather than forming a single unwieldy transaction tape. Having said so, it remains that a single transaction, and the script that can be written in a single transaction, is itself Turing-complete, as long as you do not try to limit the size of the blockchain.

Conclusion

The argument against Bitcoin being Turing-complete is one of transaction and block-size limits. Given such limits, Bitcoin would not be a Turing-complete system, but Bitcoin wasn’t designed to be limited in such a manner. Hence, whilst the BTC system is not Turing-complete, Bitcoin is. Arguments surrounding the concept of a system not being Turing-complete because it cannot loop are false. In a Church-Turing system, there is no requirement for a computational process or algorithm to loop, even though the length of the algorithm may be excessively large when loops are not found. Alternatively, many smaller functions can be run in parallel. As Bitcoin is a predicate system, only the output with a correct answer will be saved on the Bitcoin blockchain.

References

Ablayev, F. (1996). Lower bounds for one-way probabilistic communication complexity and their application to space complexity. Theoretical Computer Science, 157(2), 139–159.

Baker Jr, H. G. (1978). List Processing in Real Time on a Serial Computer. Communications of the ACM, 21(4), 280–294.

Boyer, R. S., & Moore, J. S. (1984). A Mechanical Proof of the Unsolvability of the Halting Problem. Journal of the ACM (JACM), 31(3), 441–458.

Burkholder, L. (1987). The halting problem. ACM SIGACT News, 18(3), 48–60.

Church, A. (1936). An Unsolvable Problem of Elementary Number Theory. American Journal of Mathematics, 58 (1936), 345–363.

Gödel, K. (1931). Über formal unentscheidbare Sätze der „Principia Mathematica“ und verwandter Systeme I. Monatshefte für Mathematik und Physik, 38 (1931), 173–198.

Dantzig, G., Fulkerson, R., & Johnson, S. (1954). Solution of a Large-Scale Traveling-Salesman Problem. Journal of the operations research society of America, 2(4), 393–410.

Dongarra, J. J., & Hinds, A. (1979). Unrolling loops in Fortran. Software: Practice and Experience, 9(3), 219–226.

Farmer, F. T. (1935). An Apparatus for Recording Average Amplitudes of Wireless Echoes. Mathematical Proceedings of the Cambridge Philosophical Society. 31(2), 295–302.

Gaboury, J. (1942). On Uncomputable Numbers: The Origins of a Queer Computing. Journal of the New Media Caucus| ISSN, 017X.

Greibach, S. A. (1978). One way finite visit automata. Theoretical Computer Science, 6(2), 175–221.

Hartmanis, J. (1968). Computational complexity of one-tape Turing machine computations. Journal of the ACM (JACM), 15(2), 325–339.

Hennie, F. C. (1965). One-tape, off-line Turing machine computations. Information and Control, 8(6), 553–578.

Hopcroft, J. E., & Ullman, J. D. (1969). Some results on tape-bounded Turing machines. Journal of the ACM (JACM), 16(1), 168–177.

Hudzik, H. (1979). The problem of separability, duality, reflexivity and of comparison for generalised Orlicz-Sobolev spaces\(W_M^ k (\Omega)\). Commentationes Mathematicae, 21(2).

Jacobs, J. (1890). English fairy tales. David Nutt.

Juillé, H., & Pollack, J. B. (1996). Massively Parallel Genetic Programming. Advances in Genetic Programming, 2, 339–357.

Khoussainov, B., Slaman, T., & Semukhin, P. (2006). (Pi^ 0_1)-presentations of algebras. Archive for Mathematical Logic, 45(6), 769–781.

Kaņeps, J., & Freivalds, R. (1990). Minimal nontrivial space complexity of probabilistic one-way Turing machines. International Symposium on Mathematical Foundations of Computer Science, 355–361.

Knuth, D. E. (1973). Art of computer programming, volume 2: Seminumerical algorithms. Addison-Wesley Professional.

Kutrib, M., Provillard, J., Vaszil, G., & Wendlandt, M. (2015). Deterministic One-Way Turing Machines with Sublinear Space. Fundamenta Informaticae, 136(1-2), 139–155.

Iirgen Albert, J., & Culik II, K. (1987). A simple universal cellular automaton and its one-way and totalistic version. Complex Systems, 1, 1–16.

Levin, L. A. (2003). The tale of one-way functions. Problems of Information Transmission, 39(1), 92–103.

Lorenz, E. N. (1956). Empirical Orthogonal Functions and Statistical Weather Prediction. Massachusetts Institute of Technology Department of Meteorology.

Lorenz, E. (1961). Chaos theory.

McCarthy, J. (1956). The Inversion of Functions Defined by Turing Machines. Automata Studies (AM-34), 34, 177–182.

Miller, J. S. (2003). Pi-0-1 classes in computable analysis and topology. https://dl.acm.org/doi/abs/10.5555/935786

Nies, A. (2009). Computability and randomness (vol. 51). OUP Oxford.

Rogers, H. (1958). Gödel numberings of partial recursive functions. The journal of symbolic logic, 23(3), 331–341.

Santos, E. S. (1969). Probabilistic Turing machines and computability. Proceedings of the American mathematical Society, 22(3), 704–710.

Shannon, C. E. (1956). A universal Turing machine with two internal states. Automata Studies (AM-34), 34, 157–166.

Steele Jr, G. L. (1980). Destructive Reordering of CDR-Coded Lists.

Turing, A. M. (1936). On computable numbers, with an application to the Entscheidungsproblem. Proceedings of the London mathematical society, 2(1), 230–265.

Turing, A. (1936b). Halting problem. London Mathematical Society.

Turing, A. M. (1937). Computability and λ-definability. The Journal of Symbolic Logic, 2(4), 153–163.

Turing, A. M., & Church, A. (1937). Computability and X-definability. Symbolic Logic, 2.