NDLI: Computer Science And Recursion Theory

Please wait, while we are loading the content...

The Interplay Between Mathematics And Computer Science

Stylitism, Synergism, And Syncretism: The interface of computer science and operations research

Computer Science And Recursion Theory

Computer Science Core Curriculum And Mathematics

Computer Science And Numerical Analysis

On The Difference Between Natural Language And High Level Query Languages

Impertinent Question-Answering Systems: justification and theory

Natural Language Dialogue For Managing An On-Line Calendar

Automating The Office (Panel Discussion): user experiences

A Proposed Masters Degree In Software Engineering

Educational Issues In Software Engineering

A Software Engineering Graduate Curriculum

Diagnostic And Computational Reconfiguration In Multiprocessor Systems

A Modular Computer With Petri Net Array Control

Reconfigurable Pipeline Systems

A Vocational - Technical High School Program

Small Business—A Gold Mine For D.P. Educators

Validating The Utility Of Abstraction Techniques

The Euclid Language: a progress report

A Report On The Development Of Gypsy

Aspects Of Implementing CLU

Congressional Reliance On And Use Of Computers

Federal Funding For Basic Research In Computer Science

Computer Science And Graduate Education In Applied Mathematics

Complexity Of Computations

Computer Science And Statistics

Computer Related Curricular Changes In Traditional Mathematics

Some Comments On EQS, A Near Term Natural Language Data Base Query System

The ROBOT System: Natural language processing applied to data base query

Rapidly Extendable Natural Language

Working In The Computing And Engineering Profession: Career planning and educational alternatives

Obsolescence Of The Computing Professional: The problem and possible solutions

How Women Can Advance In Management (Presentation Abstract): A perspective

Why Managers Fail(Presentation Abstract)

Opportunities For Computer Scientists And Engineers In The Federal Government (Presentation Abstract): A perspective

Employing A Deaf Programmer

Automating The Office: User experiences 2

A System For Office Automation Research

Implications Of VLSI On Computer Design(Panel Discussion)

Communication In X-TREE, A Modular Multiprocessor System

A Powerful Modular Computer On A Universal Building Module

Incomplete Fault Coverage In Modular Miltiprocessor Systems

A Program Generator Package For Management Of Data Files—The Input Language

A Utility For The Generation Of A Preliminary Data/Dictionary Directory

QUEASY: The design and implementation of a management information system for casual users

Data Usage And The Data Base Processor

Parallel Compilation In A Multiprocessor Environment (Extended Abstract)

Engineering A Program Optimizer

Direct Execution Of An Algebraic Oriented Language

A Family Of Pass-Oriented Attribute Grammar Evaluators

Software Quality And Reliability

Managing Federal Government Computer Installations

Why A Curriculum In Health Computing?

Health Computing: Curriculum for an emerging profession - report of the ACM curriculum committee on health computing education

Characteristics And Problems Encountered In Different Database Applications (Panel Discussion)

Extending The Power Of Decision Support Systems 1 And 2 (Panel Discussions)

Office Work Station Networks

Direct Execution In A High-Level Computer Architecture

The Pica-B Computer An Abstract Target Machine For A Transportable Single-User Operating Environment

Programming Distributed Systems

Multiprocessor Architectures For Concurrent Programs

How Fast Should EFT Be Moving? (Panel Discussion)

Crossfertilization Of DBMS Research With Other Disciplines Of Computer Science (Panel Discussion)

Programming Language Standards From A User's Point Of View (Panel Discussion)

A Simulation Support System Capable Of Control, Monitoring And Simulation Of Airborne Systems

Real-Time Simulation For Verification Of Tactical Electronic Warfare System

A Syntactic Schema And Algorithm For Language Arts CAI

A Processor For Providing Friendly Environments For Frequently Used Application Packages

Proposal For A Shared Resource Computing Utility

An Introduction To DIAM Levels Of Abstraction In Accessing Information

Dynamic Binary Search Trees

A Relational Problem Definition Language For Structured Data Processing

Software Blueprints

Factored Specifications In The Synthesis Of LISP Functions

The Federal Computer Professional In The 1980'S: Impact of the president's reorganization project

Implications Of The President's Reorganization Project On Government Data Processing

What Employers Look For In Hiring Computer Science Graduates (Panel Discussion)

What Employers Look For In Hiring Computer Science Graduates (Panel Discussion)

What Employers Look For In Hiring Computer Science Graduates (Panel Discussion)

What Employers Look For In Hiring Computer Science Graduates (Panel Discussion)

A Formal Theory Of Language Acquisition

Inferring Conceptual Structures From Pictorial Input

Conditions On Acquisitional Models

Case Studies On The Implementation And Use Of Database Management Systems (Panel Discussion): Experience with resistance

New Communications For The Office Of The Future (Panel Discussion): Strategies and barriers

Modeling Computer Privacy Costs

Executive Support For Urban Technology: The case of computing

The Lattice Security Model In A Public Computing Network

Notations For Software Specification And Design (Panel Discussion)

People-Oriented Computer Systems (Panel Discussion): When, and how?

On Bounding Distributions For Stochastic Networks

Closed-Form Statistical Estimates Of Optimal Solution Values To Combinatorial Problems

Some Open Problems In Cryptography

Tools For Automatic Compiler Generation (Panel Discussion)

Tools For Automatic Compiler Generation (Panel Discussion)

Tools For Automatic Compiler Generation (Panel Discussion)

Alternative Approaches To Wiring The Office Of The Future (Panel Discussion)

Alternative Approaches To Wiring The Office Of The Future (Panel Discussion)

Alternative Approaches To Wiring The Office Of The Future (Panel Discussion)

On A System For Adaptive, Parallel Finite Element Computations

An Engineering Analysis System

An Analysis Of Recurrent Software Errors In A Real-Time Control System

Computer Science And Recursion Theory

Content Provider	ACM Digital Library
Author	Pour-El, Marian Boykan
Abstract	One of the basic concerns of classical mathematical logic has been a rigorous definition of “mathematical proof". A proof may be discovered by luck, genius or accident. But once discovered it is mechanically checkable. Thus the most general type of mechanically checkable procedure provides a definition of the most general kind of proof. An investigation of “mechanical checkability" leads naturally to the notion of “computable process". Recursion theory is that branch of mathematical logic which studies computability theory. From its very inception recursion theory has been so closely associated with theoretical computer science that it is sometimes difficult to tell where one begins and the other ends. Both appear to have a common origin in the 1930's and 1940's - when the fundamental results of Turing, Post, Herbrand-Gödel, Kleene and Church on computability were obtained [52,53,35,36,19,25,26,11,12,13]. Although the work of each of these authors is based on a different intuition as to the nature of computability, they all share a common feature. In each, the approach is discrete and atomic. No attempt was made to use machines with continuously varying parameters - e.g. analog computers - as a basis for understanding computability. The author finds this regrettable and is trying to remedy the situation [39]. At all events, all of these discrete, atomic definitions have been proved to be equivalent. It is now widely accepted that the concept “computable function of natural numbers" is correctly identified with “partial recursive function". Lack of space forces us to be selective rather than exhaustive. We discuss briefly five areas of interest to the computer scientist. The purpose of this paper is to explore the interaction of recursion theory with computer science in these areas. We consider, not only similarities between the two fields, but also points of difference. We discuss how recursion theory supplied computer science with specific mathematical definitions and techniques. We also consider how the computer scientist shaped (and is still shaping) this recursion-theoretic material to his own needs. The five areas are not mutually exclusive: there are numerous connections between them. In the interest of clarity and brevity, reference is made only to those works which are easily understandable to the beginner. No attempt is made to make the bibliography complete or up-to-date.
Starting Page	15
Ending Page	20
Page Count	6
File Format	PDF
ISBN	0897910001
DOI	10.1145/800127.804061
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	1978-12-04
Publisher Place	New York
Access Restriction	Subscribed
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in