331:. It states that physical computing systems are types of mechanisms that, by design, perform physical computation, or the manipulation (by a functional mechanism) of a "medium-independent" vehicle according to a rule. "Medium-independence" requires that the property can be instantiated by multiple realizers and multiple mechanisms, and that the inputs and outputs of the mechanism also be
294:
summary of this account states that a physical system can be said to perform a specific computation when there is a mapping between the state of that system and the computation such that the "microphysical states mirror the state transitions between the computational states."
311:
content be a necessary condition for computation (that is, what differentiates an arbitrary physical system from a computing system is that the operands of the computation represent something). This notion attempts to prevent the logical abstraction of the mapping account of
335:. In short, medium-independence allows for the use of physical variables with properties other than voltage (as in typical digital computers); this is imperative in considering other types of computation, such as that which occurs in the
245:
83:, but agreement on a suitable definition proved elusive. A candidate definition was proposed independently by several mathematicians in the 1930s. The best-known variant was formalised by the mathematician
488:
418:
with discrete time and discrete state space. He maintains that a computational system is a complex object which consists of three parts. First, a mathematical dynamical system
156:. It remains an open question as to whether there exists a more powerful definition of 'well-defined' that is able to capture both computable and 'non-computable' statements.
571:
148:
Despite the widespread uptake of this definition, there are some mathematical concepts that have no well-defined characterisation under this definition. This includes
535:
594:
439:
614:
508:
219:
Calculations or statements which are ill-defined, such that they cannot be unambiguously encoded into a Turing machine: ("Paul loves me twice as much as Joe").
87:, who defined a well-defined statement or calculation as any statement that could be expressed in terms of the initialisation parameters of a
1058:
1006:
851:
793:
765:
222:
Problem statements which do appear to be well-defined, but for which it can be proved that no Turing machine exists to solve them (such as
740:
981:
937:
249:, demonstrated that there is a formal equivalence between computable statements and particular physical systems, commonly called
141:
Turing's definition apportioned "well-definedness" to a very large class of mathematical statements, including all well-formed
382:
1063:
168:
58:
343:. A rule, in this sense, provides a mapping among inputs, outputs, and internal states of the physical computing system.
701:
172:
79:
The notion that mathematical statements should be 'well-defined' had been argued by mathematicians since at least the
115:
444:
378:
332:
810:
640:
635:
358:
328:
47:
43:
625:
362:
352:
130:
Today, any formal statement or calculation that exhibits this quality of well-definedness is termed
324:
291:
287:
262:
223:
149:
911:
374:
1035:
1002:
977:
933:
847:
789:
761:
736:
540:
394:
194:
361:, a diversity of mathematical models of computation has been developed. Typical mathematical
903:
876:
821:
665:
645:
630:
415:
340:
258:
68:
513:
404:
388:
313:
266:
254:
236:
97:
688:
576:
421:
599:
493:
370:
201:
88:
80:
1052:
1023:
283:
92:
915:
207:
The majority of mathematical statements and calculations given in maths textbooks.
400:
304:
153:
84:
39:
825:
235:
Computation can be seen as a purely physical process occurring inside a closed
907:
880:
709:
183:
51:
35:
1039:
867:
Davis, Martin (2006). "Why there is no such discipline as hypercomputation".
17:
308:
250:
142:
120:
441:
with discrete time and discrete state space; second, a computational setup
307:
have suggested various accounts of computation with the restriction that
240:
179:
106:
102:
63:
894:
Godfrey-Smith, P. (2009), "Triviality
Arguments against Functionalism",
811:"On Computable Numbers, with an Application to the Entscheidungsproblem"
163:
All statements characterised in modern programming languages, including
282:
An alternative account of computation is found throughout the works of
145:, and all statements written in modern computer programming languages.
246:
On
Computable Numbers, with an Application to the Entscheidungsproblem
159:
Some examples of mathematical statements that are computable include:
187:
110:
316:, the idea that everything can be said to be computing everything.
164:
336:
134:, while the statement or calculation itself is referred to as a
1024:"What is a Physical Realization of a Computational System?"
42:
that is well-defined. Common examples of computation are
91:. Other (mathematically equivalent) definitions include
702:"Computation: Definition and Synonyms from Answers.com"
664:
The study of non-computable statements is the field of
410:
Giunti calls the models studied by computation theory
837:
835:
602:
579:
543:
516:
496:
447:
424:
733:
la
Logique de Leibniz a'Après des Documents Inédits
71:is a field that involves the study of computation.
608:
588:
565:
529:
502:
482:
433:
211:Some examples of mathematical statements that are
61:, people) that perform computations are known as
414:and he argues that all of them are mathematical
976:. Oxford: Oxford University Press. p. 10.
932:. Oxford: Oxford University Press. p. 18.
257:, human mathematicians following strict rules,
953:Fodor, J. A. (1986), "The Mind-Body Problem",
818:Proceedings of the London Mathematical Society
290:has dubbed this the "simple mapping account."
8:
327:proposes an account of computation based on
974:Physical Computation: A Mechanistic Account
930:Physical Computation: A Mechanistic Account
178:All calculations carried by an electronic
601:
578:
548:
542:
521:
515:
495:
490:, which is made up of a theoretical part
469:
446:
423:
253:. Examples of such physical systems are:
842:Davis, Martin; Davis, Martin D. (2000).
756:Davis, Martin; Davis, Martin D. (2000).
691:from the Free Merriam-Webster Dictionary
779:
777:
681:
657:
483:{\displaystyle H=\left(F,B_{F}\right)}
57:Mechanical or electronic devices (or,
1001:. New York: Oxford University Press.
7:
999:Computation, Dynamics, and Cognition
820:. 2. Vol. 42. pp. 230–65.
869:Applied Mathematics and Computation
573:, which links the dynamical system
273:Alternative accounts of computation
231:The Physical process of computation
193:All calculations carried out on an
200:All calculations carried out on a
25:
786:Computability & Unsolvability
846:. W. W. Norton & Company.
760:. W. W. Norton & Company.
1:
972:Piccinini, Gualtiero (2015).
928:Piccinini, Gualtiero (2015).
1059:Theoretical computer science
784:Davis, Martin (1982-01-01).
399:Concurrent models including
387:Functional models including
537:; third, an interpretation
1080:
1028:Isonomia -- Epistemologica
350:
908:10.1007/s11098-008-9231-3
881:10.1016/j.amc.2005.09.066
393:Logical models including
826:10.1112/plms/s2-42.1.230
731:Couturat, Louis (1901).
566:{\displaystyle I_{DS,H}}
788:. Courier Corporation.
369:State models including
320:The mechanistic account
243:. Turing's 1937 proof,
27:Any type of calculation
1022:Giunti, Marco (2017),
997:Giunti, Marco (1997).
844:The Universal Computer
809:Turing, A.M. (1937) .
758:The Universal Computer
610:
590:
567:
531:
504:
484:
435:
412:computational systems,
379:finite state automaton
896:Philosophical Studies
641:Limits of computation
636:Computational problem
611:
591:
568:
532:
530:{\displaystyle B_{F}}
505:
485:
436:
359:theory of computation
329:mechanical philosophy
303:Philosophers such as
292:Gualtiero Piccinini's
116:general recursiveness
44:mathematical equation
1064:Computability theory
626:Computability theory
600:
577:
541:
514:
494:
445:
422:
353:Model of computation
299:The semantic account
263:mechanical computers
215:computable include:
154:the busy beaver game
143:algebraic statements
955:Scientific American
712:on 22 February 2009
365:are the following:
363:models of computers
347:Mathematical models
333:multiply realizable
325:Gualtiero Piccinini
314:pancomputationalism
288:Peter Godfrey-Smith
278:The mapping account
224:the halting problem
150:the halting problem
98:lambda-definability
606:
589:{\displaystyle DS}
586:
563:
527:
510:, and a real part
500:
480:
434:{\displaystyle DS}
431:
375:pushdown automaton
38:or non-arithmetic
1008:978-0-19-509009-3
853:978-0-393-04785-1
795:978-0-486-61471-7
767:978-0-393-04785-1
609:{\displaystyle H}
503:{\displaystyle F}
416:dynamical systems
395:logic programming
259:digital computers
195:analytical engine
16:(Redirected from
1071:
1043:
1042:
1019:
1013:
1012:
994:
988:
987:
969:
963:
962:
950:
944:
943:
925:
919:
918:
891:
885:
884:
864:
858:
857:
839:
830:
829:
815:
806:
800:
799:
781:
772:
771:
753:
747:
746:
728:
722:
721:
719:
717:
708:. Archived from
698:
692:
686:
669:
666:hypercomputation
662:
646:Computationalism
631:Hypercomputation
615:
613:
612:
607:
595:
593:
592:
587:
572:
570:
569:
564:
562:
561:
536:
534:
533:
528:
526:
525:
509:
507:
506:
501:
489:
487:
486:
481:
479:
475:
474:
473:
440:
438:
437:
432:
341:quantum computer
267:analog computers
69:Computer science
46:solving and the
21:
1079:
1078:
1074:
1073:
1072:
1070:
1069:
1068:
1049:
1048:
1047:
1046:
1021:
1020:
1016:
1009:
996:
995:
991:
984:
971:
970:
966:
952:
951:
947:
940:
927:
926:
922:
893:
892:
888:
866:
865:
861:
854:
841:
840:
833:
813:
808:
807:
803:
796:
783:
782:
775:
768:
755:
754:
750:
743:
730:
729:
725:
715:
713:
700:
699:
695:
687:
683:
678:
673:
672:
663:
659:
654:
622:
598:
597:
596:with the setup
575:
574:
544:
539:
538:
517:
512:
511:
492:
491:
465:
458:
454:
443:
442:
420:
419:
405:process calculi
389:lambda calculus
355:
349:
322:
301:
280:
275:
255:Turing machines
237:physical system
233:
77:
34:is any type of
28:
23:
22:
15:
12:
11:
5:
1077:
1075:
1067:
1066:
1061:
1051:
1050:
1045:
1044:
1014:
1007:
989:
982:
964:
961:(January 1986)
945:
938:
920:
886:
859:
852:
831:
801:
794:
773:
766:
748:
742:978-0343895099
741:
723:
693:
680:
679:
677:
674:
671:
670:
656:
655:
653:
650:
649:
648:
643:
638:
633:
628:
621:
618:
605:
585:
582:
560:
557:
554:
551:
547:
524:
520:
499:
478:
472:
468:
464:
461:
457:
453:
450:
430:
427:
408:
407:
397:
391:
385:
371:Turing machine
351:Main article:
348:
345:
321:
318:
300:
297:
279:
276:
274:
271:
232:
229:
228:
227:
220:
209:
208:
205:
202:Turing Machine
198:
191:
176:
125:1-definability
89:Turing machine
76:
73:
26:
24:
14:
13:
10:
9:
6:
4:
3:
2:
1076:
1065:
1062:
1060:
1057:
1056:
1054:
1041:
1037:
1033:
1029:
1025:
1018:
1015:
1010:
1004:
1000:
993:
990:
985:
983:9780199658855
979:
975:
968:
965:
960:
956:
949:
946:
941:
939:9780199658855
935:
931:
924:
921:
917:
913:
909:
905:
902:(2): 273–95,
901:
897:
890:
887:
882:
878:
874:
870:
863:
860:
855:
849:
845:
838:
836:
832:
827:
823:
819:
812:
805:
802:
797:
791:
787:
780:
778:
774:
769:
763:
759:
752:
749:
744:
738:
734:
727:
724:
711:
707:
703:
697:
694:
690:
685:
682:
675:
667:
661:
658:
651:
647:
644:
642:
639:
637:
634:
632:
629:
627:
624:
623:
619:
617:
603:
583:
580:
558:
555:
552:
549:
545:
522:
518:
497:
476:
470:
466:
462:
459:
455:
451:
448:
428:
425:
417:
413:
406:
402:
398:
396:
392:
390:
386:
384:
380:
376:
372:
368:
367:
366:
364:
360:
354:
346:
344:
342:
338:
334:
330:
326:
319:
317:
315:
310:
306:
298:
296:
293:
289:
285:
284:Hilary Putnam
277:
272:
270:
268:
264:
260:
256:
252:
248:
247:
242:
238:
230:
225:
221:
218:
217:
216:
214:
206:
203:
199:
196:
192:
189:
185:
181:
177:
174:
170:
166:
162:
161:
160:
157:
155:
151:
146:
144:
139:
137:
133:
128:
126:
122:
118:
117:
112:
108:
104:
100:
99:
94:
93:Alonzo Church
90:
86:
82:
74:
72:
70:
66:
65:
60:
55:
53:
49:
45:
41:
37:
33:
19:
18:Computational
1031:
1027:
1017:
998:
992:
973:
967:
958:
954:
948:
929:
923:
899:
895:
889:
872:
868:
862:
843:
817:
804:
785:
757:
751:
732:
726:
714:. Retrieved
710:the original
705:
696:
684:
660:
411:
409:
356:
323:
302:
286:and others.
281:
269:and others.
244:
234:
212:
210:
158:
147:
140:
135:
131:
129:
124:
114:
96:
78:
75:Introduction
62:
59:historically
56:
50:of computer
31:
29:
706:Answers.com
689:Computation
401:actor model
305:Jerry Fodor
136:computation
85:Alan Turing
40:calculation
32:computation
1053:Categories
1034:: 177–92,
875:(1): 4–7.
676:References
184:calculator
132:computable
52:algorithms
36:arithmetic
1040:2037-4348
735:. Paris.
251:computers
239:called a
121:Emil Post
64:computers
48:execution
916:73619367
716:26 April
620:See also
339:or in a
309:semantic
241:computer
180:computer
103:Herbrand
357:In the
1038:
1005:
980:
936:
914:
850:
792:
764:
739:
381:, and
188:abacus
171:, and
169:Python
111:Kleene
912:S2CID
814:(PDF)
652:Notes
337:brain
107:Gödel
81:1600s
1036:ISSN
1003:ISBN
978:ISBN
934:ISBN
848:ISBN
790:ISBN
762:ISBN
737:ISBN
718:2017
403:and
383:PRAM
173:Java
152:and
119:and
959:244
904:doi
900:145
877:doi
873:178
822:doi
213:not
186:or
165:C++
123:'s
113:'s
95:'s
1055::
1030:,
1026:,
957:,
910:,
898:,
871:.
834:^
816:.
776:^
704:.
616:.
377:,
373:,
265:,
261:,
226:).
182:,
167:,
138:.
127:.
101:,
67:.
54:.
30:A
1032:9
1011:.
986:.
942:.
906::
883:.
879::
856:.
828:.
824::
798:.
770:.
745:.
720:.
668:.
604:H
584:S
581:D
559:H
556:,
553:S
550:D
546:I
523:F
519:B
498:F
477:)
471:F
467:B
463:,
460:F
456:(
452:=
449:H
429:S
426:D
204:.
197:.
190:.
175:.
109:-
105:-
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.