DocumentCode :
1338924
Title :
Real-Time Computation and Recursive Functions Not Real-Time Computable
Author :
Yamada, Hisao
Author_Institution :
IBM Thomas J. Watson Research Center, Yorktown Hgts., N. Y.
Issue :
6
fYear :
1962
Firstpage :
753
Lastpage :
760
Abstract :
As an attempt to investigate a general theory of real-time computability in digital computers, a subclass of Turing machines is formally introduced together with some classes of functions that are computable by them in real time. Then the existence is established of a class of recursive functions that are not computable in real time by use of a class of machines, no matter how general we make the machines subject to a given constraint.
Keywords :
Application software; Automata; Computer applications; Costs; Mathematical model; Network synthesis; Tellurium; Testing; Tree data structures; Upper bound;
fLanguage :
English
Journal_Title :
Electronic Computers, IRE Transactions on
Publisher :
ieee
ISSN :
0367-9950
Type :
jour
DOI :
10.1109/TEC.1962.5219459
Filename :
5219459
Link To Document :
بازگشت