[NKS 2004: Matthew Frank, Two Years of Struggle with Computational Equivalence] - A New Kind of Science: The NKS Forum

A New Kind of Science: The NKS Forum

Pages:1


NKS 2004: Matthew Frank, Two Years of Struggle with Computational Equivalence

(Click here to view the original thread with full colors/images)


Posted by: Catherine Boucher

Matthew Frank
University of Chicago
Two Years of Struggle with Computational Equivalence


Session:
Philosophical Implications of NKS
10:30am, April 23, 2004, Eden Vale C

Abstract:

What must a computation be in order for the principle of computational equivalence to hold? Two years of struggle with and correspondence on this question have left me with no clear answer about computational equivalence, but several insights about the peculiarities of the NKS notions of computation versus notions more familiar in mathematics. I present some of these insights, along with a more successful outcome to a briefer struggle with the principle of computational irreducibility.

http://www.wolframscience.com/confe...s/index_24.html


Posted by: Jason Cawley

Matt Frank offered a formal definition of computational irreducibility. He also offered some thoughts on which of the conclusions of chapter 12 of the NKS book depend only on computational irreducibility, and not on the stronger claim of PCE (the principle of computational equivalence) - and pointed to some that do depend on the latter. I found this separation useful, not just because one might accept the former while doubting the latter, but also because it tends to clarify both concepts.


Posted by: Matthew Frank

Here's my conjecture, inspired by the book:

Def.: Let WorstTime(T,n) be the longest time that Turing machine T takes to halt over all inputs of length n on which it does halt. Then T is *reducible* if there is a Turing machine U with the same inputs and outputs such that

WorstTime(U,n) / WorstTime(T,n) -> 0 as n -> infinity

(In particular, U should halt whenever T halts, and in other cases U should leave the tape in the same state as T does.)

Conjecture: As the number of states grows to infinity, the fraction of reducible Turing machines goes to 0.

The relevant passages in the book are pp. 737-750 (with general ideas) and 758-764 (with empirical studies of WorstTime for small Turing machines).


Posted by: Matthew Frank

This is my talk in notebook format.




Forum Sponsored by Wolfram Research

© 2004-2009 Wolfram Research, Inc. | Powered by vBulletin 2.3.0 © 2000-2002 Jelsoft Enterprises, Ltd. | Disclaimer
vB Easy Archive Final - Created by Xenon and modified/released by SkuZZy from the Job Openings