Concepedia

Deterministic Turing Machines

A Deterministic Turing Machine is a theoretical computational model in which, for any given state and tape symbol, there exists exactly one defined transition rule that uniquely determines the next state, the output symbol, and the direction of head movement, distinguishing it from nondeterministic variants by enforcing a single computation path.

89

Publications

6.1K

Citations

119

Authors

91

Institutions

Publications per year

2017–2026

1

Parents

Publications

89

Relationships between nondeterministic and deterministic tape complexities

Walter J. Savitch · Journal of Computer and System Sciences · 1970 · 1.4K citations

, , +5

Computational Complexity of Probabilistic Turing Machines

John Gill · SIAM Journal on Computing · 1977 · 694 citations

, , +17

Computationally Related Problems

Sartaj Sahni · SIAM Journal on Computing · 1974 · 362 citations

, , +16

A Catalog of Complexity Classes.

David S. Johnson · 1990 · 270 citations

, , +12

On Time Versus Space

John E. Hopcroft, Wolfgang J. Paul, Leslie G. Valiant · Journal of the ACM · 1977 · 255 citations · Full text

, , +17

1–5 of 89

Authors

119

  1. ES
    Endre Szemerédi

    Hungarian Academy of Sciences, Hungary

    4 publications · 191 citations

    4

    h-index

  2. RK
    Ravi Kannan

    Carnegie Mellon University, United States

    4 publications · 94 citations

    4

    h-index

  3. HZ
    Héctor Zenil

    Karolinska Institutet, Sweden

    4 publications · 132 citations

    4

    h-index

  4. JD
    Jean-Paul Delahaye

    Laboratoire d'Informatique Fondamentale de Lille, France

    4 publications · 132 citations

    4

    h-index

  5. WM
    Wolfgang Maass

    Graz University of Technology, Austria

    4 publications · 124 citations

    4

    h-index

1–5 of 119

Institutions

91

  1. University of California, Berkeley

    Berkeley, United States

    4 h-index

    4 publications

    139 citations

  2. Pennsylvania State University

    State College, United States

    4 h-index

    6 publications

    311 citations

  3. University of Illinois Chicago

    Chicago, United States

    4 h-index

    4 publications

    124 citations

  4. Tel Aviv University

    Tel Aviv, Israel

    3 h-index

    3 publications

    67 citations

  5. Universidad de Sevilla

    Seville, Spain

    3 h-index

    4 publications

    121 citations

  6. Cornell University

    Ithaca, United States

    3 h-index

    3 publications

    483 citations

  7. Carnegie Mellon University

    Pittsburgh, United States

    3 h-index

    4 publications

    122 citations

  8. University of Chicago

    Chicago, United States

    3 h-index

    3 publications

    121 citations

1–8 of 91

Venues

  1. SIAM Journal on Computing

    14 publications · 1.4K citations

    13

    h-index

  2. Theoretical Computer Science

    5 publications · 143 citations

    5

    h-index

  3. Journal of Computer and System Sciences

    4 publications · 1.5K citations

    4

    h-index

  4. Journal of the ACM

    JACM · 3 publications · 435 citations

    3

    h-index

  5. Fundamenta Informaticae

    3 publications · 57 citations

    3

    h-index

1–5