483:
59:
The definition of an effective method involves more than the method itself. In order for a method to be called effective, it must be considered with respect to a class of problems. Because of this, one method may be effective with respect to one class of problems and
108:
Optionally, it may also be required that the method never returns a result as if it were an answer when the method is applied to a problem from
47:
is a procedure for solving a problem by any intuitively 'effective' means from a specific class. An effective method is sometimes also called a
271:
136:
Several independent efforts to give a formal characterization of effective calculability led to a variety of proposed definitions (
412:
524:
344:
195:
407:
452:
316:
437:
553:
548:
462:
457:
395:
224:
137:
112:
its class. Adding this requirement reduces the set of classes for which there is an effective method.
160:
517:
380:
156:
400:
337:
67:
A method is formally called effective for a class of problems when it satisfies these criteria:
432:
148:) that later were shown to be equivalent. The notion captured by these definitions is known as
558:
427:
422:
374:
180:
36:
498:
8:
510:
368:
205:
164:
149:
125:
543:
330:
168:
312:
190:
185:
28:
93:
In principle, it can be done by a human without any aids except writing materials.
357:
322:
242:
494:
447:
141:
537:
267:
200:
145:
229:
Metalogic: An
Introduction to the Metatheory of Standard First-Order Logic
442:
385:
24:
72:
101:
266:
124:. Functions for which an effective method exists are sometimes called
417:
353:
121:
32:
167:. As this is not a mathematical statement, it cannot be proven by a
120:
An effective method for calculating the values of a function is an
482:
97:
490:
20:
16:
Problem-solving procedures with certain characteristics
243:"Church's Thesis and the Principles for Mechanisms"
352:
535:
270:; Copeland, Jack; Proudfoot, Diane (June 2000).
78:When it is applied to a problem from its class:
64:be effective with respect to a different class.
518:
338:
278:. Turing Archive for the History of Computing
260:
100:to succeed. In other words, it requires no
525:
511:
345:
331:
159:states that the two notions coincide: any
96:Its instructions need only to be followed
296:The Cambridge Dictionary of Philosophy,
218:
131:
536:
231:, University of California Press, 1971
326:
319:, pp. 233 ff., esp. p. 231.
240:
75:number of exact, finite instructions.
477:
150:recursive or effective computability
88:It always produces a correct answer.
13:
196:Effective results in number theory
163:that is effectively calculable is
14:
570:
85:) after a finite number of steps.
481:
413:Gödel's incompleteness theorems
290:
234:
1:
211:
115:
54:
497:. You can help Knowledge by
408:Gödel's completeness theorem
7:
174:
138:general recursive functions
10:
575:
476:
396:Foundations of mathematics
311:. Reprinted, Dover, 2002,
272:"The Turing-Church Thesis"
364:
161:number-theoretic function
438:Löwenheim–Skolem theorem
463:Use–mention distinction
493:-related article is a
458:Type–token distinction
165:recursively computable
126:effectively calculable
554:Theory of computation
307:S. C. Kleene (1967),
241:Gandy, Robin (1980).
51:method or procedure.
549:Computability theory
381:Church–Turing thesis
375:Entscheidungsproblem
247:The Kleene Symposium
181:Decidability (logic)
157:Church–Turing thesis
132:Computable functions
81:It always finishes (
37:computability theory
298:effective procedure
206:Undecidable problem
45:effective procedure
309:Mathematical logic
169:mathematical proof
506:
505:
471:
470:
71:It consists of a
566:
527:
520:
513:
485:
478:
391:Effective method
369:Cantor's theorem
347:
340:
333:
324:
323:
300:
294:
288:
287:
285:
283:
264:
258:
257:
255:
253:
238:
232:
225:Hunter, Geoffrey
222:
191:Function problem
186:Decision problem
41:effective method
29:computer science
574:
573:
569:
568:
567:
565:
564:
563:
534:
533:
532:
531:
474:
472:
467:
360:
358:metamathematics
351:
304:
303:
295:
291:
281:
279:
265:
261:
251:
249:
239:
235:
223:
219:
214:
177:
142:Turing machines
134:
118:
57:
17:
12:
11:
5:
572:
562:
561:
556:
551:
546:
530:
529:
522:
515:
507:
504:
503:
486:
469:
468:
466:
465:
460:
455:
450:
448:Satisfiability
445:
440:
435:
433:Interpretation
430:
425:
420:
415:
410:
405:
404:
403:
393:
388:
383:
378:
371:
365:
362:
361:
350:
349:
342:
335:
327:
321:
320:
302:
301:
289:
276:AlanTuring.net
268:Copeland, B.J.
259:
233:
216:
215:
213:
210:
209:
208:
203:
198:
193:
188:
183:
176:
173:
133:
130:
117:
114:
106:
105:
94:
91:
90:
89:
86:
76:
56:
53:
15:
9:
6:
4:
3:
2:
571:
560:
557:
555:
552:
550:
547:
545:
542:
541:
539:
528:
523:
521:
516:
514:
509:
508:
502:
500:
496:
492:
487:
484:
480:
479:
475:
464:
461:
459:
456:
454:
451:
449:
446:
444:
441:
439:
436:
434:
431:
429:
426:
424:
421:
419:
416:
414:
411:
409:
406:
402:
399:
398:
397:
394:
392:
389:
387:
384:
382:
379:
377:
376:
372:
370:
367:
366:
363:
359:
355:
348:
343:
341:
336:
334:
329:
328:
325:
318:
317:0-486-42533-9
314:
310:
306:
305:
299:
293:
277:
273:
269:
263:
248:
244:
237:
230:
226:
221:
217:
207:
204:
202:
201:Recursive set
199:
197:
194:
192:
189:
187:
184:
182:
179:
178:
172:
170:
166:
162:
158:
153:
151:
147:
143:
139:
129:
127:
123:
113:
111:
103:
99:
95:
92:
87:
84:
80:
79:
77:
74:
70:
69:
68:
65:
63:
52:
50:
46:
42:
38:
34:
31:, especially
30:
26:
22:
499:expanding it
488:
473:
453:Independence
428:Decidability
423:Completeness
390:
373:
308:
297:
292:
280:. Retrieved
275:
262:
250:. Retrieved
246:
236:
228:
220:
154:
135:
119:
109:
107:
82:
66:
61:
58:
48:
44:
40:
18:
559:Logic stubs
443:Metatheorem
401:of geometry
386:Consistency
104:to succeed.
25:mathematics
538:Categories
212:References
146:λ-calculus
116:Algorithms
98:rigorously
83:terminates
55:Definition
49:mechanical
544:Metalogic
418:Soundness
354:Metalogic
122:algorithm
102:ingenuity
33:metalogic
282:23 March
252:19 April
175:See also
110:outside
315:
73:finite
491:logic
489:This
39:, an
21:logic
495:stub
356:and
313:ISBN
284:2013
254:2024
155:The
35:and
27:and
62:not
43:or
19:In
540::
274:.
245:.
227:,
171:.
152:.
144:,
140:,
128:.
23:,
526:e
519:t
512:v
501:.
346:e
339:t
332:v
286:.
256:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.