Bitcoin and the Theory of Computation

  IJCTT-book-cover
 
         
 
© 2021 by IJCTT Journal
Volume-69 Issue-10
Year of Publication : 2021
Authors : Martin V. Sewell
DOI :  10.14445/22312803/IJCTT-V69I10P107

How to Cite?

Martin V. Sewell, "Bitcoin and the Theory of Computation," International Journal of Computer Trends and Technology, vol. 69, no. 10, pp. 43-46, 2021. Crossref, https://doi.org/10.14445/22312803/IJCTT-V69I10P107

Abstract
Bitcoin is assessed from the perspective of the theory of computation. Specifically, the computational power of Bitcoin is determined in the context of both computability theory and automata theory. In computability theory, there exists a hierarchy of functions, from the most powerful to the least powerful: partial recursive, total recursive, primitive recursive, elementary recursive, and lower elementary recursive. Whilst in automata theory, there exists a hierarchy of automata, from the most to least powerful: Turing machine, linear bounded automaton, non-deterministic pushdown automaton, deterministic pushdown automaton, and finite automaton. In both instances, Bitcoin lies within or below the least powerful category. Bitcoin is essentially a finite automaton that employs a scripting language for data manipulation that is even less powerful than a lower elementary recursive programming language. Bitcoin is not Turing-complete, either in whole or in part. For security reasons, Bitcoin was designed to be only as powerful as necessary.

Keywords
Automata theory, Bitcoin, Computability theory, Theory of computation, Turing-complete.

Reference

[1] S. Nakamoto, Bitcoin: A peer-to-peer electronic cash system, https://bitcoin.org/bitcoin.pdf (bitcoin.org) (2008).
[2] Wikipedia, ELEMENTARY, https://en.wikipedia.org/wiki/ELEMENTARY, (2021).
[3] A. R.Meyer, and D. M.Ritchie., The complexity of loop programs, in S. Rosenthal, Ed. ACM ’67: Proceedings of the 1967 22nd national conference. New York: Association for Computing Machinery, (1967) 465–469.
[4] D. R.Hofstadter, Gödel, Escher, Bach: An eternal golden braid. New York: Basic Books, (1979).
[5] W. Ackermann, Zum Hilbertschen Aufbau derreellen Zahlen, Mathematische Annalen, 99(1) (1928)118–133.
[6] A. M.Turing, On computable numbers, with an application to the Entscheidungs problem, Proceedings of the London Mathematical Society, s2-42 (1) (1937) 230–265.
[7] A. M.Turing, On computable numbers, with an application to the Entscheidungs problem. A correction, Proceedings of the London Mathematical Society, s2-43 (1) (1938) 544–546.
[8] M. Blum, On the size of machines, Information and Control, 11(3) (1967) 257–265.
[9] G.Wood, Ethereum: A secure decentralized generalized transaction ledger, https://ethereum.github.io/yellowpaper/paper.pdf., (2020).
[10] J. E.Hopcroft, R. Motwani, &J. D.Ullman., Introduction to automata theory, languages, and computation,3rd ed. Harlow: Pearson, (2014).
[11] Wikipedia, Linear bounded automaton, https://en.wikipedia.org/wiki/Linear_bounded_automaton, (2020).