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