Details of the Researcher

PHOTO

Takeshi Yamazaki
Section
Graduate School of Science
Job title
Associate Professor
Degree

  • 博士（理学）（東北大学）

  • 修士（理学）（東北大学）

Professional Memberships 3

  • 国際数理科学協会

  • The association for Symbolic Logic

  • 日本数学会

Research Interests 4

  • 再帰理論

  • 超準モデル

  • 二階算術

  • 逆数学

Research Areas 2

  • Natural sciences / Applied mathematics and statistics /

  • Natural sciences / Basic mathematics /

Papers 15

  1. Reverse mathematics and order theoretic fixed point theorems Peer-reviewed

    Takashi Sato, Takeshi Yamazaki

    Archive for Mathematical Logic　56　(3 and 4)　385-396　2017/03

  2. COMMUTING QUANTUM CIRCUITS WITH FEW OUTPUTS ARE UNLIKELY TO BE CLASSICALLY SIMULATABLE Peer-reviewed

    Yasuhiro Takahashi, Seiichiro Tani, Takeshi Yamazaki, Kazuyuki Tanaka

    QUANTUM INFORMATION & COMPUTATION　16　(3-4)　251-270　2016/03

    ISSN： 1533-7146

  3. Commuting Quantum Circuits with Few Outputs are Unlikely to be Classically Simulatable Peer-reviewed

    Yasuhiro Takahashi, Seiichiro Tani, Takeshi Yamazaki, Kazuyuki Tanaka

    COMPUTING AND COMBINATORICS　9198　223-234　2015

    DOI： 10.1007/978-3-319-21398-9_18 　

    ISSN： 0302-9743

  4. Hardness of classically simulating quantum circuits with unbounded Toffoli and fan-out gates. Peer-reviewed

    Yasuhiro Takahashi, Kazuyuki Tanaka, Takeshi Yamazaki

    Quantum Inf. Comput.　14　(13-14)　1149-1164　2015

    DOI： 10.26421/QIC14.13-14-7 　

  5. On the Ramseyan factorization theorem Peer-reviewed

    Shota Murakami, Takeshi Yamazaki, Keita Yokoyama

    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)　8493　324-332　2014

    Publisher: Springer Verlag

    DOI： 10.1007/978-3-319-08019-2_33 　

    ISSN： 1611-3349 0302-9743

  6. Hardness of classically simulating quantum circuits with unbounded Toffoli and fan-out gates Peer-reviewed

    Yasuhiro Takahashi, Takeshi Yamazaki, Kazuyuki Tanaka

    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)　8087　801-812　2013

    DOI： 10.1007/978-3-642-40313-2_70 　

    ISSN： 0302-9743 1611-3349

  7. Relative randomness for Martin-Löf random sets Peer-reviewed

    NingNing Peng, Kojiro Higuchi, Takeshi Yamazaki, Kazuyuki Tanaka

    HOW THE WORLD COMPUTES, Lecture Notes in Comput. Sci.　7318　581-588　2012/06

    DOI： 10.1007/978-3-642-30870-3_58 　

    ISSN： 0302-9743 1611-3349

  8. Generalization of complexity oscillations in infinite sequences Peer-reviewed

    ChenGuang Liu, Kazuyuki Tanaka, Takeshi Yamazaki

    4th International Conference on Natural Computation (ICNC'08)　299-303　2008/10

    DOI： 10.1109/ICNC.2008.915 　

  9. The quasi-equivalence between the definitions of partial randomness Peer-reviewed

    ChenGuang Liu, Kazuyuki Tanaka, Takeshi Yamazaki

    4th International Conference on Natural Computation (ICNC'08)　371-375　2008/10

    DOI： 10.1109/ICNC.2008.916 　

  10. Does truth-table of linear norm reduce the one-query tautologies to a random oracle? Peer-reviewed

    Masahiro Kumabe, Toshio Suzuki, Takeshi Yamazaki

    ARCHIVE FOR MATHEMATICAL LOGIC　47　(2)　159-180　2008/07

    DOI： 10.1007/s00153-008-0076-4 　

    ISSN： 1432-0665

  11. Reverse mathematics and weak systems of 0-1 strings for feasible analysis Peer-reviewed

    Takeshi Yamazaki

    Reverse mathematics 2001　2005

  12. Manipulating the reals in RCAo Peer-reviewed

    Kazuyuki Tanaka, Takeshi Yamzaki

    Reverse mathematics 2001　2005

  13. Uniform versions of some axioms of second order arithmetic Peer-reviewed

    N Sakamoto, T Yamazaki

    MATHEMATICAL LOGIC QUARTERLY　50　(6)　587-593　2004

    DOI： 10.1002/malq.200310122 　

    ISSN： 0942-5616

  14. Some conservation results on weak König's lemma Peer-reviewed

    Stephen G. Simpson, Kazuyuki Tanaka, Takeshi Yamazaki

    Annals of Pure and Applied Logic　118　(1-2)　87-114　2002/12

    DOI： 10.1016/S0168-0072(01)00121-X 　

    ISSN： 0168-0072

  15. A non-standard construction of Haar measure and weak König's lemma Peer-reviewed

    Kazuyuki Tanaka, Takeshi Yamazaki

    Journal of Symbolic Logic　65　(1)　173-186　2000

    Publisher: Association for Symbolic Logic

    DOI： 10.2307/2586530 　

    ISSN： 0022-4812

Show all ︎Show first 5

Misc. 1

  1. Truth-table reductions and minimum sizes of forcing conditions

    Masahiro Kumabe, Toshio Suzuki, Takeshi Yamazaki

    数理解析研究所講究録　1553　9--14　2007

Books and Other Publications 2

  1. ゲーデルと２０世紀の論理学３不完全性定理と算術の体系

    田中一之, 鹿島亮, 山崎武, 白旗優

    東京大学出版会　2007/03/15

  2. 確かさを求めて 数学の基礎についての哲学論考

    田中一之監訳

    2007/01/15

Presentations 9

  1. WKL0とPRAのPi^0_2保存性

    AIG 4　2016/01/10

  2. Reverse Mathematics and Equilibria of Continuous Games International-presentation

    Computability Theory and Foundations of Mathematics 2015　2015/09/07

  3. Some Fixed Point Theorems and Reverse Mathematics II International-presentation

    JSPS-NUS Joint Workshop in Mathematical Logic and Foundations of Mathematics　2015/03/06

  4. Some Fixed Point Theorems and Reverse Mathematics International-presentation

    IMS-JSPS joint workshop　2014/09/01

  5. Filters and Reverse Mathematics International-presentation

    Workshop on Reverse Mathematics and Type Theory　2013/03

  6. Reverse Mathematics and Commutative Ring Theory International-presentation

    Computability Theory and Foundations of Mathematics　2013/02

  7. Infinite Planar graphs and Reverse Mathematics International-presentation

    Logic seminar in Gent University　2011/09/02

  8. 二階算術における代数学の展開

    佐藤隆, 横山啓太

    日本数学会　2007/09

  9. More on the partial randomness of reals

    ChenGuang Liu

    日本数学会　2007/09

Show all Show first 5

Research Projects 9

  1. 逆数学 Competitive

    System: The Other Research Programs

    2000/04 - Present

  2. 二階算術のモデルについて Competitive

    System: The Other Research Programs

    2000/04 - Present

  3. Computational Aspects of Randomness and Their Structural Analysis via Nonstandard Methods

    TANAKA Kazuyuki, YAMAZAKI Takeshi, SUZUKI Toshio, TADAKI Kohtaro, KURODA Satoru, YOKOYAMA Keita

    Offer Organization: Japan Society for the Promotion of Science

    System: Grants-in-Aid for Scientific Research

    Category: Grant-in-Aid for Scientific Research (B)

    Institution: Tohoku University

    2011/04/01 - 2015/03/31

    More details Close

    The main aim of this research is to cultivate systematic understanding of randomness via various logical methods such as non-standard analysis so that computational aspects of basic concepts about probability and games deeply correlated to randomness should be clarified. We focus on the following five topics. (1) Setting a logical framework of nonstandard arguments for constructive measure theory. (2) Investigating computational structures by randomness notions. (3) Determining the equilibrium points of game trees. (4) Elucidating physical meaning of Chaitin’s Omega. (5) Logical treatments for determinacy of games.

  4. Towards construction of a new computation model based on quantum mechanics

    TANAKA Kazuyuki, TADAKI Kohtaro, YAMAZAKI Kakeshi

    Offer Organization: Japan Society for the Promotion of Science

    System: Grants-in-Aid for Scientific Research

    Category: Grant-in-Aid for Challenging Exploratory Research

    Institution: Tohoku University

    2011 - 2012

    More details Close

    In this research, we consider new measurement-based quantum computation models, and study their classical simulabiliy and complexity effects. Among others, we show that some constant-depth quantum circuits followed by unbounded fan-out gates can not be classically simulated in polynomial time. We also propose a new type of quantum computer which represents computable sets via the measurement of an observable in an infinite dimensional state space.

  5. Reverse Mathematics and Models of Arithmetic

    YAMAZAKI Takeshi

    Offer Organization: Japan Society for the Promotion of Science

    System: Grants-in-Aid for Scientific Research

    Category: Grant-in-Aid for Young Scientists (B)

    Institution: Tohoku University

    2007 - 2010

    More details Close

    Reverse mathematics is the research program to classify mathematical theorems according to which set existence axioms are needed to prove them. In this poin of view, we got the following three kinds of results: (1) a new method to construct omaga-model and its application to conservativity result; (2) new notions of randomness and new systems corresponding to them; (3) new reverse mathematical results on Discrete Mathematics and Ring Theory.

  6. Marriage of non-standard analysis and computability theory toward the light of algorithmic randomness

    TANAKA Kazuyuki, YAMAZAKI Takeshi, HATTORI Tetsuya, OZAWA Masanao, SUZUKI Toshio, KURODA Satoru, KUMABE Masahiro, KASHIMA Ryo

    Offer Organization: Japan Society for the Promotion of Science

    System: Grants-in-Aid for Scientific Research

    Category: Grant-in-Aid for Scientific Research (B)

    Institution: Tohoku University

    2007 - 2010

    More details Close

    The main purpose of this research is to lay a logical foundation for non-standard arguments, which have been developed in abstract set theory traditionally. Basing non-standard methods on weak subsystems of second order arithmetic connected with computability, we can obtain constructive contents of propositions by such methods. To device non-standard methods for second order arithmetic, we need to investigate their non-standard models, which are indeed sets of reals (infinite sequences). Amongst the sets of reals, many contain many random elements, which we also explore in this study.

  7. 逆数学および算術の体系に関する研究

    山崎 武

    Offer Organization: 日本学術振興会

    System: 科学研究費助成事業

    Category: 若手研究(B)

    2004 - 2006

    More details Close

    二階算術の枠組みにおいて、どれくらいの強さの集合存在公理図式があれば証明されるのに必要十分であるかという観点から、数学の定理を分類する試みを逆数学という.より厳密には、計算機が使える程度の数学領域に対応する形式体系のもとで、吉の数学の定理とある集合存在公理図式の同値性を証明する.したがって、その逆数学はここの具体的な数学対象の計算論及び再帰理論的な性質の研究と関係している.本年度は次の4点に着目しながら逆数学及び再帰理論からの応用を中心にその周辺の研究を行った. (1)無限群に関する再帰理論的研究.無念軍の中心の存在と算術的内包公理の同値性の別証をはじめとする基礎的な事柄についての成果をいくつか得られたが,発展的内容にっいては今後の課題である. (2)保存性に関する二階算術のモデル論的研究.RCAの任意のcountable modelは1つの集合で生成されるRCAのオメガーモデルであるという以前の結果を利用し,RCA + collection schemeはRCAの算術的論理式に関する保存的拡大であることの簡単な証明を得た.現在は,RCA以上の体系とcollection schemeのベーターモデルにおける関係を考察中である. (3)一般的な位相構造における逆数学.従来の逆数学では言語の制限上,位相空間としては完備可分距離空間のみが扱われてきた.しかし、Stone spaceなどもRCAよりも強い体系においては扱える.そこで、より一般的な観点から位相構造に関する逆数学を調べた. (4)部分的ランダム性の考察.0-1無限列のランダム性には様々な定義があるが,同じような形でそれらの部分的な条件を緩めるとその同値性がこわれることが知られている.そこで、劉晨光氏と共に、このような部分的ランダム性のいくつかの新しい概念を導入し、それらの分類を行っている.また、ランダム性とラムゼイの定理との関係、それに対応する逆数学及び二階算術のモデルの特性も調べている. また、逆数学に関する話題を自身の研究内容も踏まえて、田中一之編「ゲーデルと20世紀の論理学 3 不完全性定理と算術の大系」第二部「二階算術ち逆数学」を書いた.

  8. Computability of discontinuous functions-Towards its paradigm

    YASUGI Mariko, TSUJII Yoshiki, MORI Takakazu, YAMADA Shuji, TSUIKI Hideki, HAYASHI Susumu

    Offer Organization: Japan Society for the Promotion of Science

    System: Grants-in-Aid for Scientific Research

    Category: Grant-in-Aid for Scientific Research (B)

    Institution: Kyoto Sangyo University

    2004 - 2006

    More details Close

    In studying computability of some real functions which are discontinuous with respect to the Euclidean metric, the most useful and natural METHOD is uniformization of the domain of a function by isolating the discontinuous points. A general theory of the effective uniform space, especially the space of Fine metric, has been clarified. For the computability problem of a function sequence whose functions have different discontinuity points, a theory of the effective sequence of uniformities and its limit has been developed. Admitting limiting recursive functions in characterizing the image of a computable sequence of elements by a discontinuous function is another theory. In a natural setting, these two theories are equivalent. We can claim that the theory of the effective uniformity (the sequence of effective uniformities) is the fundamental method for the computability of some discontinuous functions. Limiting recursion is equivalent with Sigma^0_1 excluded middle. The relative strength between Sigma^0_1 excluded middle and other semi-constructive principles have been worked out. As for functional analysis, effectivization of various theorems, mainly on the Banach space, has made progress. A representation of real numbers in terms of {0,1,Bottom},characterizing the computability of real numbers has been studied. Some counter-examples have been constructed :a function sequence which is sequentially computable but has no effectively continuous points and a function which is Banach-Mazur computable but is not Markov computable. In applications, dynamics of double rotation maps, description of the inverse problem in multi-sectorial growth theory, the computability problem of fractals with infinitely many contraction maps, reorganization of hardware and software for discovery of non-trivial knots have been studied.

  9. Comparative studies on nonstandard methods and constructive methods

    TANAKA Kasuyuki, AKAMA Yohji, TAKEDA Masayoshi, MORITA Yasuo, YAMAZAK Takeshi

    Offer Organization: Japan Society for the Promotion of Science

    System: Grants-in-Aid for Scientific Research

    Category: Grant-in-Aid for Scientific Research (C)

    Institution: Tohoku University

    2001 - 2003

    More details Close

    Second order arithmetic was first introduced by D.Hilbert around 1920's to set a firm foundation of analysis. Among many different formalizations of second order arithmetic, RCA_0 and WKL_0 are particularly important with respect to Hilbert's program. Tanaka and Yamazaki, in cooperation with Simpson, proved that one can eliminate, the compactness argument from proofs for a certain sort of theorems in WKL_0, namely WKL_0 is conservative over RCA_0 for the formulas in a certain form. They also showed that the bounded dependent choice scheme, which is often used in the computation of real numbers, can not be eliminated likewise. Thus, Tanaka and Yamazaki constructed an appropriate truth definition for the real number system via the quantifier elimination method, by which one can manipulate the reals freely in RCA_0. By sophisticating this argument, Tanaka, jointly with Sakamoto, could prove Hilbert's Nullstellensatz within RCA_0. Yamazaki and Sakamoto also studied uniform versions of WKL_0 and other statements within higher order arithmetic. Yamazaki investigated the logical strength of completeness theorems for intuitionistic logic.

Show all Show first 5

Social Activities 1

  1. 数学基礎論サマースクール2006

    2006/08/31 - 2006/09/02

    More details Close

    証明論に関する専門家を講師として，入門的な内容から最新の話 題まで様々な講義をする．二階算術のモデルについての基礎的な事柄と現在行っている研究の基になる考えについて解説した．