17
Part II: EGBChapter 17
Church, Turing, Tarski, and Others
The Church-Turing Thesis. Is the universe a computer?
The Church-Turing Thesis states that anything that can be computed can be computed by a Turing Machine. This implies that if the human mind is a physical process, it can be simulated by a computer. We explore the philosophical implications: Is the universe itself just a giant computer processing information? Is consciousness just a specific type of software?
Select Program (Algorithm)
The Tape (Memory)
|
0
0
1
Head
1
2
1
3
4
5
6
7
8
9
10
11
|
12
Internal State
CURRENT STATESTART
LAST ACTIONProgram A loaded. Increments a binary number by 1. (e.g., 011 → 100)
The Rule Book (Program A)IF State + Symbol THEN Write + Move + NewState
START+'|'
→
'|'+▶+START
START+'0'
→
'0'+▶+START
START+'1'
→
'1'+▶+START
START+'_'
→
'_'+◀+INC
INC+'0'
→
'1'+▶+DONE
INC+'1'
→
'0'+◀+INC
INC+'|'
→
'|'+▶+DONE
DONE+'0'
→
'0'+▶+DONE
DONE+'1'
→
'1'+▶+DONE
DONE+'_'
→
'_'+▶+START