Last update: December 19, 2014.

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


    教科書および講義ノート


An Operational Characterization of the Notion of Probability by Algorithmic Randomness

  1. K. Tadaki. An operational characterization of the notion of probability by algorithmic randomness and its application to cryptography. To appear in the Proceedings of the 32nd Symposium on Cryptography and Information Security (SCIS2015), 2D4-3, January 20-23, 2015, Kokura, Japan.
  2. 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©2013 IEICE.

A Refinement of Quantum Mechanics by Algorithmic Randomness

  1. K. Tadaki. A refinement of quantum mechanics by algorithmic randomness. Accepted for 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)
  2. 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.
  3. 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.

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.

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.

Statistical Mechanical Interpretation of Algorithmic Information Theory

  1. 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
  2. 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.
  3. 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)
  4. 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)
  5. 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
  6. 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)
  7. K. Tadaki. A Chaitin Ω number based on compressible strings. Special issue "Unconventional Computation 2010," Natural Computing, Vol.11, pp.117-128, 2012. (refereed)
  8. 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)
  9. 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
  10. 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)
  11. 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/
  12. 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
  13. 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
  14. 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.
  15. 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)
  16. 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
  17. 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)
  18. 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

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.

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

Dimension and Partial Randomness

  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
  3. K. Tadaki. A generalization of Chaitin's halting probability Ω and halting self-similar sets. Hokkaido Mathematical Journal, Vol.31, pp.219-253, February 2002. (refereed) Final Draft Available from: arXiv:nlin/0212001v1
  4. 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)

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

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

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

Kohtaro Tadaki
Research and Development Initiative, Chuo University
1-13-27 Kasuga, Bunkyo-ku, Tokyo 112-8551, Japan
External Researcher, CDMTCS, The University of Auckland, New Zealand
Contact: kohtarotadaki_at_gmail.com