Document Zbl 0462.03010

Complexity of algorithms and computations. (English) Zbl 0462.03010

J. Sov. Math. 15, 140-165 (1981).

Page: −5 −4 −3 −2 −1 ±0 +1 +2 +3 +4 +5 Show Scanned Page
scan of Zbl 0462.03010

MSC:

03D15	Complexity of computation (including implicit computational complexity)
68Q05	Models of computation (Turing machines, etc.) (MSC2010)
68W99	Algorithms in computer science
68Q25	Analysis of algorithms and problem complexity
68-02	Research exposition (monographs, survey articles) pertaining to computer science
03D25	Recursively (computably) enumerable sets and degrees
03-02	Research exposition (monographs, survey articles) pertaining to mathematical logic and foundations

Keywords:

analytic classification; Turing machine; Markov algorithm; real time computation; hierarchies

Citations:

Zbl 0454.03018

Cite Review PDF

Full Text: DOI

References:

[1]	V. N. Agafonov, ?Normal sequences and finite automata,? in: Probl. Kibern., No. 20, Nauka, Moscow (1968), pp. 123?129.
[2]	V. N. Agafonov, The Complexity of Algorithms and Computations. 2, Novosibirsk State Univ. (1975).
[3]	V. N. Agafonov, ?The complexity of computing pseudorandom sequences,? Algebra Logika, Seminar,7, No. 2, 4?19 (1968).
[4]	Ya. M. Barzdin’, ?Complexity and accuracy of solving initial fragments of the problem of belonging to a recursively enumerable set,? Dokl. Akad. Nauk SSSR,199, No. 2, 262?264 (1971).
[5]	Ya. M. Barzdin’, ?The complexity of programs recognizing whether quantities not exceeding natural numbers belong to a recursively enumerable set,? Dokl. Akad. Nauk SSSR,182, No‘. 6, 1249?1252 (1968).
[6]	Ya. M. Barzdin’, ?The complexity of recognizing symmetry on Turing machines,? in: Probl. Kibern., No. 15, Nauka, Moscow (1965), pp. 245?248.
[7]	Yu. Ya. Breitbart, ?On automatic and ?zone? complexity of the predicate ?be the power of a number?,? Dokl. Akad. Nauk SSSR,196, No. 1, 16?19 (1971).
[8]	Yu. A. Bukhshtab, ?The realizability of functions on one-dimensional iterative circuits in real time,? in: Probl. Kibern., No. 22, Nauka, Moscow (1970), pp. 85?94. · Zbl 0199.31403
[9]	M. K. Valiev, ?Some estimates of computation time for Turing machines with input,? Kibernetika, No. 6, 26?32 (1970).
[10]	A. V. Gladkii and A. Ya. Dikovskii, ?The theory of formal grammars,? Teor. Veroyatn. Mat. Statistika. Teor. Kibern., Vol. 7 (Itogi Nauki i Tekh.) (1972), pp. 107?142.
[11]	V. G. Zharov, ?On estimating the complexity of terms of constructive sequences of normal algorithms,? Dokl. Akad. Nauk SSSR,203, No. 4, 746?748 (1972).
[12]	I. D. Zaslavskii, ?On the pseudofunctions of Shannon,? Zap. Nauchn. Sem. Leningr. Otd. Mat.Inst. Akad. Nauk SSSR,16, 65?76 (1969).
[13]	A. K. Zvonkin and L. A. Levin, ?The complexity of finite objects and the foundation of the concepts of information and randomness by means of the theory of algorithms,? Usp. Mat. Nauk,25, No. 6, 86?127 (1970). · Zbl 0222.02027
[14]	Ya. B. Kazanovich, ?Classification of primitively recursive functions by means of Turing machines,? in: Probl. Kibern., No. 22, Nauka, Moscow (1970), pp. 95?106. · Zbl 0241.02011
[15]	M. I. Kanovich, ?On the domains of optimal algorithms,? Dokl. Akad. Nauk SSSR,198, No. 2, 283?285 (1971). · Zbl 0235.02025
[16]	M. I. Kanovich, ?On the universality of strongly nonsolvable sets,? Dokl. Akad. Nauk SSSR,204, No. 3, 533?535 (1972).
[17]	M. I. Kanovich, ?On the complexity of minimizing Boolean functions,? Dokl. Akad. Nauk SSSR,198, No. 1, 35?38 (1971). · Zbl 0235.02026
[18]	M. I. Kanovich, ?On the complexity of the resolution of algorithms,? Dokl. Akad. Nauk SSSR,186, No. 5, 1008?1009 (1969).
[19]	M. I. Kanovich, ?On the complexity of enumerating and resolving predicates,? Dokl. Akad. Nauk SSSR,190, No. 1, 23?26 (1970).
[20]	M. I. Kanovich, ?The complexity of bounded resolution of semienumerable sets,? Dokl. Akad. Nauk SSSR,203, No. 6, 1246?1248 (1972).
[21]	M. I. Kanovich, ?The complexity of resolving an enumerable set as a criterion of its universality,? Dokl. Akad. Nauk SSSR,194, No. 3, 500?503 (1970).
[22]	M. I. Kanovich and B. A. Kushner, ?On an estimate of the complexity of some mass problems of analysis,? Zap. Nauchn. Sem. Leningr. Otd. Mat. Inst. Akad. Nauk SSSR,16, 81?90 (1969). · Zbl 0267.02022
[23]	M. I. Kanovich and N. V. Petri, ?Some theorems on the complexity of normal algorithms and computations,? Dokl. Akad. Nauk SSSR,184, No. 6, 1275?1276 (1969).
[24]	A. A. Karatsuba and Yu. P. Ofman, ?Multiplication of multidigit numbers on automata,? Dokl. Akad. Nauk SSSR,145, No. 2, 293?294 (1962).
[25]	B. M. Kloss, ?On the definition of the complexity of algorithms,? Dokl. Akad. Nauk SSSR,157, No. 1, 38?40 (1964). · Zbl 0127.01001
[26]	V. A. Kozmidiadi, ?On a generalization of finite automata which forms a hierarchy analogous to the classification of A. Grzegorczyk of primitively recursive functions,? in: Probl. Kibern., No. 23, Nauka, Moscow (1970), pp. 127?170.
[27]	V. A. Kozmidiadi and S. S. Marchenkov, ?On multihead automata,? in: Probl. Kibern., No. 21, Nauka, Moscow (1969), pp. 127?158.
[28]	A. N. Kolmogorov, ?Three approaches to the definition of the concept of the ?quantity of information?,? Probl. Peredachi Inf.,1, No. 1, 3?11 (1965).
[29]	Yu. A. Kryukov, ?Turing machines with two symbols and two states,? Algebra Logika. Seminar,6, No. 3, 51?60 (1967).
[30]	Yu. A. Kryukov, ?Turing machines with three states and two symbols and one state and symbols,? Kibernetika, No. 1, 12?13 (1971).
[31]	A. V. Kuznetsov, ?On a theorem on the canonical form for ordinal recursive functions,? Appendix to the book of R. L. Goodstein, Mathematical Logic [Russian translation], IL, Moscow (1961), pp. 149?154.
[32]	V. A. Kuz’min, ?Realization of functions of a logic algebra by automata, normal algorithms, and Turing machines,? in: Probl. Kibern., No. 13, Nauka, Moscow (1955), pp. 75?96.
[33]	G. B. Marandzhyan, ?The hierarchy of recursive functions and asymptotic optimality,? Aikakan SSR Gitutyunneri Akademia, Zekuitsner. Dokl. Akad. Nauk ArmSSR,48, No. 4, 193?197 (1969).
[34]	G. B. Marandzhyan, ?On some properties of asymptotical optimal recursive functions,? Aikakan SSR Gitutyunneri Akademiai Tegekagir. Matematika, Izv. Akad. Nauk ArmSSR, Mat.,4, No. 1, 3?22 (1969).
[35]	G. B. Marandzhyan, ?On strictly effective immunity of the stems of additively optimal recursive functions,? Aikakan SSR Gitutyunneri Akademia Tegekagir. Matematika, Izv. Akad. Nauk ArmSSR,7, No. 6, 391?398 (1972).
[36]	A. A. Markov, ?On normal algorithms computing Boolean functions,? Dokl. Akad. Nauk SSSR,157, No. 2, 262?264 (1964). · Zbl 0127.01002
[37]	A. A. Markov, ?On normal algorithms connected with the computation of Boolean functions,? Izv. Akad. Nauk SSSR, Ser. Mat.,31, No. 1, 161?208 (1967).
[38]	P. Martin-Löf, ?On the concept of a random sequence,? Teor. Veroyatn. Ee Primen.,11, No, 2, 198?202 (1966).
[39]	S. S. Marchenkov, ?On bounded recursions,? Math. Balkan.,2, 124?142 (1972).
[40]	S. G. Matveeva, ?On the theorem of Rabin on the complexity of computable functions,? Sib. Mat. Zh.,4, No. 3, 546?555 (1965).
[41]	Yu. V. Matiyasevich, ?On the recognizing in real time of the relation of containment,? Zap. Nauchn. Sem. Leningr. Otd. Mat. Inst. Akad. Nauk SSSR,20, 104?114 (1971).
[42]	V. A. Moshchenskii, ?On the question of the complexity of Turing computations,? Dokl. Akad. Nauk BSSR,13, No. 10, 871?878 (1969).
[43]	V. A. Moshchenskii, ?On the estimate of certain functions characterizing the work of Turing machines,? Kibernetika, No. 1, 34?40 (1971).
[44]	V. A. Nepomnyashchii, ?On a basis for recursively enumerable sets,? Dokl. Akad. Nauk SSSR,170, No. 6, 1262?1264 (1966).
[45]	V. A. Nepomnyashchii, ?A rudimentary interpretation of two-tape Turing computations,? Kibernetika, No. 2, 29?35 (1970).
[46]	V. A. Nepomnyashchii, ?Rudimentary predicates and Turing computations,? Dokl. Akad. Nauk SSSR,195, No. 2, 282?284 (1970).
[47]	E. S. Orlovskii, ?Some questions of the theory of algorithms,? Tr. Mat. Inst. Akad. Nauk SSSR,52, 140?171 (1958).
[48]	D. A. Ostroukhov, ?On the coding of natural numbers by schemes of normal algorithms,? Z. Math. Log. Grundl. Math.,16, No. 4, 347?352 (1970). · Zbl 0222.02026 · doi:10.1002/malq.19700160607
[49]	D. A. Ostroukhov, ?On an estimate of the complexity of normal algorithms,? Dokl. Akad. Nauk SSSR,184, No. 6, 1292?1293 (1969).
[50]	N. V. Petri, ?On algorithms connected with predicates and Boolean functions,? Dokl. Akad. Nauk SSSR,185, No. 1, 37?39 (1969). · Zbl 0193.31501
[51]	N. V. Petri, ?Complexity of algorithms and their working time,? Dokl. Akad. Nauk SSSR,186, No, 1, 30?31 (1969). · Zbl 0272.02053
[52]	D. Skordev, ?Some simple examples of universal functions,? Dokl. Akad. Nauk SSSR,190, No. 1, 45?46 (1970). · Zbl 0197.28101
[53]	N. P. Ter-Zakharyan, ?On some quantitative characteristics of algorithmic languages,? Dokl. Akad. Nauk SSSR,190, No. 3, 538?540 (1970).
[54]	A. L. Toom, ?On the complexity of a scheme of functional elements realizing the multiplication of whole numbers,? Dokl. Akad. Nauk SSSR,150, No. 3, 496?498 (1963). · Zbl 0203.15604
[55]	B. A. Trakhtenbrot, ?On normalized signalings for Turing computations,? Algebra Logika. Seminar,5, No. 6, 61?70 (1966).
[56]	B. A. Trakhtenbrot, ?Optimal computations and the frequency phenomenon of Yablonskii,? Algebra Logika. Seminar,4, No. 5, 79?93 (1965).
[57]	B. A. Trakhtenbrot, Complexity of Algorithms and Computations [in Russian], Novosibirsk State Univ. (1967).
[58]	B. A. Trakhtenbrot, ?Turing computations with logarithmic delay,? Algebra Logika. Seminar,3, No. 4, 33?48 (1964).
[59]	R. V. Freivald, ?On the order of growth of precise time signalings for Turing computations,? Algebra Logika. Seminar,5, No. 5, 85?93 (1966).
[60]	R. V. Freivald, ?The complexity of symmetry recognition on Turing machines with input,? Algebra Logika. Seminar,4, No. 1, 47?58 (1965).
[61]	V. I. Khomich, ?On the complexity of algorithms connected with the realization of logical-arithmetic and propositional formulas,? Dokl. Akad. Nauk SSSR,191, No. 5, 1004?1006 (1970).
[62]	G. S. Tseitin, ?A lower bound for the number of steps for an inverting normal algorithm and two analogous algorithms,? Zap. Nauch. Sem. Leningr. Otd. Mat. Inst. Akad. Nauk SSSR,20, 243?262 (1971).
[63]	G. S. Tseitin, ?An estimate of the number of steps in applying a normal algorithm,? Mathematics in the USSR after Forty Years, Moscow,1, 44?45 (1959).
[64]	S. Aanderaa and P. C. Fischer, ?The solvability of halting problem for 2-state Post machines,? J. Assoc. Comput. Mach.,14, No. 4, 677?682 (1967). · Zbl 0163.00903 · doi:10.1145/321420.321426
[65]	M. A. Arbib, Speed-Up Theorems and Incompleteness Theorems in Automata Theory, Academic Press, New York-London (1966), pp. 6?24.
[66]	M. A. Arbib and M. Blum, ?Machine dependence of degrees of difficulty,? Proc. Am. Math. Soc.,16, No. 3, 442?447 (1965). · Zbl 0135.25002 · doi:10.1090/S0002-9939-1965-0181538-0
[67]	A. J. Atrubin, ?A one-dimensional real-time iterative multiplier,? IEEE Trans. Electron. Comput.,14, No. 3, 394?399 (1965). · doi:10.1109/PGEC.1965.264145
[68]	G. Ausiello, ?Abstract computational complexity and cyclic function,? Conf. Rec. of Second Annual ACM Symposium on Theory of Computing,4, 1?47 (1970).
[69]	P. Axt, ?Enumeration and Grzegorczyk hierarchy,? Z. Math. Logik Grundl. Math.,9, No. 1, 53?65 (1963). · Zbl 0112.24602 · doi:10.1002/malq.19630090106
[70]	P. Axt, ?Iteration of primitive recursion,? Z. Math. Logik Grundl. Math.,11, No. 3, 253?255 (1965). · Zbl 0144.00201 · doi:10.1002/malq.19650110310
[71]	P. Axt, ?Note on the 3-recursive functions,? Z. Math. Logik Grundl. Math.,7, No. 2, 97?98 (1961). · Zbl 0106.00701 · doi:10.1002/malq.19610070702
[72]	J. Becvar, ?Probleme der Komplexität in der Theorie der Algorithmen und Automaten,? Int. Ser. Number. Math. 6, Basel-Stuttgart, 142?157 (1967). · Zbl 0174.03806
[73]	J. Becvar, ?Programmkomplexität von borechenbaren Funktionen,? Z. Angew. Math. Mech.,50, Sonderh, 1?4, 82 (1970). · Zbl 0205.01305 · doi:10.1002/zamm.19700500140
[74]	J. Becvar, ?Programmkomplexität von Funktionen und Mengen,? Ber. Math. Forschunginst. Oberwolfach, No. 3, 317?326 (1970).
[75]	J. Becvar, ?Real-time and complexity problems in automata theory,? Kybernetika,1, No. 6, 475?498 (1965). · Zbl 0192.08701
[76]	M. Blum, ?A machine-independent theory of the complexity of recursive functions,? J. Assoc. Comput. Mach.,14, No. 2, 322?326 (1967). · Zbl 0155.01503 · doi:10.1145/321386.321395
[77]	M. Blum, ?Measures on the computational speed of partial recursive functions,? Q. Progr. Report, 72, Res. Lab. Electronics, MIT, 237?253 (1964).
[78]	M. Blum, ?On effective procedures for speeding up algorithms,? J. Assoc. Comput. Mach.,18, No. 2, 290?305 (1971). · Zbl 0221.02016 · doi:10.1145/321637.321648
[79]	M. Blum, ?On the size of machines,? Inf. Control,11, No. 3, 257?265 (1968). · Zbl 0165.02102 · doi:10.1016/S0019-9958(67)90546-3
[80]	M. Blum, ?Recursive function theory and speed of computation,? Can. Math. Bull.,9, No. 6, 745?750 (1966). · Zbl 0158.24904 · doi:10.4153/CMB-1966-030-9
[81]	R. V. Book and S. A. Greibach, ?Quasi-realtime languages,? Math. Syst. Theory,4, No. 2, 97?111 (1970). · Zbl 0188.33102 · doi:10.1007/BF01705890
[82]	C. Böhm, ?A three-tape, three-state, three-symbol universal Turing machine,? Pubbl. Inst. Applic. Calcolo, No. 698 (1968).
[83]	A. Borodin, ?Computational complexity and the existence of complexity gaps,? J. Assoc. Comput. Mach.,19, 158?174 (1972). · Zbl 0261.68024 · doi:10.1145/321679.321691
[84]	A. Borodin, ?Computational complexity 2 A survey,? Proc. Fourth Ann. Princeton Conf. on Information Sci. and Systems, 257?262 (1970).
[85]	A. Borodin, R. L. Constable, and J. E. Hopcroft, ?Dense and nondense families of complexity classes,? IEEE Conf. Rec. 10th Annual Sympos. Switch. and Automata Theory, Waterloo, 1969, New York, 7?19 (1969).
[86]	J. Bulnes, ?On the speed of addition and multiplication on one-tape, off-line Turing machines,? Inf. Control,20, No. 5, 415?431 (1972). · Zbl 0238.02033 · doi:10.1016/S0019-9958(72)90843-1
[87]	W. A. Burkhard, ?Complexity problems in real time computation,? Conf. Rec. of Second Ann. ACM Symposium on Theory of Computing, 62?69 (1970).
[88]	W. A. Burkhard and P. P. Varaiya, ?Complexity problems in real time languages,? Inf. Sci.,3, No. 1, 87?100 (1971). · Zbl 0222.02041 · doi:10.1016/S0020-0255(71)80024-5
[89]	J. R. Buchi, ?Weak second-order arithmetic and finite automata,? Z. Math. Logik Grundl. Math.,6, No. 1, 66?92 (1960). · Zbl 0103.24705 · doi:10.1002/malq.19600060105
[90]	G. J. Chaitin, ?On the length of programs for computing finite binary sequences,? J. Assoc. Comput. Mach.,13, 547?569 (1966). · Zbl 0158.25301 · doi:10.1145/321356.321363
[91]	T. S. Chow, ?On the structure of Blum measure,? AFIPS Conf. Proc, Vol. 40, Spring Joint Comput. Conf., Atlantic City, N.J., 1972, Montvale, New Jersey, 503?506 (1972).
[92]	J. P. Cleave, ?A hierarchy of primitive recursive functions,? Z. Math. Logik Grundl. Math.,9, No. 4, 331?346 (1963). · Zbl 0124.00303 · doi:10.1002/malq.19630092202
[93]	A. Cobham, ?The intrinsic computational difficulty of functions,? Logic, Methodol. Philos. Sci., Amsterdam, 24?30 (1965). · Zbl 0192.08702
[94]	A. Cobham, ?Time and memory capacity bounds for machines which recognize squares of palindroms,? IBM Res. Report RC 1621 (1966).
[95]	?Complexity of computer computations,? Panel Discussion, Complexity Comput. Computat., Proc. Symp., Yorktown Heights, New York, 1972, New York-London, 169?185 (1972).
[96]	R. L. Constable, ?On the size of programs in subrecursive formalisms,? Ann. ACM. Symp. Theory Comput., 1?9 (1970).
[97]	R. L. Constable, ?Two types of hierarchy theorems for axiomatic complexity classes,? Courant. Comput. Sci. Symp. J. Comput., Complex., 1971, New York, New York, 37?63 (1973).
[98]	R. L. Constable, ?Upward and downward diagonalisation over axiomatic complexity classes,? Technical Report 69-32, Dept. of Computer Science, Cornell University (1969).
[99]	R. L. Constable and A. Borodin, ?On the efficiency of programs in subrecursive formalisms.? Incomplete version, Extend. Abstr. IEEE Conf. Rec. 11th Annual Symp. Switch. and Automata Theory, Santa Monica, Calif., 1970, New York, New York (1970).
[100]	R. L. Constable and J. Hartmanis, ?Complexity of formal translations and speed-up results,? Conf. Rec. 3rd Annu. ACM Symp. Theory Comput., Shaker Heights, Ohio, 1971, New York, New York (1971). · Zbl 0257.68036
[101]	S. A. Cook, ?Characterizations of pushdown machines in terms of time-bounded computers,? J. Assoc. Comput. Mach.,18, No. 1, 4?18 (1971). · Zbl 0222.02035 · doi:10.1145/321623.321625
[102]	S. A. Cook, ?The complexity of theorem-proving procedures,? Conf. Rec. 3rd Annu. ACM Symp. Theory Comput., Shaker Heights, Ohio, 1971, New York, New York (1971). · Zbl 0253.68020
[103]	S. A. Cook and S. O. Aanderaa, ?On the minimum computation time of functions,? Trans. Am. Math. Soc.,142, 291?314 (1969). · doi:10.1090/S0002-9947-1969-0249212-8
[104]	H. B. Enderton, ?Degrees of computational complexity,? J. Comput. Syst. Sci.,6, No. 5, 389?396 (1972). · Zbl 0251.68029 · doi:10.1016/S0022-0000(72)80010-2
[105]	S. Feferman, ?Classifications of recursive functions by means of hierarchies,? Trans. Am. Math. Soc.,104, No. 1, 101?122 (1962). · Zbl 0106.00602 · doi:10.1090/S0002-9947-1962-0142453-3
[106]	P. C. Fischer, ?The reduction of tape reversals for off-line one-tape Turing machines,? J. Comput. Syst. Sci.,2, No. 2, 136?147 (1968). · Zbl 0199.31001 · doi:10.1016/S0022-0000(68)80028-5
[107]	P. C. Fischer, ?Turing machines with a schedule to keep,? Inf. Control,11, Nos. 1?2, 138?146 (1967). · Zbl 0153.31701 · doi:10.1016/S0019-9958(67)90433-0
[108]	P. C. Fischer, J. Hartmanis, and M. Blum, ?Tape reversal complexity hierarchies,? IEEE Conf. Rec. of 1968 Ninth Annual Symp. on Switching and Automata Theory, 373?382 (1968).
[109]	P. C. Fischer, A. R. Meyer, and A. L. Rosenberg, ?Counter machines and counter languages,? Math. Syst. Theory,2, No. 3, 265?283 (1968). · Zbl 0165.32002 · doi:10.1007/BF01694011
[110]	P. C. Fischer, A. R. Meyer, and A. L. Rosenberg, ?Real time simulation of multihead tape units,? J. Assoc. Comput. Mach.,19, No. 4, 590?607 (1972). · Zbl 0261.68027 · doi:10.1145/321724.321726
[111]	P. C. Fischer, A. R. Meyer, and A. L. Rosenberg, ?Time-restricted sequence generation,? J. Comput. Syst. Sci.,4, No. 1, 50?73 (1970). · Zbl 0191.18301 · doi:10.1016/S0022-0000(70)80012-5
[112]	E. P. Glinert, ?On restricted Turing computability,? Math. Syst. Theory,5, No. 4, 331?343 (1971). · Zbl 0226.02038 · doi:10.1007/BF01694077
[113]	A. Grzegorczyk, ?Some classes of recursive functions,? Instytut Matematyczny Polskiej Akademii Nauk. Rozprawy Matematyczne, 4 (1953).
[114]	J. Hartmanis, ?Computational complexity of one tape Turing machine computations,? J. Assoc. Comput. Mach.,15, No. 2, 325?339 (1968). · Zbl 0162.31703 · doi:10.1145/321450.321464
[115]	J. Hartmanis, ?On the complexity of undecidable problems on automata theory,? J. Assoc. Comput. Mach.,16, No. 1, 160?167 (1969). · Zbl 0182.02403 · doi:10.1145/321495.321507
[116]	J. Hartmanis, ?Size argument in the study of computation speeds,? Proc. Symp. Comput. and Automata, New York, New York, 1971, Brooklyn, New York (1971). · Zbl 0265.68029
[117]	J. Hartmanis, ?Tape reversal bounded Turing machine computations,? J. Comput. Syst. Sci.,2, No. 2, 117?135 (1968). · Zbl 0259.68020 · doi:10.1016/S0022-0000(68)80027-3
[118]	J. Hartmanis and J. E. Hopcroft, ?An overview of the theory of computational complexity,? J. Assoc. Comput. Mach.,18, No. 3, 444?475 (1971). · Zbl 0226.68024 · doi:10.1145/321650.321661
[119]	J. Hartmanis, P. M. Lewis II, and R. E. Stearns, ?Classifications of computations by time and memory requirements,? Proc. of IFIP Congress I, Washington, D. C. (1965). · Zbl 0203.16401
[120]	J. Hartmanis and H. Shank, ?Two memory bounds for the recognition of primes by automata,? Math. Syst. Theory,3, No. 2, 125?129 (1969). · Zbl 0175.00804 · doi:10.1007/BF01746518
[121]	J. Hartmanis and R. E. Stearns, ?Automata-based computational complexity,? Inf. Sci.,1, No. 2, 173?184 (1969). · Zbl 0156.25604 · doi:10.1016/0020-0255(69)90014-0
[122]	J. Hartmanis and R. E. Stearns, ?On the computational complexity of algorithms,? Trans. Am. Math. Soc.,117, No. 5, 285?306 (1965). · Zbl 0131.15404 · doi:10.1090/S0002-9947-1965-0170805-7
[123]	I. M. Havel, ?Weak complexity measures,? SIGACT News,8, 21?30 (1971). · doi:10.1145/1247063.1247064
[124]	J. P. Helm and P. R. Young, ?On size vs efficiency for programs admitting speed-ups,? J. Symbol. Log.,36, No. 1, 21?27 (1971). · Zbl 0258.68023 · doi:10.2307/2271512
[125]	F. C. Hennie, ?Crossing sequences and off-line Turing machine computations,? IEEE Conf. Rec. Switch. Circuit. Theory and Logic Design, Ann Arbor, Mich., 1965, New York, New York, Inst. Electr. and Electron Engrs. Inc. (1965).
[126]	F. C. Hennie, ?One-tape, off-line Turing machine computations,? Inf. Control,8, 553?578 (1965). · Zbl 0231.02048 · doi:10.1016/S0019-9958(65)90399-2
[127]	F. C. Hennie, ?On-line Turing machine computations,? IEEE Trans. Electron. Comput.,15, No. 1, 35?44 (1966). · Zbl 0161.13504 · doi:10.1109/PGEC.1966.264374
[128]	F. C. Hennie and R. E. Stearns, ?Two-tape simulation of multitape Turing machines,? J. Assoc. Comput. Mach.,13, No. 4, 533?546 (1976). · Zbl 0148.24801 · doi:10.1145/321356.321362
[129]	G. T. Herman, ?A new hierarchy of elementary functions,? Proc. Am. Mach. Soc.,20, No. 2, 557?562 (1969). · Zbl 0181.01201 · doi:10.1090/S0002-9939-1969-0250878-2
[130]	G. T. Herman, ?The equivalence of different hierarchies of elementary functions,? Z. Math. Log. Grundl.,17, No. 3, 219?224 (1971). · Zbl 0222.02043 · doi:10.1002/malq.19710170125
[131]	G. T. Herman, ?The halting problem of one state Turing machines with n-dimensional tape,? Z. Math. Logik Grundl. Math.,14, No. 2, 185?191 (1968). · Zbl 0169.31104 · doi:10.1002/malq.19680140706
[132]	P. K. Hooper, ?Some small, multitape universal Turing machines,? Inf. Sci.,1, No. 2, 209?215 (1969). · doi:10.1016/0020-0255(69)90017-6
[133]	J. E. Hopcroft and J. D. Ullman, ?Relation between time and tape complexities,? J. Assoc. Comput. Mach.,15, No. 3, 414?427 (1968). · Zbl 0169.31103 · doi:10.1145/321466.321474
[134]	J. E. Hopcroft and J. D. Ullman, ?Some results on tape-bounded Turing machines,? J. Assoc. Comput. Mach.,16, No. 1, 168?177 (1969). · Zbl 0188.33501 · doi:10.1145/321495.321508
[135]	O. H. Ibarra, ?A note concerning nondeterministic tape complexities,? J. Assoc. Comput. Mach.,18, No. 4, 608?612 (1972). · Zbl 0245.94044 · doi:10.1145/321724.321727
[136]	L. Kalmar, ?Eguszerü pelda eldönthetetlen aritmetikai problemara? (Ein einfaches Beispiel für ein unentscheibares arithmetisches Problem), Matematikai es Fizikai Lapok,50, 1?23 (1943).
[137]	T. Kameda, ?Constant-tape-reversal bounded nondeterministic Turing machine computations,? Comput. Symp., 1970, Bonn, Proc., Frankfurt (1973).
[138]	T. Kameda and K. Vollmar, ?Note on tape reversal complexity of languages,? Inf. Control,17, No. 2, 203?215 (1970). · Zbl 0196.01801 · doi:10.1016/S0019-9958(70)90549-8
[139]	T. Kameda and R. Vollmar, ?Zur Umkehrkomplexität von Sprachen,? Ber. Math. Forschungsinst. Oberwolfach,3, 327?339 (1970).
[140]	R. M. Karp, ?Reducibility among combinatorial problems,? Complexity Comput. Computat., Proc. Symp., Yorktown Heights, New York, 1972, New York-London (1972).
[141]	R. M. Karp, ?Some bounds on the storage requirements of sequential machines and Turing machines,? J. Assoc. Comput. Mach.,14, No. 3, 478?489 (1967). · Zbl 0153.31802 · doi:10.1145/321406.321410
[142]	S. C. Kleene, ?Extension of an effectively generated class of functions by enumeration,? Colloq. Math.,6, 67?78 (1958). · Zbl 0085.24602
[143]	D. E. Knouth, The Art of Computer Programming, 2, Addison-Wesley (1969).
[144]	L. H. Landweber and E. L. Robertson, ?Recursive properties of abstract complexity classes,? J. Assoc. Comput. Mach.,19, No. 2, 296?308 (1972). · Zbl 0261.68025 · doi:10.1145/321694.321702
[145]	E. L. Lawler, ?The complexity of combinatorial computations, a survey,? Proc. Symp. Comput. and Automata, New York, New York, 305?311 (1971). · Zbl 0257.68035
[146]	F. D. Lewis, ?The enumerability and invariance of complexity classes,? J. Comput. Syst. Sci.,5, No. 3, 286?303 (1971). · Zbl 0215.04701 · doi:10.1016/S0022-0000(71)80037-5
[147]	G. Longo, ?Towards an abstract analysis of time progression of consumption of resources during computation,? Int. Comput. Symp., Venice (1972).
[148]	L. Longo, ?Axioms for time dependence of resource consumption in computing recursive functions,? SIGACT News,12, 14?24 (1971).
[149]	D. W. Loveland, ?A variant of the Kolomogorov concept of complexity,? Inf. Control,15, No. 6, 510?526 (1969). · Zbl 0188.52101 · doi:10.1016/S0019-9958(69)90538-5
[150]	M. H. Löb and S. S. Wainer, ?Hierarchies of number-theoretic functions. I,? Arch.Mach. Log. Grundl.,13, Nos. 1?2, 39?51 (1970). · Zbl 0211.31205
[151]	M. H. Löb and S. S. Wainer, ?Hierarchies of number-theoretic functions. II,? Arch. Math. Log. Grundl.,13, Nos. 3?4, 97?113 (1970). · Zbl 0222.02049 · doi:10.1007/BF01973616
[152]	N. A. Lynch, ?Relativization of the theory of computational complexity,? Proj. MAC Tech. Rept., No. 99 (1972).
[153]	P. Martin-Löf, ?Complexity oscillations in infinite binary sequences,? Z. Wahrscheinlichkeitstheory Verw. Geb.,19, No. 3, 225?237 (1971). · Zbl 0212.23103 · doi:10.1007/BF00534110
[154]	P. Martin-Löf, ?On the notion of randomness,? Intuitionism and proof theory, New York, 73?78 (1968).
[155]	P. Martin-Löf, ?The definition of random sequences,? Inf. Control,9, No. 6, 602?619 (1966). · Zbl 0244.62008 · doi:10.1016/S0019-9958(66)80018-9
[156]	E. M. McCreight and A. R. Meyer. ?Classes of computable functions defined by bounds on computation: preliminary report,? Conf. Rec. of ACM Symp. on Theory of Computing, 79?88 (1969). · Zbl 1283.03074
[157]	A. R. Meyer, ?Program size in restricted programming languages,? Inf. Control,21, No. 4, 382?394 (1972). · Zbl 0301.68019 · doi:10.1016/S0019-9958(72)90592-X
[158]	A. R. Meyer, ?Theories of computational complexity,? Comput. Sci. Res. Review, Carnegie -Mellon Univ., 17?22 (1968).
[159]	A. R. Meyer, ?Weak monadic second-order theory of successor is not elementary recursive,? Preliminary Report, Cambridge, Mass., 1?24 (1972).
[160]	A. R. Meyer and A. Bagchi, ?Program size and economy of descriptions,? Preliminary Report, 4th Annual ACM Symp. Theory Comput., Denver, Colo., 183?186 (1972). · Zbl 0354.68024
[161]	A. R. Meyer and P. Fischer, ?Economy of descriptions by automata, grammars and formal systems,? Conf. Rec. 12th Annual Symp. Switch. and Automata Theory, East Lansing, Mich., 1971, New York, New York, 188?191 (1971).
[162]	A. R. Meyer and P. Fischer, ?Computational speed-up by effective operators,? J. Symbol. Log.,37, No. 1, 55?68 (1972). · Zbl 0249.68018 · doi:10.2307/2272545
[163]	A. R. Meyer and E. M. McCreight, ?Computationally complex and pseudorandom zero-one valued functions,? Theory Mach. Comput., New York-London, 19?42 (1971).
[164]	A. R. Meyer and R. Moll, ?Honest bounds for complexity classes of recursive functions,? 13th Annual Symp. Switch. and Automata Theory, 1972, New York, New York, 61?66 (1972).
[165]	A. R. Meyer, A. L. Rosenberg, and P. C. Fischer, ?Turing machines with several read-write heads,? Preliminary Report, IEEE Conf. Rec. 8th Annual Symp. Switch. and Automata Theory, Austin, Texas, 1967, New York, New York, 117?127 (1967).
[166]	A. R. Meyer and D. M. Ritchie, ?A classification of the recursive functions,? Z. Math. Log. Grundl. Math.,18, No. 1, 71?81 (1972). · Zbl 0247.02037 · doi:10.1002/malq.19720180405
[167]	M. L. Minsky, Computation: Finite and Infinite Machines, Prentice-Hall, Englewood Cliffs, New Jersey (1967). · Zbl 0195.02402
[168]	M. L. Minsky, ?Size and structure of universal Turing machines using Tag systems,? Recurs. Funct. Theory, Am. Math. Soc., 229?238 (1962). · Zbl 0192.06601
[169]	J. Myhill, ?A stumblingblock in constructive mathematics,? Abstract, J. Symbol. Logic,18, 190?191 (1953).
[170]	A. Nozaki, ?On the notion of universality of Turing machine,? Kybernetika,5, No. 1 (1969). · Zbl 0167.01504
[171]	D. Pager, ?On the efficiency of algorithms,? J. Assoc. Comput. Mach.,17, No. 4, 708?714 (1970). · Zbl 0206.28601 · doi:10.1145/321607.321619
[172]	R. A. Di Paola, ?Random sets in subrecursive hierarchies,? J. Assoc. Comput. Mach.,16, No. 4, 621?630 (1969). · Zbl 0188.02703 · doi:10.1145/321541.321551
[173]	Ch. Parsons, ?Hierarchies of primitive recursive functions,? Z. Math. Logik Grundl. Math.,14, No. 4, 357?376 (1968). · Zbl 0172.29703 · doi:10.1002/malq.19680142106
[174]	M. S. Paterson, ?Tape bounds for time bounded Turing machines,? J. Comput. Syst. Sci.,6, No. 2, 116?124 (1972). · Zbl 0236.02031 · doi:10.1016/S0022-0000(72)80017-5
[175]	R. Peter, ?Mehrfache und transfinite Rekursionen,? J. Symbol. Logic,15, 248?272 (1950). · Zbl 0040.29402 · doi:10.2307/2268337
[176]	R. Peter, Rekursive Funktione, Budapest (1951).
[177]	R. Peter, ?Über die mehrfache rekursion,? Math. Annalen,113, 489?527 (1936). · Zbl 0015.33902 · doi:10.1007/BF01571648
[178]	M. O. Rabin, ?Real time computation,? Israel J. Math.,1, No. 4, 203?211 (1963). · Zbl 0156.25603 · doi:10.1007/BF02759719
[179]	M. O. Rabin, ?Speed of computation of functions and classification of recursive sets,? Bull. Res. Council Israel,8, No. 1, 69?70 (1959).
[180]	R. W. Ritchie, ?Classes of predictably computable functions,? Trans. Am. Math. Soc.,106, 139?173 (1963). · Zbl 0107.01001 · doi:10.1090/S0002-9947-1963-0158822-2
[181]	R. W. Ritchie, ?Classes of recursive functions based on Ackermann’s function,? Pac. J. Math.,15, No. 3, 1027?1044 (1965). · Zbl 0133.24903 · doi:10.2140/pjm.1965.15.1027
[182]	E. L. Robertson, ?A corrected definition of ?local speedup?,? SIGACT News,6, 15?16 (1970). · doi:10.1145/1247054.1247057
[183]	E. L. Robertson, ?Complexity classes of partial recursive functions (preliminary version),? Conf. Rec. 3rd Annual ACM Symp. Theory Comput., Shaker Heights, Ohio, 1971, New York, New York, 258?266 (1971).
[184]	A. L. Rosenberg, ?Real-time definable languages,? J. Assoc. Comput. Mach.,14, No. 4, 645?662 (1967). · Zbl 0153.00902 · doi:10.1145/321420.321423
[185]	N. A. Routledge, ?Ordinal recursion,? Proc. Cambridge Philos. Soc.,49, Part 2, 175?182 (1953). · doi:10.1017/S0305004100028255
[186]	S. S. Ruby and P. C. Fischer, ?Translational methods and computational complexity,? IEEE Conf. Rec. Switch. Circuit Theory and Log. Design, Ann Arbor, Mich., 1965, New York, New York, Inst. Electr. and Electron. Eng. Inc., 173?178 (1965). · Zbl 0257.68037
[187]	W. J. Savitch, ?Relationships between nondeterministic and deterministic tape complexities,? J. Comput. Syst. Sci.,4, No. 2, 177?192 (1970). · Zbl 0188.33502 · doi:10.1016/S0022-0000(70)80006-X
[188]	A. Schmitt, ?Die Zustands-Komplexitats-Klassen von Turing-machinen,? Ber. Math. Forschungsinst. Oberwolfach, No. 3, 343?350 (1970).
[189]	A. Schmitt, ?The state complexity of Turing machines,? Inf. Control,17, No. 3, 217?225 (1970). · Zbl 0222.02038 · doi:10.1016/S0019-9958(70)90440-7
[190]	C. P. Schnorr, ?A unified approach to the definition of random sequences,? Math. Syst. Theory,5, No. 3, 246?258 (1971). · Zbl 0227.62005 · doi:10.1007/BF01694181
[191]	C. P. Schnorr, ?Eine Bemerkung zum Begriff der zufalligen Folge,? Z. Wahrscheinlichkeitstheor. Verw. Geb.,14, No. 1, 27?35 (1969). · Zbl 0188.02805 · doi:10.1007/BF00534115
[192]	C. P. Schnorr, ?Klassifikation der Zufallsgesetze nach Komplexität und Ordnung,? Z. Wahrschienlichkeitstheor. Verw. Geb.,16, No. 1, 1?21 (1971). · Zbl 0192.53503 · doi:10.1007/BF00538763
[193]	C. P. Schnorr, ?The process complexity and effective random tests,? 4th Annual ACM Symp. Theory of Comput., Denver, Colo., 1972, S. 1, 168?176 (1972). · Zbl 0357.68045
[194]	C. P. Schnorr, ?Zufälligkeit und Wahrscheinlichkeit. Eine algorithmische Begrundung der Wahrscheinlichkeitstheorie,? Lect. Notes Math.,218, IV (1971).
[195]	A. Schönhage, ?Multiplikation grosser Zahlen,? Computing (Arch. Elektron. Rechnen),1, 182?196 (1966).
[196]	A. Schönhage and V. Strassen, ?Schnelle Multiplikation grosser Zahlen,? Computing,7, Nos. 3?4, 281?292 (1971). · Zbl 0223.68007 · doi:10.1007/BF02242355
[197]	H. Schwichtenberg, ?Rekursionszahlen und die Grzegorczyk-Hierarchie,? Arch. Math. Logik Grundl.,12, Nos. 1?2, 85?97 (1969). · Zbl 0213.01801 · doi:10.1007/BF01982053
[198]	C. E. Shannon, ?A universal Turing machine with two internal states,? Ann. Math. Stud.,34, 157?165 (1959).
[199]	T. Skolem, ?A theorem on recursively enumerable sets,? Abstr. of Short Comm. Int. Congress Math., Stockholm, 11 (1962).
[200]	A. R. Smith, ?Real-time language recognition by one-dimensional cellular automata,? J. Comput. Syst. Sci.,6, No. 3, 233?253 (1972). · Zbl 0268.68044 · doi:10.1016/S0022-0000(72)80004-7
[201]	R. M. Smullyan, Theory of Formal Systems (Ann. Math. Studies, No. 47), Univ. Press, Princeton, New Jersey, XTV (1961). · Zbl 0097.24503
[202]	R. J. Solomonoff, ?A formal theory of inductive inference. Part I,? Inf. Control,7, No. 1, 1?22 (1964). · Zbl 0258.68045 · doi:10.1016/S0019-9958(64)90223-2
[203]	R. E. Stearns, J. Hartmanis, and P. M. Lewis II, ?Hierarchies of memory limited computations,? IEEE Conf. Rec. Switch. Circuit Theory and Logic Design, Ann Arbor, Mich, 1965, New York, New York, Inst. Electr. and Electron. Eng., Inc., 179?190 (1965).
[204]	L. J. Stockmeyer and A. R. Meyer, ?Word problems requiring exponential time,? Preliminary Report, Cambridge, Mass., 1?17 (1972). · Zbl 0359.68050
[205]	H. J. Stoss, ?A two-tape simulation of Turing machines,? Computing,7, 222?235 (1971). · Zbl 0222.02037 · doi:10.1007/BF02242349
[206]	H. J. Stoss, ?k-band simulation von k-kops Turing machinen,? Computing,6, Nos. 3?4, 309?317 (1970). · Zbl 0222.02036 · doi:10.1007/BF02238815
[207]	P. Strnad, ?On-line Turing machine recognition,? Inf. Control,12, 442?452 (1968). · Zbl 0172.01002 · doi:10.1016/S0019-9958(68)90477-4
[208]	P. Strnad, ?O reprezentovatelnosti jiste mnozine slov automatem v realnem case,? Sb. Vedeck. Praci Vysoke Skoly Strojni a Textil, Liberei, 1966, Prague, 23?27 (1966).
[209]	D. B. Thompson, ?Subrecursiveness: machine-independent notions of computability in restricted time and storage,? Math. Syst. Theory,6, No. 1, 3?15 (1972). · Zbl 0229.68013 · doi:10.1007/BF01706069
[210]	S. S. Wainer, ?A classification of the ordinal recursive functions,? Arch. Math. Log. Grundl.,13, Nos. 3?4, 136?153 (1970). · Zbl 0228.02027 · doi:10.1007/BF01973619
[211]	S. S. Wainer, ?Ordinal recursion and refinement of the extended Grzegorczyk hierarchy,? J. Symbol. Logic,37, No. 2, 281?292 (1972). · Zbl 0261.02031 · doi:10.2307/2272973
[212]	Shigeru Watanabe, ?5-symbol 8-state and 5-symbol 6-state universal Turing machines,? J. Assoc. Comput. Machinery,8, No. 4, 476?483 (1961). · Zbl 0154.41605 · doi:10.1145/321088.321090
[213]	S. Winograd, ?On the time required to perform addition,? J. Assoc. Comput. Mach.,12, No. 2, 277?285 (1965). · Zbl 0125.36306 · doi:10.1145/321264.321279
[214]	S. Winograd, ?On the time required to perform multiplication,? J. Assoc. Comput. Mach.,14, No. 4, 793?802 (1967). · Zbl 0197.43901 · doi:10.1145/321420.321438
[215]	H. Yamada, ?Real-time computation and recursive functions not real-time computable,? IRE Trans. Electron. Comput.,11, No. 6, 753?760 (1962). · doi:10.1109/TEC.1962.5219459
[216]	P. R. Young, ?A note on dense and nondense families of complexity classes,? Math. Syst. Theory,5, No. 1, 66?70 (1971). · Zbl 0216.29103 · doi:10.1007/BF01691468
[217]	P. R. Young, ?Speed-ups by changing the order in which sets are enumerated,? Math. Syst. Theory,5, 145?156 (1971). · Zbl 0219.28004 · doi:10.1007/BF01702870

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.