{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:10:45Z","timestamp":1760202645283},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2013,10,3]],"date-time":"2013-10-03T00:00:00Z","timestamp":1380758400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2015,4]]},"DOI":"10.1007\/s00224-013-9507-7","type":"journal-article","created":{"date-parts":[[2013,10,2]],"date-time":"2013-10-02T09:33:43Z","timestamp":1380706423000},"page":"439-464","source":"Crossref","is-referenced-by-count":4,"title":["Feasible Analysis, Randomness, and Base Invariance"],"prefix":"10.1007","volume":"56","author":[{"given":"Santiago","family":"Figueira","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andr\u00e9","family":"Nies","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2013,10,3]]},"reference":[{"key":"9507_CR1","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1016\/0304-3975(87)90053-3","volume":"51","author":"K. Ambos-Spies","year":"1987","unstructured":"Ambos-Spies, K., Fleischhack, H., Huwig, H.: Diagonalizations over polynomial time computable sets. Theor. Comput. Sci. 51, 177\u2013204 (1987)","journal-title":"Theor. Comput. Sci."},{"key":"9507_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/3-540-18170-9_149","volume-title":"CSL","author":"K. Ambos-Spies","year":"1987","unstructured":"Ambos-Spies, K., Fleischhack, H., Huwig, H.: Diagonalizing over deterministic polynomial time. In: CSL. Lecture Notes in Computer Science, vol. 329, pp. 1\u201316 (1987)"},{"key":"9507_CR3","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1016\/S0304-3975(95)00260-X","volume":"172","author":"K. Ambos-Spies","year":"1997","unstructured":"Ambos-Spies, K., Terwijn, S., Zheng, X.: Resource bounded randomness and weakly complete problems. Theor. Comput. Sci. 172, 195\u2013207 (1997)","journal-title":"Theor. Comput. Sci."},{"key":"9507_CR4","doi-asserted-by":"crossref","first-page":"947","DOI":"10.1016\/S0304-3975(01)00170-0","volume":"270","author":"V. Becher","year":"2002","unstructured":"Becher, V., Figueira, S.: An example of a computable absolutely normal number. Theor. Comput. Sci. 270, 947\u2013958 (2002). doi: 10.1016\/S0304-3975(01)00170-0","journal-title":"Theor. Comput. Sci."},{"issue":"1\u20133","key":"9507_CR5","doi-asserted-by":"crossref","first-page":"126","DOI":"10.1016\/j.tcs.2007.02.022","volume":"377","author":"V. Becher","year":"2007","unstructured":"Becher, V., Figueira, S., Picchi, R.: Turing\u2019s unpublished algorithm for normal numbers. Theor. Comput. Sci. 377(1\u20133), 126\u2013138 (2007)","journal-title":"Theor. Comput. Sci."},{"key":"9507_CR6","doi-asserted-by":"crossref","unstructured":"Becher, V., Heiber, P., Slaman, T.A.: A polynomial-time algorithm for computing absolutely normal numbers. Manuscript (2013)","DOI":"10.1016\/j.ic.2013.08.013"},{"key":"9507_CR7","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1007\/BF03019651","volume":"27","author":"E. Borel","year":"1909","unstructured":"Borel, E.: Les probabilit\u00e9s d\u00e9nombrables et leurs applications arithm\u00e9tiques. Rend. Circ. Mat. Palermo 27, 247\u2013271 (1909)","journal-title":"Rend. Circ. Mat. Palermo"},{"key":"9507_CR8","unstructured":"Brattka, V., Miller, J.S., Nies, A.: Randomness and differentiability (2011, to appear)"},{"issue":"3","key":"9507_CR9","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1016\/0022-314X(86)90034-X","volume":"24","author":"G. Brown","year":"1986","unstructured":"Brown, G., Moran, W., Pearce, C.E.M.: A decomposition theorem for numbers in which the summands have prescribed normality properties. J. Number Theory 24(3), 259\u2013271 (1986). doi: 10.1016\/0022-314X(86)90034-X","journal-title":"J. Number Theory"},{"key":"9507_CR10","doi-asserted-by":"crossref","first-page":"44","DOI":"10.1007\/3-540-58131-6_37","volume-title":"Results and Trends in Theoretical Computer Science","author":"C.S. Calude","year":"1994","unstructured":"Calude, C.S., J\u00fcrgensen, H.: Randomness as an invariant for number representations. In: Maurer, J.K.H., Rozenberg, G. (eds.) Results and Trends in Theoretical Computer Science, pp. 44\u201366. Springer, Berlin (1994)"},{"key":"9507_CR11","doi-asserted-by":"crossref","first-page":"254","DOI":"10.1112\/jlms\/s1-8.4.254","volume":"8","author":"D.G. Champernowne","year":"1933","unstructured":"Champernowne, D.G.: The construction of decimals in the scale of ten. J. Lond. Math. Soc. 8, 254\u2013260 (1933)","journal-title":"J. Lond. Math. Soc."},{"issue":"2","key":"9507_CR12","doi-asserted-by":"crossref","first-page":"481","DOI":"10.4007\/annals.2008.167.481","volume":"167","author":"B. Green","year":"2008","unstructured":"Green, B., Tao, T.: The primes contain arbitrarily long arithmetic progressions. Ann. Math. 167(2), 481\u2013547 (2008)","journal-title":"Ann. Math."},{"key":"9507_CR13","doi-asserted-by":"crossref","first-page":"796","DOI":"10.1007\/BFb0055103","volume-title":"Automata, Languages and Programming","author":"P. Hertling","year":"1998","unstructured":"Hertling, P., Weihrauch, K.: Randomness space. In: Automata, Languages and Programming, pp. 796\u2013807. Springer, Berlin (1998)"},{"key":"9507_CR14","unstructured":"Hitchcock, J., Mayordomo, E.: Base invariance of feasible dimension. Manuscript (2012)"},{"issue":"6","key":"9507_CR15","doi-asserted-by":"crossref","first-page":"1100","DOI":"10.1137\/0219076","volume":"19","author":"J.H. Lutz","year":"1990","unstructured":"Lutz, J.H.: Category and measure in complexity classes. SIAM J. Comput. 19(6), 1100\u20131131 (1990)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"9507_CR16","doi-asserted-by":"crossref","first-page":"220","DOI":"10.1016\/0022-0000(92)90020-J","volume":"44","author":"J.H. Lutz","year":"1992","unstructured":"Lutz, J.H.: Almost everywhere high nonuniform complexity. J. Comput. Syst. Sci. 44(2), 220\u2013258 (1992)","journal-title":"J. Comput. Syst. Sci."},{"key":"9507_CR17","unstructured":"Lutz, J., Mayordomo, E.: Construction of an absolutely normal real number in polynomial time. Manuscript (2012)"},{"key":"9507_CR18","doi-asserted-by":"crossref","first-page":"602","DOI":"10.1016\/S0019-9958(66)80018-9","volume":"9","author":"P. Martin-L\u00f6f","year":"1966","unstructured":"Martin-L\u00f6f, P.: The definition of random sequences. Inf. Control 9, 602\u2013619 (1966)","journal-title":"Inf. Control"},{"key":"9507_CR19","doi-asserted-by":"crossref","DOI":"10.1093\/acprof:oso\/9780199230761.001.0001","volume-title":"Computability and Randomness","author":"A. Nies","year":"2009","unstructured":"Nies, A.: Computability and Randomness. Clarendon Press, Oxford (2009)"},{"key":"9507_CR20","doi-asserted-by":"crossref","first-page":"661","DOI":"10.2140\/pjm.1960.10.661","volume":"10","author":"W.M. Schmidt","year":"1960","unstructured":"Schmidt, W.M.: On normal numbers. Pac. J. Math. 10, 661\u2013672 (1960)","journal-title":"Pac. J. Math."},{"key":"9507_CR21","doi-asserted-by":"crossref","first-page":"246","DOI":"10.1007\/BF01694181","volume":"5","author":"C.P. Schnorr","year":"1971","unstructured":"Schnorr, C.P.: A unified approach to the definition of a random sequence. Math. Syst. Theory 5, 246\u2013258 (1971)","journal-title":"Math. Syst. Theory"},{"key":"9507_CR22","series-title":"Lecture Notes in Mathematics","doi-asserted-by":"crossref","DOI":"10.1007\/BFb0112458","volume-title":"Zuf\u00e4lligkeit und Wahrscheinlichkeit","author":"C.P. Schnorr","year":"1971","unstructured":"Schnorr, C.P.: Zuf\u00e4lligkeit und Wahrscheinlichkeit. Lecture Notes in Mathematics, vol. 218 (1971)"},{"key":"9507_CR23","first-page":"127","volume":"45","author":"W. Sierpinski","year":"1917","unstructured":"Sierpinski, W.: D\u00e9monstration \u00e9l\u00e9mentaire du th\u00e9or\u00e8me de M. Borel sur les nombres absolument normaux et d\u00e9termination effective d\u2019un tel nombre. Bull. Soc. Math. Fr. 45, 127\u2013132 (1917)","journal-title":"Bull. Soc. Math. Fr."},{"key":"9507_CR24","unstructured":"Silveira, J.: Invariancia por cambio de base de la aleatoriedad computable y la aleatoriedad con recursos acotados. Ph.D. thesis, University of Buenos Aires (2011). Advisor: Santiago Figueira. Unpublished"},{"key":"9507_CR25","doi-asserted-by":"crossref","first-page":"536","DOI":"10.1007\/3-540-48321-7_45","volume-title":"Proceedings of the 12th International Symposium on Fundamentals of Computation Theory, FCT \u201999","author":"L. Staiger","year":"1999","unstructured":"Staiger, L.: The Kolmogorov complexity of real numbers. In: Proceedings of the 12th International Symposium on Fundamentals of Computation Theory, FCT \u201999, pp. 536\u2013546. Springer, London (1999). http:\/\/dl.acm.org\/citation.cfm?id=647899.740968"},{"key":"9507_CR26","first-page":"117","volume-title":"Collected Works of A.M. Turing: Pure Mathematics","author":"A.M. Turing","year":"1992","unstructured":"Turing, A.M.: A note on normal numbers. In: Britton, J. (ed.) Collected Works of A.M. Turing: Pure Mathematics, pp. 117\u2013119. North Holland, Amsterdam (1992)"},{"key":"9507_CR27","unstructured":"Wang, Y.: Randomness and complexity. Ph.D. thesis, University of Heidelberg (1996)"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-013-9507-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-013-9507-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-013-9507-7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,7,28]],"date-time":"2019-07-28T05:45:19Z","timestamp":1564292719000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-013-9507-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,10,3]]},"references-count":27,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2015,4]]}},"alternative-id":["9507"],"URL":"https:\/\/doi.org\/10.1007\/s00224-013-9507-7","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,10,3]]}}}