Last update: January 12, 2022.

Kohtaro Tadaki (只木孝太郎) - Research on Algorithmic Dimensions, Algorithmic Randomness, and Their Extensions over Physics


Invention of "Algorithmic Dimensions" and Partial Randomness

  1. K. Tadaki. A generalization of Chaitin's halting probability Ω and halting self-similar sets. Hokkaido Mathematical Journal, Vol.31, pp.219-253, February 2002. doi:10.14492/hokmj/1350911778. (refereed, Received September 6, 2000 and Accepted January 24, 2001)
  2. K. Tadaki. Kolmogorov complexity and fractal sets. Bussei Kenkyu, Vol.74, No.1, pp.39-46, April 2000. (in Japanese)
  3. K. Tadaki. Algorithmic information theory and fractal sets. Proceedings of 1999 Workshop on Information-Based Induction Sciences (IBIS'99), pp.105-110, August 26-27, 1999, Syuzenji, Shizuoka, Japan. (refereed, in Japanese)

Statistical Mechanical Interpretation of Algorithmic Dimensions and Algorithmic Information Theory as a Whole: Temperature is Algorithmic Dimension !!

  1.  New! K. Tadaki. Algorithmic information theory and its statistical mechanical interpretation. Sugaku Expositions, Vol.33, No.1, pp.1-29, American Mathematical Society, 2020. (invited)
  2. K. Tadaki. A Statistical Mechanical Interpretation of Algorithmic Information Theory. SpringerBriefs in Mathematical Physics, Vol.36, Springer, Singapore, 2019. (invited and refereed)

    SMIAIT

    New book available now!
  3. K. Tadaki. Algorithmic information theory and its statistical mechanical interpretation. Sugaku, The Mathematical Society of Japan, Vol.67, No.1, pp.1-25, 2015. (invited, in Japanese)
  4. K. Tadaki. Phase transition and strong predictability. Proceedings of the Unconventional Computation & Natural Computation 2014 (UCNC 2014), Lecture Notes in Computer Science, Springer-Verlag, Vol.8553, pp.340-352, July 14-18, 2014, University of Western Ontario, Canada. (refereed) A Preliminary Draft Available from: CDMTCS Research Report Series, 436 or arXiv:1304.6858
  5. K. Tadaki. Recent developments in statistical mechanical interpretation of algorithmic information theory. Invited Talk at the 13th Asian Logic Conference (ALC2013), September 16-20, 2013, Guangzhou, China.
  6. K. Tadaki. A statistical mechanical interpretation of algorithmic information theory III: Composite systems and fixed points. Special Issue of the CiE 2010 Special Session on Computability of the Physical, Mathematical Structures in Computer Science, Vol.22, pp.752-770, 2012. (refereed)
  7. K. Tadaki. Fixed point theorems on partial randomness. Special Issue of the Symposium on Logical Foundations of Computer Science 2009, Annals of Pure and Applied Logic, Vol.163, pp.763-744, 2012. (refereed)
  8. K. Tadaki. Phase transition between unidirectionality and bidirectionality. Proceedings of the International Workshop on Theoretical Computer Science, Dedicated to Prof. Cristian S. Calude's 60th Birthday (WTCS 2012), Lecture Notes in Computer Science Festschrifts Series, Springer-Verlag, Vol.7160, pp.203-223, February 21-24, 2012, Auckland, New Zealand. (invited) An Earlier Full Version Available at CDMTCS Research Report Series, 406
  9. K. Tadaki. Robustness of statistical mechanical interpretation of algorithmic information theory. Proceedings of the 2011 IEEE Information Theory Workshop (ITW 2011), pp.237-241, October 16-20, 2011, Paraty, Brazil. (refereed)
  10. K. Tadaki. A Chaitin Ω number based on compressible strings. Special issue "Unconventional Computation 2010," Natural Computing, Vol.11, pp.117-128, 2012. (refereed)
  11. K. Tadaki. A Chaitin Ω number based on compressible strings. Eighth International Conference on Computability and Complexity in Analysis (CCA 2011), January 31-February 4, 2011, Cape Town, South Africa. (abstract refereed)
  12. K. Tadaki. A new representation of Chaitin Ω number based on compressible strings. Proceedings of the 9th International Conference on Unconventional Computation (UC 2010), Lecture Notes in Computer Science, Springer-Verlag, Vol.6079, pp.127-139, June 21-25, 2010, Tokyo, Japan. (refereed) An Earlier Full Version Available at CDMTCS Research Report Series, 380
  13. K. Tadaki. The Hausdorff dimension of the halting self-similar sets of T-universal prefix-free machines. Proceedings of the 2010 IEEE International Symposium on Information Theory (ISIT 2010), pp.1287-1291, June 13-18, 2010, Austin, Texas, USA. (refereed)
  14. K. Tadaki. A statistical mechanical interpretation of algorithmic information theory: Total statistical mechanical interpretation based on physical argument. Proceedings of Kyoto RIMS workshop: "Mathematical Aspects of Generalized Entropies and their Applications," Journal of Physics: Conference Series (JPCS), Vol.201, 012006 (10pp), February 2010. (refereed) See also http://www.icsd3.tj.chiba-u.jp/~rims2009/
  15. K. Tadaki. A statistical mechanical interpretation of algorithmic information theory III: Composite systems and fixed points. Proceedings of the 2009 IEEE Information Theory Workshop (ITW 2009), pp.354-358, October 11-16, 2009, Taormina, Sicily, Italy. (refereed) Final Draft Available at CDMTCS Research Report Series, 358
  16. K. Tadaki. Fixed points on partial randomness. Proceedings of the 6th Workshop on Fixed Points in Computer Science (FICS 2009), pp.100-107, September 12-13, 2009, Coimbra, Portugal. (refereed) Electronic Version Available here
  17. K. Tadaki. A statistical mechanical interpretation of algorithmic information theory. Invited Talk at Physics and Computation 2009, September 7-11, 2009, Ponta-Delgada, Azores, Portugal.
  18. K. Tadaki. Fixed points on partial randomness and composition of systems. The 11th Asian Logic Conference (ALC2009), June 22-27, 2009, National University of Singapore, Singapore. (abstract refereed)
  19. K. Tadaki. Fixed point theorems on partial randomness. Proceedings of the Symposium on Logical Foundations of Computer Science 2009 (LFCS'09), Lecture Notes in Computer Science, Springer-Verlag, Vol.5407, pp.422-440, January 3-6, 2009, Deerfield Beach, Florida, USA. (refereed) Extended Version Available at CDMTCS Research Report Series, 355
  20. K. Tadaki. Fixed point theorems on partial randomness. The 10th Asian Logic Conference (ALC 10), September 1-6, 2008, Kobe University, Kobe, Hyogo, Japan. (abstract refereed)
  21. K. Tadaki. A statistical mechanical interpretation of algorithmic information theory. Local Proceedings of the Computability in Europe 2008 (CiE 2008), pp.425-434, June 15-20, 2008, University of Athens, Greece. (refereed) Extended Version Available from: arXiv:0801.4194

Algorithmic Dimensions of Recursively Enumerable Reals

  1. K. Tadaki. Partial randomness and dimension of recursively enumerable reals. Proceedings of the 34st International Symposium on Mathematical Foundations of Computer Science (MFCS 2009), Lecture Notes in Computer Science, Springer-Verlag, Vol.5734, pp.687-699, August 24-28, 2009, Novy Smokovec, High Tatras, Slovakia. (refereed) Final Draft Available from: arXiv:0906.2812
  2. K. Tadaki. Equivalent characterizations of partial randomness for a recursively enumerable real. Conference on Computability, Complexity and Randomness, May 19-23, 2008, Institute of Mathematical Science, Nanjing University, Nanjing, China. Extended Version Available from: arXiv:0805.2691

An Operational Characterization of the Notion of Probability by Algorithmic Randomness -- An Extreme of the Frequency Interpretation of Probability

  1. K. Tadaki. An operational characterization of the notion of probability by algorithmic randomness and its applications. arXiv:1611.06201v2 [math.PR], December 2021.
  2. K. Tadaki. An operational characterization of the notion of probability by algorithmic randomness II: Discrete probability spaces. arXiv:1909.02854v1 [math.PR], August 2019.
  3. K. Tadaki. An operational characterization of the notion of probability by algorithmic randomness II: Discrete probability spaces. Presentation at the 15th Asian Logic Conference (ALC2017), July 10-14, 2017, Daejeon, Korea. (abstract refereed)
  4. K. Tadaki. An operational characterization of the notion of probability by algorithmic randomness and its application to cryptography. Proceedings of the 32nd Symposium on Cryptography and Information Security (SCIS2015), 2D4-3, January 20-23, 2015, Kokura, Japan, Copyright©2015 IEICE.
  5. K. Tadaki. An operational characterization of the notion of probability by algorithmic randomness. Proceedings of the 37th Symposium on Information Theory and its Applications (SITA2014), 5.4.1, pp.389-394, December 9-12, 2014, Unazuki, Toyama, Japan, Copyright©2014 IEICE.

A Refinement of Quantum Mechanics by Algorithmic Randomness: The Principle of Typicality -- Our world is typical among many coexisting worlds !!

  1.  New! K. Tadaki. A refinement of the argument of Bell's inequality versus quantum mechanics by algorithmic randomness. In: Masahiko Sakai (ed.), New Trends in Algorithms and Theory of Computation, RIMS Kôkyûroku, No.2154, April 2020.
  2. K. Tadaki. A refinement of quantum mechanics by algorithmic randomness. arXiv:1804.10174, April 2018.
  3. K. Tadaki. A refinement of quantum mechanics by algorithmic randomness. Presentation at Workshop: Quantum Contextuality in Quantum Mechanics and Beyond (QCQMB), June 4-5, 2017, Prague, Czech Republic. (abstract refereed)
  4. K. Tadaki. A refinement of quantum mechanics by algorithmic randomness and its application to quantum cryptography. Proceedings of 2017 Symposium on Cryptography and Information Security (SCIS2017), 4A1-2, January 24-27, 2017, Naha, Japan, Copyright©2017 IEICE.
  5. K. Tadaki. The principle of typicality. Presentation at Eleventh International Conference on Computability, Complexity and Randomness (CCR 2016), January 4-8, 2016, Honolulu, USA. (abstract refereed)
  6. K. Tadaki. A refinement of quantum mechanics by algorithmic randomness. Presentation at Quantum Computation, Quantum Information, and the Exact Sciences (QCOMPINFO2015), January 30-31, 2015, Ludwig-Maximilians-Universität München, Munich, Germany. (abstract refereed)
  7. K. Tadaki. Reformulating quantum mechanics by algorithmic randomness. Invited Talk at Ninth International Conference on Computability, Complexity and Randomness (CCR 2014), Institute for Mathematical Sciences, National University of Singapore, Singapore, June 9-13, 2014.
  8. K. Tadaki. A reformulation of quantum mechanics by algorithmic randomness. Presentation at the 30th Quantum Information Technology Symposium (QIT30), Toyoda Auditorium/Symposion, Nagoya University, Japan, May 12-13, 2014.

Extension of Universal Probability to POVM

  1. K. Tadaki. An extension of Chaitin's halting probability Ω to a measurement operator in an infinite dimensional quantum system. Mathematical Logic Quarterly, Vol.52, pp.419-438, 2006. (refereed) Preliminary Draft Available from: arXiv:quant-ph/0407023
  2. K. Tadaki. Upper bound by Kolmogorov complexity for the probability in computable quantum measurement. Proceedings of the 5th Conference on Real Numbers and Computers (RNC'5), pp.193-214, September 2003. (refereed) Preliminary Draft Available from: arXiv:quant-ph/0212071

Quantum Proving Without Giving the Proof

  1. C. S. Calude and K. Tadaki. Spectral representation of some computably enumerable sets with an application to quantum provability. Proceedings of the Unconventional Computation & Natural Computation 2013 (UCNC 2013), Lecture Notes in Computer Science, Springer-Verlag, Vol.7956, pp.43-54, July 1-5, 2013, Milano, Italy. (refereed) A Preliminary Version Available from: arXiv:1303.5502
  2. K. Tadaki. Quantum proving without giving the proof. CDMTCS Seminar, Department of Computer Science, The University of Auckland, March 4, 2013, Auckland, New Zealand.
  3. C. S. Calude and K. Tadaki. Spectral representation of some computably enumerable sets with an application to quantum provability. CDMTCS Research Report Series, 434, CDMTCS, The University of Auckland, New Zealand, March 2013.

Statistical Mechanical Interpretation of Noiseless Source Coding

  1. K. Tadaki. A statistical mechanical interpretation of instantaneous codes. Proceedings of the 2007 IEEE International Symposium on Information Theory (ISIT2007), pp.1906-1910, June 24-29, 2007, Nice, France. (refereed) Japanese Version appeared in Soryushiron Kenkyu, Vol.13 (2012) No.1.

Computational Power of Chaitin Ω Numbers

  1. K. Tadaki. Chaitin Ω numbers and halting problems. Proceedings of the Computability in Europe 2009 (CiE 2009), Lecture Notes in Computer Science, Springer-Verlag, Vol.5635, pp.447-456, July 19-24, 2009, Heidelberg, Germany. (refereed) Final Draft. An Earlier Full Version Available at CDMTCS Research Report Series, 359

The Random Oracle Methodology and Algorithmic Randomness

  1. K. Tadaki and N. Doi. Cryptography and algorithmic randomness. Theory of Computing Systems, Published online: 23 May 2014. (refereed) A Preliminary Draft Available from: CDMTCS Research Report Series, 435 or arXiv:1305.2391
  2. K. Tadaki. Cryptography and algorithmic randomness II. Eighth International Conference on Computability, Complexity and Randomness (CCR 2013), September 23-27, 2013, Moscow, Russia. (abstract refereed)
  3. K. Tadaki and N. Doi. Algorithmic randomness and the generic group model. Proceedings of the 30th Symposium on Cryptography and Information Security (SCIS2013), 3B3-1, January 22-25, 2013, Kyoto, Japan, Copyright©2013 IEICE.
  4. K. Tadaki and N. Doi. A secure instantiation of the random oracle by a computable function. Proceedings of the 35th Symposium on Information Theory and its Applications (SITA2012), 3.4.1, pp.212-217, December 11-14, 2012, Beppu, Oita, Japan, Copyright©2013 IEICE.
  5. K. Tadaki and N. Doi. Cryptography and algorithmic randomness. Seventh International Conference on Computability, Complexity and Randomness (CCR 2012), July 2-6, 2012, Cambridge, Great Britain. (abstract refereed)
  6. K. Tadaki and N. Doi. Instantiating the random oracle using a random real. Proceedings of the 29th Symposium on Cryptography and Information Security (SCIS2012), 2A3-4, January 30-February 2, 2012, Kanazawa, Japan, Copyright©2013 IEICE.

Properties of Optimal Prefix-Free Machines

  1. K. Tadaki. Properties of fibers of optimal prefix-free machines. Sixth International Conference on Computability, Complexity and Randomness (CCR 2011), January 31-February 4, 2011, Cape Town, South Africa. (abstract refereed)
  2. K. Tadaki. Properties of optimal prefix-free machines as instantaneous codes. Proceedings of the 2010 IEEE Information Theory Workshop (ITW 2010 Dublin), August 30 - September 3, 2010, Dublin, Ireland. (refereed) Final Draft Available at CDMTCS Research Report Series, 389

Universal Probability and Entropy

  1. K. Tadaki. The Tsallis entropy and the Shannon entropy of a universal probability. Proceedings of the 2008 IEEE International Symposium on Information Theory (ISIT 2008), pp.2111-2115, July 6-11, 2008, Toronto, Canada. (refereed) Final Draft Available from: arXiv:0805.0154

    中部大学生のための “基本情報技術者試験” 受験勉強の方法

    中部大学生のための “応用情報技術者試験” 受験勉強の方法

    中部大学生のための “情報処理安全確保支援士試験” 受験勉強の方法(逐次追加)


Kohtaro Tadaki
Department of Computer Science, College of Engineering, Chubu University
1200 Matsumoto-cho, Kasugai-shi, Aichi 487-8501, Japan
External Researcher, CDMTCS, The University of Auckland, New Zealand
Contact: kohtarotadaki_at_gmail.com