Authors:
(1) Lenore Blum (lblum@cs.cmu.edu);
(2) Manuel Blum (mblum@cs.cmu.edu). Table of Links Abstract and 1 Introduction 2 Brief Overview of CtmR, a Robot with a CTM Brain 2.1 Formal Definition of CtmR 2.2 Conscious Attention in CtmR 2.3 Conscious Awareness and the Feeling of Consciousness in CtmR 2.4 CtmR as a Framework for Artificial General Intelligence (AGI) 3 Alignment of CtmR with Other Theories of Consciousness 4 Addressing Kevin Mitchell’s questions from the perspective of CtmR 5 Summary and Conclusions 6 Acknowledgements 7 Appendix 7.1 A Brief History of the Theoretical Computer Science Approach to Computation 7.2 The Probabilistic Competition for Conscious Attention and the Influence of Disposition on it References 7.1 A Brief History of the Theoretical Computer Science Approach to Computation The theoretical computer science approach to computation starts with Alan Turing in the 1930’s and focuses on the question, “What is computable (decidable) and what is not?” (Turing, 1937). Turing defined a simple formal model of computation, which we now call the Turing Machine (TM) and defined a function to be computable if and only if it can be realized as the input-output map of a TM. The formal definition of a TM (program) also provides a formal definition of the informal concept of algorithm. Using his model, Turing proved properties (theorems) of computable functions, including the existence of universal computable functions (universal Turing machines) and the fact that some functions are not computable. The former foresees the realization of general purpose programmable computers; the latter that some problems cannot be decided even by the most powerful computers. For example, Turing shows there is no Turing machine (Turing computable function) that given the description of a TM M and an input x, outputs 1 if M on input x (eventually) halts, and 0 if not. This is known as the “halting problem” and is equivalent to Gödel’s theorem on the undecidability of arithmetic. But why should we believe the Church-Turing Thesis, suggested first in (Turing, 1937), that the TM embodies the informal notion of computability (decidability)? That’s because each of a great many very different independently defined models of discrete computation, including TMs and Alonzo Church’s effective calculability (Church, 1936), define exactly the same class of functions, the computable functions. In programming parlance, all sufficiently powerful practical programming languages are equivalent in that any one can simulate (be compiled into) any other. The ensuing mathematical theory is often called the Theory of Computation (TOC). In the 1960’s, with the wider accessibility of computers, newly minted theoretical computer scientists such as Jack Edmonds (Edmonds, 1965) and Richard Karp (Karp, 1972), pointed out that resources matter. Certain problems that in principle were decidable, were seemingly intractable given feasible time and space resources. Even more, intractability seemed to be an intrinsic property of the problem, not the method of solution or the implementing machine. The ensuing sub-theory of TOC, which introduces resource constraints into what is or is not computable efficiently, is called Theoretical Computer Science (TCS). TCS focuses on the question, “What is or is not computable (decidable) given limited resources?” A key problem here is the deceivingly simple “SAT problem”: Given a boolean formula �, is it satisfiable, meaning is there a truth assignment to its variables that makes formula � true? This problem is decidable. Here is a decision procedure: Given a boolean formula � with n variables, systematically check to see if any of the 2n possible truth assignments makes the formula true. If yes, output 1, otherwise output 0. This brute force procedure takes exponential(n) time in general. But is the “SAT problem” tractable, meaning decidable efficiently, i.e., in polynomial(n) time? This is equivalent to the well-known P = NP? problem of (Cook, 1971), (Karp, 1972), (Levin, 1973). The design of novel and efficient algorithms is a key focus of TCS. Turning the table on its head, the ability to exploit the power of hard problems, problems that cannot be solved efficiently, has been a key insight of TCS. An example is the definition of pseudorandomness. This ability to exploit the power of hardness is novel for mathematics. This paper is available on arxiv under CC BY 4.0 DEED license. Authors: (1) Lenore Blum (lblum@cs.cmu.edu); (2) Manuel Blum (mblum@cs.cmu.edu). Authors: Authors: (1) Lenore Blum (lblum@cs.cmu.edu); (2) Manuel Blum (mblum@cs.cmu.edu). Table of Links Abstract and 1 Introduction Abstract and 1 Introduction 2 Brief Overview of CtmR, a Robot with a CTM Brain 2.1 Formal Definition of CtmR 2.1 Formal Definition of CtmR 2.2 Conscious Attention in CtmR 2.2 Conscious Attention in CtmR 2.3 Conscious Awareness and the Feeling of Consciousness in CtmR 2.3 Conscious Awareness and the Feeling of Consciousness in CtmR 2.4 CtmR as a Framework for Artificial General Intelligence (AGI) 2.4 CtmR as a Framework for Artificial General Intelligence (AGI) 3 Alignment of CtmR with Other Theories of Consciousness 3 Alignment of CtmR with Other Theories of Consciousness 4 Addressing Kevin Mitchell’s questions from the perspective of CtmR 4 Addressing Kevin Mitchell’s questions from the perspective of CtmR 5 Summary and Conclusions 5 Summary and Conclusions 6 Acknowledgements 6 Acknowledgements 7 Appendix 7.1 A Brief History of the Theoretical Computer Science Approach to Computation 7.1 A Brief History of the Theoretical Computer Science Approach to Computation 7.2 The Probabilistic Competition for Conscious Attention and the Influence of Disposition on it 7.2 The Probabilistic Competition for Conscious Attention and the Influence of Disposition on it References References 7.1 A Brief History of the Theoretical Computer Science Approach to Computation The theoretical computer science approach to computation starts with Alan Turing in the 1930’s and focuses on the question, “What is computable (decidable) and what is not?” (Turing, 1937). Turing defined a simple formal model of computation, which we now call the Turing Machine (TM) and defined a function to be computable if and only if it can be realized as the input-output map of a TM. The formal definition of a TM (program) also provides a formal definition of the informal concept of algorithm. Using his model, Turing proved properties (theorems) of computable functions, including the existence of universal computable functions (universal Turing machines) and the fact that some functions are not computable. The former foresees the realization of general purpose programmable computers; the latter that some problems cannot be decided even by the most powerful computers. For example, Turing shows there is no Turing machine (Turing computable function) that given the description of a TM M and an input x, outputs 1 if M on input x (eventually) halts, and 0 if not. This is known as the “halting problem” and is equivalent to Gödel’s theorem on the undecidability of arithmetic. But why should we believe the Church-Turing Thesis, suggested first in (Turing, 1937), that the TM embodies the informal notion of computability (decidability)? That’s because each of a great many very different independently defined models of discrete computation, including TMs and Alonzo Church’s effective calculability (Church, 1936), define exactly the same class of functions, the computable functions. In programming parlance, all sufficiently powerful practical programming languages are equivalent in that any one can simulate (be compiled into) any other. The ensuing mathematical theory is often called the Theory of Computation (TOC). In the 1960’s, with the wider accessibility of computers, newly minted theoretical computer scientists such as Jack Edmonds (Edmonds, 1965) and Richard Karp (Karp, 1972), pointed out that resources matter. Certain problems that in principle were decidable, were seemingly intractable given feasible time and space resources. Even more, intractability seemed to be an intrinsic property of the problem, not the method of solution or the implementing machine. The ensuing sub-theory of TOC, which introduces resource constraints into what is or is not computable efficiently, is called Theoretical Computer Science (TCS). TCS focuses on the question, “What is or is not computable (decidable) given limited resources?” A key problem here is the deceivingly simple “SAT problem”: Given a boolean formula �, is it satisfiable, meaning is there a truth assignment to its variables that makes formula � true? This problem is decidable. Here is a decision procedure: Given a boolean formula � with n variables, systematically check to see if any of the 2n possible truth assignments makes the formula true. If yes, output 1, otherwise output 0. This brute force procedure takes exponential(n) time in general. But is the “SAT problem” tractable, meaning decidable efficiently, i.e., in polynomial(n) time? This is equivalent to the well-known P = NP? problem of (Cook, 1971), (Karp, 1972), (Levin, 1973). The design of novel and efficient algorithms is a key focus of TCS. Turning the table on its head, the ability to exploit the power of hard problems, problems that cannot be solved efficiently, has been a key insight of TCS. An example is the definition of pseudorandomness. This ability to exploit the power of hardness is novel for mathematics. This paper is available on arxiv under CC BY 4.0 DEED license. This paper is available on arxiv under CC BY 4.0 DEED license. available on arxiv

Part of HackerNoon's growing list of open-source research papers, promoting free access to academic material.

A Brief History of the Theoretical Computer Science Approach to Computation

About Author

Comments

TOPICS

THIS ARTICLE WAS FEATURED IN

Related Stories

Addressing Kevin Mitchell’s Questions From the Perspective of Conscious Turing Machine Robots

The Noonification: How Often Do NFTs Pass The Howey Test? (1/13/2023)

Darwin's Hybrid Intelligence to Align AI & Human Goals for Startups & VCs

The Noonification: White Man (11/26/2022)

The Noonification: The Metaverse is a Sh*tshow (11/2/2022)

100 Days of AI Day 1: From Newsletter to Podcast, Leveraging AI for Audio Transformation

Addressing Kevin Mitchell’s Questions From the Perspective of Conscious Turing Machine Robots

The Noonification: How Often Do NFTs Pass The Howey Test? (1/13/2023)

Darwin's Hybrid Intelligence to Align AI & Human Goals for Startups & VCs

The Noonification: White Man (11/26/2022)

The Noonification: The Metaverse is a Sh*tshow (11/2/2022)

100 Days of AI Day 1: From Newsletter to Podcast, Leveraging AI for Audio Transformation

Light-Mode

Classic

Newspaper

Minty

Dark-Mode

Neon Noir

Minty

HN StartUps