Ramon Quesada
Bitcoin is a Turing complete system even in script.
Sep 1, 2021
Unfortunately, a major problem stems from a lack of understanding and 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.
The first part of this that 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. That also isn’t an infinite tape; it is an unbounded system. By definition, any unbounded system is always infinitely smaller than the infinite.
Bitcoin is a Turing complete system even in script. A Turing machine assumes that you have an unbounded tape. In this 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. However, there is nothing in the foundations of Turing machines that require efficiency.
The main reason that core attack the comment that I have stated that bitcoin is Turing complete is related to the introduction of limits that they have imposed. Whereas I stated bitcoin grows to where it ends in data centres, they wish to create a separate system that is more limited. A limited tape is not one that can run any algorithm. Hence, with a limited transaction size, you can never achieve the same level of computation as you can with an unlimited transaction size.
Turing wrote the following papers:
Turing, A. M. (1937). On computable numbers, with an application to the Entscheidungsproblem. Proceedings of the London mathematical society, 2(1), 230-265.
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.
If you read these, you will see that he (Turing, 1936, p. 230) is talking about “’computable ’numbers” 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 this definition. Rather, an approximation in finite time and space of pi can be considered Turing computable.
Turing’s paper is premised on that my Godel:
, ” Uber formal unentscheidbare Satze der Principia Mathematica und verwandter Systeme, I”. Monatsheftc Math. Phys., 38 (1931), 173-198
Unfortunately, if you do not have the mathematical background in the form of discrete maths that these authors were talking about, or other writing about, in that case, you are likely to make one of the many errors that people make around the definition of a Turing machine.
Turing had noted (1936, p.230) that the class of computable numbers was “nevertheless enumerable”. However, he did not state that the touring machine itself needed to be enumerable for this to be true.
Turing was extending the research of Church (1936), who was researching the concept of ‘effective calculability’. As Turing noted, effective calculability is functionally equivalent to Turing’s concept of ‘computability ’whilst these are each separately defined. For this reason, it has been called the Church-Turing problem. Each author created a solution with Church deriving his first.
Alonzo Church, “An unsolvable problem, of elementary number theory “, AmericanJ. of Math., 58 (1936), 345-363
2/3
Hennie (1965) investigated the concept of a single tape off-line Turing machine.
Hennie, F. C. (1965). One-tape, off-line Turing machine computations. Information and Control, 8(6), 553-578.
Such a machine and tape can be computed as needed and created in a structured manner that can be later produced to validate any single computable number. An example of how this can be reflected in bitcoin script would be creating a set of rules and mathematical processes that can computer any digital number on a tape that may then be processed. In this instance, we can analogise the tape to the bitcoin script. In this manner, you could imagine creating a single transaction as a single tape that is compiled and produced offline and used online in finite time.
Hartmanis (1968) provided a discussion around the complexity of single tape Turing machines. Whilst he noted that there is a sharp time-bound over nine regular sets of sequences, there are various forms of computational complexity that can be used to measure these forms of computation. Simultaneously, it is possible to determine the different complexity levels for these tapes compared to these tapes to multiple tape machines. From this, the various forms of computational complexity have been derived. So, the issue is now not whether a script is a Turing complete system but whether it is efficient. Of course, a single tape computation is inefficient, and that is not one that I would recommend but, it is feasible and possible to implement.
Hartmanis, J. (1968). Computational complexity of one-tape Turing machine computations. Journal of the ACM (JACM), 15(2), 325-339.
Shannon (1956) looked at the concept provided by Turing to make a mechanical machine or other an 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”. It was not Turing that stated that a Turing machine must be infinite but rather Shannon.
Shannon, C. E. (1956). A universal Turing machine with two internal states. In Automata Studies.(AM-34), Volume 34 (pp. 157-166). Princeton University Press.
Whilst Shannon produced some excellent engineering; he was not a mathematician. This is an important distinction because Turing (1936, p. 230) stated categorically that it was a machine that can calculate “the real numbers whose expressions as a decimal are calculable by finite means”.
Turing noted that the computing machine does not write more than a finite number of symbols (1936, p. 233). In this, the machine is unbounded, but it is not infinite. This is a significant and very important distinction that many non-mathematicians failed to comprehend. An unbounded machine is infinitely smaller than any infinite value.
Hopcroft and Ullman (1969, p. 168) investigated tape bounded Turing machines and followed up Shannon’s error of assuming an infinite working tape rather than an unbounded one. This is, unfortunately, laziness and should not have been done in this manner. You will note that they discuss the online and off-line versions of Turing machines and that they note that in the case of the off-line Turing machine that I mentioned above, the tape can be assumed not to loop. In this paper (1969, p. 169), you will note that the authors have removed the assumption of the machine halting for every input. Whilst this provides a form of machine, it is not more than a single example, and people take these for more than they are as examples and make them universal. Note that I’m not saying universal Turing machine here, which is a different thing again.
Hopcroft, J. E., & Ullman, J. D. (1969). Some results on tape-bounded Turing machines. Journal of the ACM (JACM), 16(1), 168-177.
3/3
However, suppose you do read the paper in full. In that case, you will see that the definition of a nondeterministic Turing machine that they present as a 6-Tuple (p. 169) is created using finite states, finite symbols, and finite. Therefore, it is not an infinite machine.
Although people use infinite and unbounded interchangeably, these are 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 definable in large, which differs from an infinite system which is indefinable a large.
The way to think about this 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. Moreover, you can do this as many times as is necessary. That remains a process that happens in finite time in finite space and hence never becomes infinite.
Note here that I have said in <space> “finite” and I have not said this in a manner that states it is a process which is “infinite”. This distinction is not mathematical but rather the error in noting in <space> finite differs from the English expression infinite.
An infeasible problem cannot be solved and has no solution. An unbounded problem may be calculated given sufficient time and memory space.
In a paper on paralysed computation, Juille and Pollack (1996) documented methodologies to create a multiple tape Turing machine that would be more efficient than a single tape transaction type that I have proposed above. In this, rather than a single transaction, you would run many transactions in parallel and only require that a single path is promoted as a solution. In this manner, you would not use a single transaction but rather an unbounded number of transactions that are computed as off-line Turing machines where you only send a single transaction to be recorded on the Blockchain that has been demonstrated (outside the Blockchain) to find the desired solution and to compute the problem correctly.
Juillé, H., & Pollack, J. B. (1996). Massively parallel genetic programming. In Advances in genetic programming: volume 2 (pp. 339-357).
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 this type) are extremely inefficient. Consequently, as I noted above in the paper by Juillé and Pollack (1996), the solution should be found in parallelised systems that compute many possibilities simultaneously rather than making a single unwieldy transaction tape. That stated, 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 and limit the size of the Blockchain.
The argument against bitcoin being Turing complete is that of transaction and block size limits. Given those limits, bitcoin is not a Turing complete system, but bitcoin wasn’t designed to be limited in that manner. Hence, whilst BTC is not Turing complete, bitcoin is.
McCarthy, J. (1956). The inversion of functions defined by Turing machines. In Automata Studies.(AM-34), Volume 34 (pp. 177-182). Princeton University Press.
It was a stream of consciousness from when I woke up
CSW
Sep 1, 2021
1/3
