|
|
 |
| Авторизация |
|
|
|
| Поиск по указателям |
|
|
|
|
|
|
|
 |
|
|
|
| Brady J.M. — The theory of computer science: A programming approach |
|
|
|
| Предметный указатель |
(RASP) (Elgot and Robinson) Section 2.8.3 222
Abstract analytic syntax 172 240
Abstract machine 222
Abstract machine approach (to defining computable) 5 Chapter 92
Acceptor (FSM) 24 70
Ackermann's function 105 109ff 117 121 Section 166
Ackermann, W. 105 110ff
Adder 22
Advice taker project 147
Algol 60 4 11 60 62 64 71 83 89 100 103 123 126 139 140 143 145 168ff Section Section 241
Algol 60 report 11 15 169 Section
ALGOL 68 4 8 70
Algorithm 2 3 6 10 19 52
Allison, D.C.S. 3 6 8 103
Alphabet 70
Amarel, S. 13
Ambiguous grammar 87ff
AND 20 143
Append function 154 163ff
Applicative expressions (AE's) 231 241
Applicative part of a programming language 23
Approximation 229
Arbib, M.A. 14 30 67
Argument selector functions 96ff 119 see
Argument strip for a TM 37 119 122 127
artificial intelligence 10 75 147 167 168
ASC II character set 20 60
assertions 186ff 198 207 215
Assignment command 172 189 198 202ff 242 245
atom (function) 150
atoms (Lisp) 148 150
Automatic programming 101
Axiom 69 73 157 198
B machines Section 2.8.1
Backus, J.W. 11
Backwards substitution 189 198
Barnard, G.A. 6
Base functions 93ff
Basic machine 20 Section
Bdmin (default name for bounded minimisation) 108 122
Behaviour of a program 13 176ff 179ff 181 218
Benchmark 181
Bernays, P. 101
Binary trees 147
Blank tape halting problem 52ff 55
Bledsoe, W.W. 207
Block structure 127 251
BNF 11 29 Section 138 149 169
Body (of a procedure or lambda expression) 70 145 225
Boone, W.W. 73
Bound variable part (of a procedure or lambda expression) 70 145 225
Bounded minimisation (Bdmin) 108 122
Boyer, R.S. 101 172
Burstall, R.M. 174 182
C(f) 93 139 149
Canonical form of S-expression 158
Canonical systems (of Post) 69
Cantor enumeration 58 68 131
Cantor, G. 52 55 58ff
Caplain, M. 208
CAR 150
CDR 150
cdr loop 154
Chomsky hierarchy 25 88ff
Chomsky, N. 25 70 83 88ff 170
Church — Rosser Theorem 71 228 230
Church, A. 4 5 6 70 71 224 225 231 233
Circle-and-arrow notation 22 33 127
Closure 11 231 233 235ff 239 243
Coding 37 41 54 118 122 125 Section see
Combination 225
Combinator 224 231 234
Command 8 172 230 241
Compiler 6 92 117 Section 174 221 239
Complete lattice 229 244
Completeness problem (for a logical system) 74
Complexity hierarchy 112
Complexity measures of computation 5 14 Section 109 Section
Compos (default name for composition) 98 125 139
Computable 2 3 Section 5 19 51 209 224 234 see
Computable real numbers 72
Computer storage 7 49 50
Computers 14 19 29 48 95 117
Concrete synthetic syntax 172
Conditional command 126
Conditional expression 140 155 231 239
Cons 150
Contents (of memory) 7 50
Context free grammar 89
Context sensitive grammar 88
Continuation 249
Continuation induction 185ff
Continuous function 229 244
Cooper, D.C. 208
Correctness of programs 13 174 Chapter 138 150 209 212
CSEDM machine 222 239ff
Curry, H.B. 224 225
Currying 225 227 230 248
Cut assertions 193 197 206
Data structure 12 117 Section 180
de Fermat, P. 52 53
Debugging 13 Chapter
Decidability Section 3.3.2 57 85 91 214
Decision problem 73
declaration 198
Declarative part of a programming language 238
Dedekind, R. 101
Default names 98 100 145
Derivability (in a PSG) 85
Descriptions 6 222 238
Deutsch, L.P. 207 217
Dijkstra, E.W. 81 167 181
Display 233
Domain (Scott) 229ff 244
Dotted pairs 149 230
Dump 222 Section 239
Elgot, C.C. 5 47 50 222
Entry assertion 189 193 197 206
Entscheidungsproblem 74
Enumerability 3 Section 65 67 85
Environment 222 231 233ff 236 248 251
eq 150
Equivalent, proving programs are 14 75ff 138 Section 213
Equivalent, schemas (strong, weak, finite) 80ff
Equivalent, states of a FSM 27
Escapers 11 178 202 218 239
Euclid's Algorithm 190ff Section Section
Execution sequence 80 211
Exit assertion 189 193 197 206
Explicit transformation 99
Fermat's last problem 52 53
find program 198
Finite state machine (FSM) 19ff Section 24ff Section 32 48 91 139
Finiteness assumption 19 29 48 92
Fixed point of a function 146
Floyd, R.W. 89 178 186ff 197 199 208 218
FOL (first order logic) 188ff
Foley, M. 178 215
for statement 202
Formal language theory 10 25 70 Section
FORTRAN 4 11 60 100 114 139 204
Forwards substitution 189
Foster, J.M. 90 148 217
Free variable 225ff 234
Frege, G. 94 223
Function composition 93 118
Functional approach 5 Chapter
General minimisation 121
General recursive functions (GRF) 2 5ff Chapter 117 123 125 139
Generalised composition 93ff 125 139
| Genmin (default name for general minimisation) 121 123 142
German, S.M. 208
Global variable see "Free variable"
Goedel coding 109 131 133
Goedel Incompleteness Theorem 67 74
Goedel, K. 5 101 67ff
Goldstine, H.H. 187
Good, D.I. 208ff
goto 181 248
Grammatical analysis 10 Section 170
Graph 141
Greif, I. 208
Group 72
Grzegriczyk hierarchy Section 4.3 116 166
Grzegroczyk, A. 5 109ff
Halting problem (for TMs) 1 51ff Section 64 67 82 86 105 120
Hayes, P.J. 107
Henkin, L. 74
Herbrand base 81
Herbrand, J. 5 81
Hetzel, W.C. 179
Hilbert's tenth problem 2 71
Hilbert, D. 2 5 71 74 75 92ff
History (of a FSM) 25
Hoare's logic of programs see "Logic of programs"
Hoare, C.A.R. 3 6 8 12 103 178 189 190 Section 215ff 218 233 247
Hooper, P.K. 56
Hopcroft, J. 14 83
IAE see "Imperative applicative expression"
IAL (International Algorithmic Language) 11 83
Identity function 97
Igarishi, S. 206ff 215ff
Immortality problem (for TMs) 56
Imperative applicative expression (IAE) 218 222 238
implementation 221ff 251
Inductive assertion (approach to proving correctness) Section 7.3 209 215
Information packet 118 131
Ingermann, P.Z. 232
Initialisation (of a TM) 118 Section
Input set 20 24
Interpretation 73 79
Interpreter 40 138
Invariance (of an assertion) 198ff 206 215
Iteration 160 198
Iterative form of a recursive definition 160
j operator 239
Jones, C.B. 174
Jump 239 see
Katz, S.M. 208
King, J.C. 182ff 188 194 217
Kleene normal form theorem 110
Kleene theorem 24 91
Kleene, S.C. 5 24 25 92 106 123
Knuth, D.E. 15 38 181 187
Kreisel, G. 75
Kuhn, T. 9 15
L-value 242
Lambda abstraction 145 224 231
Lambda calculus 4 70 145 218 Section 231 243
Lambda notation 145 224
Landin, P.J. 202 218 222 224 231 240
Laski, J.G. 242
Leavenworth, B. 178
length (function) 154 163
Levitt, K.N. 182ff
Limitation of abstract machines Section 2.4
Linear bounded automaton 89
Lisp 4 12 40 70 95 100 107 143 214 215 233 242
List dynamic 11 239
LISt Processing 148
List structure 148
Location 7 50 230
Logic of programs 189 Section 206 221 233
Logic, formal 73
Logical substitution 198 202ff
London, R.L. 178 206ff 215
Loop programs 109 113ff
Lucas, P. 174 240
Luckham, D.C. 2 52 Section 75ff 206ff 215
Main loop of a TM 118 Section
Manna, Z. 13 101 178 Section
Mathematical semantics 222 223 Section
Matyasevich, A. 2 71
McCarthy's formalism 137 Section
McCarthy, J. 2 4 5 13 14 16 103 Chapter 29 40 177 214 220 240
Meaning (of a program) 10ff 15 50 94 Section 177 Chapter see
member (function) 154 161
Memory 8 50 222
META 1 209 220
Meta-computer science 1 Section 8 139
Metamathematics 1
Metatheory 1 2
Meyer, A. 109 114
Milne, R. 244
Milner, R. 218 221 239 244
Min (default name for minimisation) 106 126ff 142
Minimisation strategy 106 120 126ff
Minsky, M.L. 5 6 24 46 47 48ff 55 60 75 222
Moore, E.F. 24 27
Moore, J. 101 167
Morris, F.L. 249
Mosses, P. 244 252
Multiplication 34
Myhill, J. 67
Naur, P. 11 178 188
NIL 150 152 153
Ninety-one (91) function 14
Non-computable function 2 Section 61
Normal form of a lambda expression 71
Normal order reduction sequence 228 231
Novikov, P. 73
Nucleus 215
null (function) 154
Operational semantics 221 223 Section
Output set 20 24
Oxford school 221 Section
Painter, J. 174 177
Paradox 7 37 55 147
Parameter passing 204ff 222
Parenthesis checker 32ff
Parikh, R.J. 87
Park, D.M.R. 2 52 Section 75ff
Parse tree 86ff
Parsing 11 25 Section 170
Partial correctness 195ff 212
Pascal 198 201ff 215ff
Paterson, M.S. 2 52 Section 75ff
Path 194 197
Path condition 189 195 197 206ff 212 218 "Verification
Peano, G. 96 139
Phrase structure grammar (PSG) 84ff
Phrase structure language 85ff
PL/1 218 Section
POP-2 12 70 95 215 240
Post, E. 69ff 83 84
Predecessor function (pred) 96ff 125
Predicate 143 233
Predicate logic 1 4 73 138 188
Primitive recursion Section 4.2.2 125
Primitive recursive functions Section 4.2.2 108 111 112 116 123
Principle of Mathematical Induction 74 100
Problem solving 9 219
Procedure 70 203 218 222 227 230 231 243
productions 69 84
Productive set 64 69 71
PROGRAM 1ff
Program as constructive proof 3 57 Chapter 92 117
Program correctness 12 13 Chapter
Program machines (Minsky) Section 2.8.2
Program point 239
|
|
|
| Реклама |
|
|
|
|
|
О проекте