Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.theory > #49891 > unrolled thread
| Started by | olcott <polcott2@gmail.com> |
|---|---|
| First post | 2022-05-06 15:53 -0500 |
| Last post | 2022-05-09 10:35 -0500 |
| Articles | 20 on this page of 194 — 10 participants |
Back to article view | Back to comp.theory
Validating that the implementation meets the spec for TM transition function olcott <polcott2@gmail.com> - 2022-05-06 15:53 -0500
Re: Validating that the implementation meets the spec for TM transition function Mr Flibble <flibble@reddwarf.jmc> - 2022-05-06 22:08 +0100
Re: Validating that the implementation meets the spec for TM transition function olcott <polcott2@gmail.com> - 2022-05-06 16:25 -0500
Re: Validating that the implementation meets the spec for TM transition function Mr Flibble <flibble@reddwarf.jmc> - 2022-05-06 22:29 +0100
Re: Validating that the implementation meets the spec for TM transition function olcott <polcott2@gmail.com> - 2022-05-06 17:08 -0500
Re: Validating that the implementation meets the spec for TM transition function Mr Flibble <flibble@reddwarf.jmc> - 2022-05-07 13:02 +0100
Re: Validating that the implementation meets the spec for TM transition function Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2022-05-06 14:41 -0700
Re: Validating that the implementation meets the spec for TM transition function olcott <polcott2@gmail.com> - 2022-05-06 17:02 -0500
Re: Validating that the implementation meets the spec for TM transition function Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2022-05-06 15:36 -0700
Re: Validating that the implementation meets the spec for TM transition function olcott <polcott2@gmail.com> - 2022-05-06 17:54 -0500
Re: Validating that the implementation meets the spec for TM transition function Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2022-05-07 00:39 +0100
Re: Validating that the implementation meets the spec for TM transition function olcott <polcott2@gmail.com> - 2022-05-06 18:54 -0500
Re: Validating that the implementation meets the spec for TM transition function Ben <ben.usenet@bsb.me.uk> - 2022-05-07 01:54 +0100
Re: Validating that the implementation meets the spec for TM transition function olcott <polcott2@gmail.com> - 2022-05-06 20:05 -0500
Re: Validating that the implementation meets the spec for TM transition function Ben <ben.usenet@bsb.me.uk> - 2022-05-07 23:21 +0100
Re: Validating that the implementation meets the spec for TM transition function Jeff Barnett <jbb@notatt.com> - 2022-05-07 19:57 -0600
Re: Validating that the implementation meets the spec for TM transition function Richard Damon <Richard@Damon-Family.org> - 2022-05-08 07:34 -0400
Re: Validating that the implementation meets the spec for TM transition function Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2022-05-08 05:11 -0700
Re: Validating that the implementation meets the spec for TM transition function Richard Damon <Richard@Damon-Family.org> - 2022-05-08 14:20 -0400
Re: Validating that the implementation meets the spec for TM transition function Ben <ben.usenet@bsb.me.uk> - 2022-05-08 19:59 +0100
Re: Validating that the implementation meets the spec for TM transition function Ben <ben.usenet@bsb.me.uk> - 2022-05-09 03:14 +0100
Re: Validating that the implementation meets the spec for TM transition function olcott <NoOne@NoWhere.com> - 2022-05-08 22:39 -0500
Re: Validating that the implementation meets the spec for TM transition function Ben <ben.usenet@bsb.me.uk> - 2022-05-09 12:36 +0100
Re: Validating that the implementation meets the spec for TM transition function Ben <ben.usenet@bsb.me.uk> - 2022-05-08 14:44 +0100
Re: Validating that the implementation meets the spec for TM transition function Jeff Barnett <jbb@notatt.com> - 2022-05-08 11:08 -0600
Re: Validating that the implementation meets the spec for TM transition function Ben <ben.usenet@bsb.me.uk> - 2022-05-08 19:27 +0100
Re: Validating that the implementation meets the spec for TM transition function Richard Damon <Richard@Damon-Family.org> - 2022-05-08 15:22 -0400
Re: Validating that the implementation meets the spec for TM transition function Mr Flibble <flibble@reddwarf.jmc> - 2022-05-08 20:30 +0100
Re: Validating that the implementation meets the spec for TM transition function olcott <NoOne@NoWhere.com> - 2022-05-09 10:53 -0500
Re: Validating that the implementation meets the spec for TM transition function Ben <ben.usenet@bsb.me.uk> - 2022-05-09 23:08 +0100
Re: Validating that the implementation meets the spec for TM transition function olcott <NoOne@NoWhere.com> - 2022-05-09 17:32 -0500
Re: Validating that the implementation meets the spec for TM transition function Richard Damon <Richard@Damon-Family.org> - 2022-05-09 20:31 -0400
Re: Validating that the implementation meets the spec for TM transition function Ben <ben.usenet@bsb.me.uk> - 2022-05-10 01:37 +0100
Re: Validating that the implementation meets the spec for TM transition function olcott <NoOne@NoWhere.com> - 2022-05-09 20:29 -0500
Re: Validating that the implementation meets the spec for TM transition function Ben <ben.usenet@bsb.me.uk> - 2022-05-10 11:35 +0100
Re: Validating that the implementation meets the spec for TM transition function [ best tape] olcott <NoOne@NoWhere.com> - 2022-05-10 19:12 -0500
Re: Validating that the implementation meets the spec for TM transition function Jeff Barnett <jbb@notatt.com> - 2022-05-08 14:51 -0600
Re: Validating that the implementation meets the spec for TM transition function olcott <NoOne@NoWhere.com> - 2022-05-09 10:18 -0500
Re: Validating that the implementation meets the spec for TM transition function Ben <ben.usenet@bsb.me.uk> - 2022-05-09 23:14 +0100
Re: Validating that the implementation meets the spec for TM transition function olcott <NoOne@NoWhere.com> - 2022-05-09 17:42 -0500
Re: Validating that the implementation meets the spec for TM transition function Ben <ben.usenet@bsb.me.uk> - 2022-05-10 01:13 +0100
Re: Validating that the implementation meets the spec for TM transition function olcott <NoOne@NoWhere.com> - 2022-05-09 20:28 -0500
Re: Validating that the implementation meets the spec for TM transition function Richard Damon <Richard@Damon-Family.org> - 2022-05-09 23:34 -0400
Re: Validating that the implementation meets the spec for TM transition function Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2022-05-10 00:24 -0700
Re: Validating that the implementation meets the spec for TM transition function Ben <ben.usenet@bsb.me.uk> - 2022-05-10 11:31 +0100
Re: Validating that the implementation meets the spec for TM transition function Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2022-05-10 03:46 -0700
Re: Validating that the implementation meets the spec for TM transition function Ben <ben.usenet@bsb.me.uk> - 2022-05-10 12:23 +0100
Re: Validating that the implementation meets the spec for TM transition function olcott <NoOne@NoWhere.com> - 2022-05-10 06:53 -0500
Re: Validating that the implementation meets the spec for TM transition function Richard Damon <Richard@Damon-Family.org> - 2022-05-10 08:01 -0400
Re: Validating that the implementation meets the spec for TM transition function Ben <ben.usenet@bsb.me.uk> - 2022-05-10 16:41 +0100
Re: Validating that the implementation meets the spec for TM transition function Jeff Barnett <jbb@notatt.com> - 2022-05-10 11:56 -0600
Re: Validating that the implementation meets the spec for TM transition function olcott <NoOne@NoWhere.com> - 2022-05-10 19:43 -0500
Re: Validating that the implementation meets the spec for TM transition function Jeff Barnett <jbb@notatt.com> - 2022-05-10 20:49 -0600
Re: Validating that the implementation meets the spec for TM transition function Mr Flibble <flibble@reddwarf.jmc> - 2022-05-10 19:01 +0100
Re: Validating that the implementation meets the spec for TM transition function "dklei...@gmail.com" <dkleinecke@gmail.com> - 2022-05-10 11:59 -0700
Re: Validating that the implementation meets the spec for TM transition function olcott <NoOne@NoWhere.com> - 2022-05-10 19:04 -0500
Re: Validating that the implementation meets the spec for TM transition function Ben <ben.usenet@bsb.me.uk> - 2022-05-11 01:42 +0100
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] olcott <NoOne@NoWhere.com> - 2022-05-10 20:12 -0500
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2022-05-11 03:05 +0100
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] olcott <NoOne@NoWhere.com> - 2022-05-10 21:14 -0500
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2022-05-11 02:19 -0700
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] olcott <NoOne@NoWhere.com> - 2022-05-11 08:54 -0500
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2022-05-11 16:27 +0100
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] olcott <NoOne@NoWhere.com> - 2022-05-11 10:36 -0500
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2022-05-11 16:49 +0100
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2022-05-11 14:30 -0700
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] olcott <NoOne@NoWhere.com> - 2022-05-11 16:38 -0500
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2022-05-12 00:01 +0100
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] olcott <NoOne@NoWhere.com> - 2022-05-11 19:05 -0500
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2022-05-12 04:03 +0100
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] olcott <NoOne@NoWhere.com> - 2022-05-11 22:29 -0500
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] olcott <NoOne@NoWhere.com> - 2022-05-11 22:37 -0500
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] Ben <ben.usenet@bsb.me.uk> - 2022-05-12 15:02 +0100
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2022-05-12 19:03 +0100
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] Ben <ben.usenet@bsb.me.uk> - 2022-05-12 19:30 +0100
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] olcott <NoOne@NoWhere.com> - 2022-05-12 14:23 -0500
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] Richard Damon <Richard@Damon-Family.org> - 2022-05-12 19:19 -0400
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2022-05-13 01:02 +0100
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] Jeff Barnett <jbb@notatt.com> - 2022-05-11 23:13 -0600
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] olcott <NoOne@NoWhere.com> - 2022-05-12 00:43 -0500
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] Ben <ben.usenet@bsb.me.uk> - 2022-05-11 04:02 +0100
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] olcott <NoOne@NoWhere.com> - 2022-05-10 22:07 -0500
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] Ben <ben.usenet@bsb.me.uk> - 2022-05-11 13:40 +0100
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] olcott <NoOne@NoWhere.com> - 2022-05-11 09:02 -0500
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2022-05-11 16:09 +0100
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] olcott <NoOne@NoWhere.com> - 2022-05-11 10:29 -0500
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] Ben <ben.usenet@bsb.me.uk> - 2022-05-11 20:35 +0100
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] olcott <NoOne@NoWhere.com> - 2022-05-11 15:12 -0500
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] Ben <ben.usenet@bsb.me.uk> - 2022-05-11 22:54 +0100
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] olcott <NoOne@NoWhere.com> - 2022-05-11 17:02 -0500
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] Ben <ben.usenet@bsb.me.uk> - 2022-05-12 02:00 +0100
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] olcott <NoOne@NoWhere.com> - 2022-05-11 20:37 -0500
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] Ben <ben.usenet@bsb.me.uk> - 2022-05-12 02:49 +0100
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] olcott <NoOne@NoWhere.com> - 2022-05-11 21:49 -0500
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] Ben <ben.usenet@bsb.me.uk> - 2022-05-12 14:45 +0100
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] olcott <NoOne@NoWhere.com> - 2022-05-12 10:31 -0500
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] Ben <ben.usenet@bsb.me.uk> - 2022-05-12 21:20 +0100
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] olcott <NoOne@NoWhere.com> - 2022-05-12 15:33 -0500
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] Mr Flibble <flibble@reddwarf.jmc> - 2022-05-12 21:36 +0100
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] olcott <NoOne@NoWhere.com> - 2022-05-12 16:28 -0500
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] Mr Flibble <flibble@reddwarf.jmc> - 2022-05-12 22:33 +0100
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] Ben <ben.usenet@bsb.me.uk> - 2022-05-12 22:02 +0100
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] olcott <NoOne@NoWhere.com> - 2022-05-12 16:14 -0500
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] Ben <ben.usenet@bsb.me.uk> - 2022-05-13 00:18 +0100
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] olcott <NoOne@NoWhere.com> - 2022-05-12 18:22 -0500
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] Ben <ben.usenet@bsb.me.uk> - 2022-05-13 01:10 +0100
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] olcott <NoOne@NoWhere.com> - 2022-05-12 19:58 -0500
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] Ben <ben.usenet@bsb.me.uk> - 2022-05-13 02:54 +0100
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] Richard Damon <Richard@Damon-Family.org> - 2022-05-12 22:09 -0400
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] olcott <NoOne@NoWhere.com> - 2022-05-12 21:41 -0500
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] Mikko <mikko.levanto@iki.fi> - 2022-05-13 10:01 +0300
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] olcott <NoOne@NoWhere.com> - 2022-05-13 10:57 -0500
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] Mikko <mikko.levanto@iki.fi> - 2022-05-13 19:06 +0300
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] Ben <ben.usenet@bsb.me.uk> - 2022-05-13 11:54 +0100
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] Mr Flibble <flibble@reddwarf.jmc> - 2022-05-13 13:38 +0100
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] olcott <NoOne@NoWhere.com> - 2022-05-13 11:07 -0500
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] Mr Flibble <flibble@reddwarf.jmc> - 2022-05-13 17:14 +0100
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] olcott <NoOne@NoWhere.com> - 2022-05-13 12:03 -0500
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] Mr Flibble <flibble@reddwarf.jmc> - 2022-05-13 18:09 +0100
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] olcott <NoOne@NoWhere.com> - 2022-05-13 12:15 -0500
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] Ben <ben.usenet@bsb.me.uk> - 2022-05-13 17:26 +0100
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] olcott <NoOne@NoWhere.com> - 2022-05-13 12:07 -0500
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] Ben <ben.usenet@bsb.me.uk> - 2022-05-13 19:45 +0100
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] olcott <NoOne@NoWhere.com> - 2022-05-13 13:57 -0500
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] Richard Damon <Richard@Damon-Family.org> - 2022-05-13 15:04 -0400
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] olcott <NoOne@NoWhere.com> - 2022-05-13 14:15 -0500
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] Richard Damon <Richard@Damon-Family.org> - 2022-05-13 15:40 -0400
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] olcott <NoOne@NoWhere.com> - 2022-05-13 14:58 -0500
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] Richard Damon <Richard@Damon-Family.org> - 2022-05-13 16:24 -0400
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] olcott <NoOne@NoWhere.com> - 2022-05-13 15:33 -0500
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] Richard Damon <Richard@Damon-Family.org> - 2022-05-13 17:25 -0400
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] olcott <NoOne@NoWhere.com> - 2022-05-13 16:48 -0500
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] Richard Damon <Richard@Damon-Family.org> - 2022-05-13 18:05 -0400
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] Ben <ben.usenet@bsb.me.uk> - 2022-05-13 20:12 +0100
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] olcott <NoOne@NoWhere.com> - 2022-05-13 14:28 -0500
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] Ben <ben.usenet@bsb.me.uk> - 2022-05-13 21:58 +0100
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] olcott <NoOne@NoWhere.com> - 2022-05-13 16:12 -0500
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] Ben <ben.usenet@bsb.me.uk> - 2022-05-13 23:57 +0100
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] olcott <NoOne@NoWhere.com> - 2022-05-13 17:59 -0500
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] Ben <ben.usenet@bsb.me.uk> - 2022-05-14 01:00 +0100
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] olcott <NoOne@NoWhere.com> - 2022-05-13 19:09 -0500
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] Ben <ben.usenet@bsb.me.uk> - 2022-05-14 01:21 +0100
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] olcott <NoOne@NoWhere.com> - 2022-05-17 13:17 -0500
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2022-05-14 01:54 -0700
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] olcott <NoOne@NoWhere.com> - 2022-05-14 04:13 -0500
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2022-05-14 03:30 -0700
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] olcott <NoOne@NoWhere.com> - 2022-05-14 08:51 -0500
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2022-05-14 11:38 -0700
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] olcott <NoOne@NoWhere.com> - 2022-05-14 13:54 -0500
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] Ben <ben.usenet@bsb.me.uk> - 2022-05-14 13:15 +0100
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2022-05-14 11:37 -0700
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2022-05-14 19:47 +0100
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] Ben <ben.usenet@bsb.me.uk> - 2022-05-14 20:15 +0100
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2022-05-14 12:52 -0700
Re: Validating that the implementation meets the spec for TM transition function [ unlimited scalability ] olcott <NoOne@NoWhere.com> - 2022-05-13 16:43 -0500
Re: Validating that the implementation meets the spec for TM transition function [ unlimited scalability ] Ben <ben.usenet@bsb.me.uk> - 2022-05-13 23:58 +0100
Re: Validating that the implementation meets the spec for TM transition function [ unlimited scalability ] olcott <NoOne@NoWhere.com> - 2022-05-13 18:03 -0500
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] Jeff Barnett <jbb@notatt.com> - 2022-05-13 15:06 -0600
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] olcott <NoOne@NoWhere.com> - 2022-05-13 16:16 -0500
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] Jeff Barnett <jbb@notatt.com> - 2022-05-13 17:48 -0600
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] olcott <NoOne@NoWhere.com> - 2022-05-13 19:06 -0500
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] Jeff Barnett <jbb@notatt.com> - 2022-05-13 19:58 -0600
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] olcott <NoOne@NoWhere.com> - 2022-05-13 22:39 -0500
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] Jeff Barnett <jbb@notatt.com> - 2022-05-13 19:48 -0600
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] olcott <NoOne@NoWhere.com> - 2022-05-13 11:00 -0500
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] Richard Damon <Richard@Damon-Family.org> - 2022-05-13 12:08 -0400
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] Ben <ben.usenet@bsb.me.uk> - 2022-05-13 17:27 +0100
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] olcott <NoOne@NoWhere.com> - 2022-05-13 12:10 -0500
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] Richard Damon <Richard@Damon-Family.org> - 2022-05-13 13:20 -0400
Re: Validating that the implementation meets the spec for TM transition function [ best tape ] Richard Damon <Richard@Damon-Family.org> - 2022-05-11 22:07 -0400
Re: Validating that the implementation meets the spec for TM transition function olcott <NoOne@NoWhere.com> - 2022-05-10 21:06 -0500
Re: Validating that the implementation meets the spec for TM transition function Ben <ben.usenet@bsb.me.uk> - 2022-05-11 00:11 +0100
Re: Validating that the implementation meets the spec for TM transition function olcott <NoOne@NoWhere.com> - 2022-05-10 19:41 -0500
Re: Validating that the implementation meets the spec for TM transition function olcott <NoOne@NoWhere.com> - 2022-05-10 06:53 -0500
Re: Validating that the implementation meets the spec for TM transition function olcott <NoOne@NoWhere.com> - 2022-05-07 21:04 -0500
Re: Validating that the implementation meets the spec for TM transition function Richard Damon <Richard@Damon-Family.org> - 2022-05-08 07:30 -0400
Re: Validating that the implementation meets the spec for TM transition function Ben <ben.usenet@bsb.me.uk> - 2022-05-08 14:46 +0100
Re: Validating that the implementation meets the spec for TM transition function olcott <NoOne@NoWhere.com> - 2022-05-09 10:19 -0500
Re: Validating that the implementation meets the spec for TM transition function Ben <ben.usenet@bsb.me.uk> - 2022-05-07 01:22 +0100
Re: Validating that the implementation meets the spec for TM transition function olcott <polcott2@gmail.com> - 2022-05-06 19:38 -0500
Re: Validating that the implementation meets the spec for TM transition function Ben <ben.usenet@bsb.me.uk> - 2022-05-07 02:01 +0100
Re: Validating that the implementation meets the spec for TM transition function olcott <polcott2@gmail.com> - 2022-05-06 20:22 -0500
Re: Validating that the implementation meets the spec for TM transition function Ben <ben.usenet@bsb.me.uk> - 2022-05-07 23:30 +0100
Re: Validating that the implementation meets the spec for TM transition function Ben <ben.usenet@bsb.me.uk> - 2022-05-07 02:04 +0100
Re: Validating that the implementation meets the spec for TM transition function olcott <polcott2@gmail.com> - 2022-05-06 20:26 -0500
Re: Validating that the implementation meets the spec for TM transition function Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2022-05-07 05:00 -0700
Re: Validating that the implementation meets the spec for TM transition function Ben <ben.usenet@bsb.me.uk> - 2022-05-07 23:31 +0100
Re: Validating that the implementation meets the spec for TM transition function olcott <NoOne@NoWhere.com> - 2022-05-07 18:36 -0500
Re: Validating that the implementation meets the spec for TM transition function Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2022-05-08 02:39 -0700
Re: Validating that the implementation meets the spec for TM transition function [ priorities ] olcott <NoOne@NoWhere.com> - 2022-05-08 17:21 -0500
Re: Validating that the implementation meets the spec for TM transition function Mikko <mikko.levanto@iki.fi> - 2022-05-07 11:06 +0300
Re: Validating that the implementation meets the spec for TM transition function olcott <polcott2@gmail.com> - 2022-05-07 11:14 -0500
Re: Validating that the implementation meets the spec for TM transition function Mikko <mikko.levanto@iki.fi> - 2022-05-08 11:57 +0300
Re: Validating that the implementation meets the spec for TM transition function olcott <NoOne@NoWhere.com> - 2022-05-09 10:35 -0500
Page 4 of 10 — ← Prev page 1 2 3 [4] 5 6 … 10 Next page →
| From | Malcolm McLean <malcolm.arthur.mclean@gmail.com> |
|---|---|
| Date | 2022-05-11 02:19 -0700 |
| Subject | Re: Validating that the implementation meets the spec for TM transition function [ best tape ] |
| Message-ID | <d4a4f528-98d7-4203-97cc-c7c110b87dbbn@googlegroups.com> |
| In reply to | #50216 |
On Wednesday, 11 May 2022 at 03:05:37 UTC+1, Mike Terry wrote: > > But what you suggest is quite workable... > > I think if I were interested in ultimate efficiency, I might go with Jeff's "chained blocks" with a > comfortably large chosen page size. (But efficiency really isn't an issue for this task!) > The tape is unbounded. And even some very simple machines will fill it up to infinity. If you stop the machine when the process runs out of memory, which is a reasonable strategy, you don't want O(N) tape write operations. Chained blocks are probably the best model. They don't scale up, so a machine that was written for a 16K ZX81 might struggle when ported to a 16GB typical modern desktop. If you know the approximate szie of your tape, however, then blocks are a good solution.
[toc] | [prev] | [next] | [standalone]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2022-05-11 08:54 -0500 |
| Subject | Re: Validating that the implementation meets the spec for TM transition function [ best tape ] |
| Message-ID | <QJudnRpb3qKIXeb_nZ2dnUU7_83NnZ2d@giganews.com> |
| In reply to | #50223 |
On 5/11/2022 4:19 AM, Malcolm McLean wrote: > On Wednesday, 11 May 2022 at 03:05:37 UTC+1, Mike Terry wrote: >> >> But what you suggest is quite workable... >> >> I think if I were interested in ultimate efficiency, I might go with Jeff's "chained blocks" with a >> comfortably large chosen page size. (But efficiency really isn't an issue for this task!) >> > The tape is unbounded. And even some very simple machines will fill it up to infinity. > If you stop the machine when the process runs out of memory, which is a reasonable > strategy, you don't want O(N) tape write operations. > > Chained blocks are probably the best model. They don't scale up, so a machine that was written > for a 16K ZX81 might struggle when ported to a 16GB typical modern desktop. If you know > the approximate szie of your tape, however, then blocks are a good solution. I prefer the exponential memory allocation of std:vector. It seems to be the optimal balance between speed and memory use. My implementation of David Kleinecke's double stack based std::deque will allow std::deque::push_front() to work exactly the same way as std:vector::push_back(). It doesn't invalidate iterators or integer subscripts or have any of the extra (memory or time) overhead of std:deque. It seems to me to simply be a much better way to implement the same functionality as std::deque. -- Copyright 2022 Pete Olcott "Talent hits a target no one else can hit; Genius hits a target no one else can see." Arthur Schopenhauer
[toc] | [prev] | [next] | [standalone]
| From | Mike Terry <news.dead.person.stones@darjeeling.plus.com> |
|---|---|
| Date | 2022-05-11 16:27 +0100 |
| Subject | Re: Validating that the implementation meets the spec for TM transition function [ best tape ] |
| Message-ID | <t5gkl6$8og$1@gioia.aioe.org> |
| In reply to | #50223 |
On 11/05/2022 10:19, Malcolm McLean wrote: > On Wednesday, 11 May 2022 at 03:05:37 UTC+1, Mike Terry wrote: >> >> But what you suggest is quite workable... >> >> I think if I were interested in ultimate efficiency, I might go with Jeff's "chained blocks" with a >> comfortably large chosen page size. (But efficiency really isn't an issue for this task!) >> > The tape is unbounded. And even some very simple machines will fill it up to infinity. > If you stop the machine when the process runs out of memory, which is a reasonable > strategy, you don't want O(N) tape write operations. > > Chained blocks are probably the best model. They don't scale up, so a machine that was written > for a 16K ZX81 might struggle when ported to a 16GB typical modern desktop. If you know > the approximate szie of your tape, however, then blocks are a good solution. > I don't get why you say a chained block approach doesn't scale up. Such a design works well until the logical (user) address space is filled, which is absolutely huge on a modern 64-bit machine with page files etc.. When the tape gets very large, only a small portion of it needs to be in the working set for the process to avoid paging. The only design I can think of that might scale up better would be one using an output device larger than the logical address space limit. Maybe you were just saying that a hard-coded small block size (for a ZX81?) is not as efficient as big blocks if you've got lots of memory? I don't see that you would use a chained block approach on such a tiny machine! Perhaps you meant to say the design doesn't scale /down/ rather than up? (And the size of chained blocks can be dynamically decided at run time if we like.) Other designs, e.g. using vector or strings will involve copying ever larger blocks of memory around when the vector/string is extended, so perhaps you meant to say that /those/ designs don't scale up, but the chained blocks scale up? Mike.
[toc] | [prev] | [next] | [standalone]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2022-05-11 10:36 -0500 |
| Subject | Re: Validating that the implementation meets the spec for TM transition function [ best tape ] |
| Message-ID | <2oSdnbrtJu94Sub_nZ2dnUU7_83NnZ2d@giganews.com> |
| In reply to | #50233 |
On 5/11/2022 10:27 AM, Mike Terry wrote: > On 11/05/2022 10:19, Malcolm McLean wrote: >> On Wednesday, 11 May 2022 at 03:05:37 UTC+1, Mike Terry wrote: >>> >>> But what you suggest is quite workable... >>> >>> I think if I were interested in ultimate efficiency, I might go with >>> Jeff's "chained blocks" with a >>> comfortably large chosen page size. (But efficiency really isn't an >>> issue for this task!) >>> >> The tape is unbounded. And even some very simple machines will fill it >> up to infinity. >> If you stop the machine when the process runs out of memory, which is >> a reasonable >> strategy, you don't want O(N) tape write operations. >> >> Chained blocks are probably the best model. They don't scale up, so a >> machine that was written >> for a 16K ZX81 might struggle when ported to a 16GB typical modern >> desktop. If you know >> the approximate szie of your tape, however, then blocks are a good >> solution. >> > > I don't get why you say a chained block approach doesn't scale up. Such > a design works well until the logical (user) address space is filled, > which is absolutely huge on a modern 64-bit machine with page files > etc.. When the tape gets very large, only a small portion of it needs > to be in the working set for the process to avoid paging. > The exponential growth rate factor of std::vector seems to be a more efficient tradeoff of space versus time and does not have the extra (space/time) overhead of multiple levels of reference. > The only design I can think of that might scale up better would be one > using an output device larger than the logical address space limit. > Maybe you were just saying that a hard-coded small block size (for a The fastest output devices are still enormously slower than RAM. > ZX81?) is not as efficient as big blocks if you've got lots of memory? > I don't see that you would use a chained block approach on such a tiny > machine! Perhaps you meant to say the design doesn't scale /down/ > rather than up? (And the size of chained blocks can be dynamically > decided at run time if we like.) > > Other designs, e.g. using vector or strings will involve copying ever > larger blocks of memory around when the vector/string is extended, so > perhaps you meant to say that /those/ designs don't scale up, but the > chained blocks scale up? > > > Mike. Empirical testing seems to prove that std::vector is faster than other methods because it greatly reduces the number of allocations required. -- Copyright 2022 Pete Olcott "Talent hits a target no one else can hit; Genius hits a target no one else can see." Arthur Schopenhauer
[toc] | [prev] | [next] | [standalone]
| From | Mike Terry <news.dead.person.stones@darjeeling.plus.com> |
|---|---|
| Date | 2022-05-11 16:49 +0100 |
| Subject | Re: Validating that the implementation meets the spec for TM transition function [ best tape ] |
| Message-ID | <rsidnRMUF-lhR-b_nZ2dnUU7-TnNnZ2d@brightview.co.uk> |
| In reply to | #50235 |
On 11/05/2022 16:36, olcott wrote: > On 5/11/2022 10:27 AM, Mike Terry wrote: >> On 11/05/2022 10:19, Malcolm McLean wrote: >>> On Wednesday, 11 May 2022 at 03:05:37 UTC+1, Mike Terry wrote: >>>> >>>> But what you suggest is quite workable... >>>> >>>> I think if I were interested in ultimate efficiency, I might go with Jeff's "chained blocks" with a >>>> comfortably large chosen page size. (But efficiency really isn't an issue for this task!) >>>> >>> The tape is unbounded. And even some very simple machines will fill it up to infinity. >>> If you stop the machine when the process runs out of memory, which is a reasonable >>> strategy, you don't want O(N) tape write operations. >>> >>> Chained blocks are probably the best model. They don't scale up, so a machine that was written >>> for a 16K ZX81 might struggle when ported to a 16GB typical modern desktop. If you know >>> the approximate szie of your tape, however, then blocks are a good solution. >>> >> >> I don't get why you say a chained block approach doesn't scale up. Such a design works well until >> the logical (user) address space is filled, which is absolutely huge on a modern 64-bit machine >> with page files etc.. When the tape gets very large, only a small portion of it needs to be in >> the working set for the process to avoid paging. >> > > The exponential growth rate factor of std::vector seems to be a more efficient tradeoff of space > versus time and does not have the extra (space/time) overhead of multiple levels of reference. > >> The only design I can think of that might scale up better would be one using an output device >> larger than the logical address space limit. Maybe you were just saying that a hard-coded small >> block size (for a > > The fastest output devices are still enormously slower than RAM. > >> ZX81?) is not as efficient as big blocks if you've got lots of memory? I don't see that you would >> use a chained block approach on such a tiny machine! Perhaps you meant to say the design doesn't >> scale /down/ rather than up? (And the size of chained blocks can be dynamically decided at run >> time if we like.) >> >> Other designs, e.g. using vector or strings will involve copying ever larger blocks of memory >> around when the vector/string is extended, so perhaps you meant to say that /those/ designs don't >> scale up, but the chained blocks scale up? >> >> >> Mike. > > Empirical testing seems to prove that std::vector is faster than other methods because it greatly > reduces the number of allocations required. So you don't understand DK/Ben's two stack approach, and you don't understand the chained blocks approach. I could ask "what empirical testing?" but that would just be a waste of time, so I won't... Anyway, none of that matters - just concentrate on finishing your coding! (I did say that your two vector approach was ok, so I was never suggesting you're incapable of finishing it, or that it can't work or anything...) Mike.
[toc] | [prev] | [next] | [standalone]
| From | Malcolm McLean <malcolm.arthur.mclean@gmail.com> |
|---|---|
| Date | 2022-05-11 14:30 -0700 |
| Subject | Re: Validating that the implementation meets the spec for TM transition function [ best tape ] |
| Message-ID | <0b2409e1-6bc0-426d-9a9b-9f8ce84f1c0fn@googlegroups.com> |
| In reply to | #50233 |
On Wednesday, 11 May 2022 at 16:27:37 UTC+1, Mike Terry wrote: > On 11/05/2022 10:19, Malcolm McLean wrote: > > On Wednesday, 11 May 2022 at 03:05:37 UTC+1, Mike Terry wrote: > >> > >> But what you suggest is quite workable... > >> > >> I think if I were interested in ultimate efficiency, I might go with Jeff's "chained blocks" with a > >> comfortably large chosen page size. (But efficiency really isn't an issue for this task!) > >> > > The tape is unbounded. And even some very simple machines will fill it up to infinity. > > If you stop the machine when the process runs out of memory, which is a reasonable > > strategy, you don't want O(N) tape write operations. > > > > Chained blocks are probably the best model. They don't scale up, so a machine that was written > > for a 16K ZX81 might struggle when ported to a 16GB typical modern desktop. If you know > > the approximate szie of your tape, however, then blocks are a good solution. > > > I don't get why you say a chained block approach doesn't scale up. Such a design works well until > the logical (user) address space is filled, which is absolutely huge on a modern 64-bit machine with > page files etc.. When the tape gets very large, only a small portion of it needs to be in the > working set for the process to avoid paging. > > The only design I can think of that might scale up better would be one using an output device larger > than the logical address space limit. Maybe you were just saying that a hard-coded small block size > (for a ZX81?) is not as efficient as big blocks if you've got lots of memory? I don't see that you > would use a chained block approach on such a tiny machine! Perhaps you meant to say the design > doesn't scale /down/ rather than up? (And the size of chained blocks can be dynamically decided at > run time if we like.) > > Other designs, e.g. using vector or strings will involve copying ever larger blocks of memory around > when the vector/string is extended, so perhaps you meant to say that /those/ designs don't scale up, > but the chained blocks scale up? > I was thinking that the chained block degenerates into effectively a linked list when block size becomes small in relation to tape length. However that isn't really a problem - it still works more effectively than a contiguous model.
[toc] | [prev] | [next] | [standalone]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2022-05-11 16:38 -0500 |
| Subject | Re: Validating that the implementation meets the spec for TM transition function [ best tape ] |
| Message-ID | <bfWdnfWTUopbseH_nZ2dnUU7_81g4p2d@giganews.com> |
| In reply to | #50247 |
On 5/11/2022 4:30 PM, Malcolm McLean wrote: > On Wednesday, 11 May 2022 at 16:27:37 UTC+1, Mike Terry wrote: >> On 11/05/2022 10:19, Malcolm McLean wrote: >>> On Wednesday, 11 May 2022 at 03:05:37 UTC+1, Mike Terry wrote: >>>> >>>> But what you suggest is quite workable... >>>> >>>> I think if I were interested in ultimate efficiency, I might go with Jeff's "chained blocks" with a >>>> comfortably large chosen page size. (But efficiency really isn't an issue for this task!) >>>> >>> The tape is unbounded. And even some very simple machines will fill it up to infinity. >>> If you stop the machine when the process runs out of memory, which is a reasonable >>> strategy, you don't want O(N) tape write operations. >>> >>> Chained blocks are probably the best model. They don't scale up, so a machine that was written >>> for a 16K ZX81 might struggle when ported to a 16GB typical modern desktop. If you know >>> the approximate szie of your tape, however, then blocks are a good solution. >>> >> I don't get why you say a chained block approach doesn't scale up. Such a design works well until >> the logical (user) address space is filled, which is absolutely huge on a modern 64-bit machine with >> page files etc.. When the tape gets very large, only a small portion of it needs to be in the >> working set for the process to avoid paging. >> >> The only design I can think of that might scale up better would be one using an output device larger >> than the logical address space limit. Maybe you were just saying that a hard-coded small block size >> (for a ZX81?) is not as efficient as big blocks if you've got lots of memory? I don't see that you >> would use a chained block approach on such a tiny machine! Perhaps you meant to say the design >> doesn't scale /down/ rather than up? (And the size of chained blocks can be dynamically decided at >> run time if we like.) >> >> Other designs, e.g. using vector or strings will involve copying ever larger blocks of memory around >> when the vector/string is extended, so perhaps you meant to say that /those/ designs don't scale up, >> but the chained blocks scale up? >> > I was thinking that the chained block degenerates into effectively a linked list when block size becomes > small in relation to tape length. However that isn't really a problem - it still works more effectively > than a contiguous model. The actual run-time cost issue is not copying data, this is fairly cheap. A linear growth factor has far many more very expensive operating system memory allocation calls than an exponential growth factor. -- Copyright 2022 Pete Olcott "Talent hits a target no one else can hit; Genius hits a target no one else can see." Arthur Schopenhauer
[toc] | [prev] | [next] | [standalone]
| From | Mike Terry <news.dead.person.stones@darjeeling.plus.com> |
|---|---|
| Date | 2022-05-12 00:01 +0100 |
| Subject | Re: Validating that the implementation meets the spec for TM transition function [ best tape ] |
| Message-ID | <t5hf7p$1kd4$1@gioia.aioe.org> |
| In reply to | #50247 |
On 11/05/2022 22:30, Malcolm McLean wrote: > On Wednesday, 11 May 2022 at 16:27:37 UTC+1, Mike Terry wrote: >> On 11/05/2022 10:19, Malcolm McLean wrote: >>> On Wednesday, 11 May 2022 at 03:05:37 UTC+1, Mike Terry wrote: >>>> >>>> But what you suggest is quite workable... >>>> >>>> I think if I were interested in ultimate efficiency, I might go with Jeff's "chained blocks" with a >>>> comfortably large chosen page size. (But efficiency really isn't an issue for this task!) >>>> >>> The tape is unbounded. And even some very simple machines will fill it up to infinity. >>> If you stop the machine when the process runs out of memory, which is a reasonable >>> strategy, you don't want O(N) tape write operations. >>> >>> Chained blocks are probably the best model. They don't scale up, so a machine that was written >>> for a 16K ZX81 might struggle when ported to a 16GB typical modern desktop. If you know >>> the approximate szie of your tape, however, then blocks are a good solution. >>> >> I don't get why you say a chained block approach doesn't scale up. Such a design works well until >> the logical (user) address space is filled, which is absolutely huge on a modern 64-bit machine with >> page files etc.. When the tape gets very large, only a small portion of it needs to be in the >> working set for the process to avoid paging. >> >> The only design I can think of that might scale up better would be one using an output device larger >> than the logical address space limit. Maybe you were just saying that a hard-coded small block size >> (for a ZX81?) is not as efficient as big blocks if you've got lots of memory? I don't see that you >> would use a chained block approach on such a tiny machine! Perhaps you meant to say the design >> doesn't scale /down/ rather than up? (And the size of chained blocks can be dynamically decided at >> run time if we like.) >> >> Other designs, e.g. using vector or strings will involve copying ever larger blocks of memory around >> when the vector/string is extended, so perhaps you meant to say that /those/ designs don't scale up, >> but the chained blocks scale up? >> > I was thinking that the chained block degenerates into effectively a linked list when block size becomes > small in relation to tape length. However that isn't really a problem - it still works more effectively > than a contiguous model. Yes, for a fixed block length it will be like a tape element linked list, but only some small fraction of the allocation overhead. Bigger blocks resulting in a smaller fraction. Or we could have some kind of exponential block size growth, so we start with, say, 1 allocation cost for the first 50000 tape elements, then getting smaller as blocks get bigger - but 1 allocation per 50000 tape elements is already a pretty small overhead for most purposes. E.g. writing/testing PO's Even TM, we could make do with one single fixed block of just 20 tape elements!!! I'd think the key thing for PO should be to get on with the exercise, rather than playing with TM emulator efficiency. Mike.
[toc] | [prev] | [next] | [standalone]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2022-05-11 19:05 -0500 |
| Subject | Re: Validating that the implementation meets the spec for TM transition function [ best tape ] |
| Message-ID | <aYadnaAI4O_Z0uH_nZ2dnUU7_83NnZ2d@giganews.com> |
| In reply to | #50252 |
On 5/11/2022 6:01 PM, Mike Terry wrote: > On 11/05/2022 22:30, Malcolm McLean wrote: >> On Wednesday, 11 May 2022 at 16:27:37 UTC+1, Mike Terry wrote: >>> On 11/05/2022 10:19, Malcolm McLean wrote: >>>> On Wednesday, 11 May 2022 at 03:05:37 UTC+1, Mike Terry wrote: >>>>> >>>>> But what you suggest is quite workable... >>>>> >>>>> I think if I were interested in ultimate efficiency, I might go >>>>> with Jeff's "chained blocks" with a >>>>> comfortably large chosen page size. (But efficiency really isn't an >>>>> issue for this task!) >>>>> >>>> The tape is unbounded. And even some very simple machines will fill >>>> it up to infinity. >>>> If you stop the machine when the process runs out of memory, which >>>> is a reasonable >>>> strategy, you don't want O(N) tape write operations. >>>> >>>> Chained blocks are probably the best model. They don't scale up, so >>>> a machine that was written >>>> for a 16K ZX81 might struggle when ported to a 16GB typical modern >>>> desktop. If you know >>>> the approximate szie of your tape, however, then blocks are a good >>>> solution. >>>> >>> I don't get why you say a chained block approach doesn't scale up. >>> Such a design works well until >>> the logical (user) address space is filled, which is absolutely huge >>> on a modern 64-bit machine with >>> page files etc.. When the tape gets very large, only a small portion >>> of it needs to be in the >>> working set for the process to avoid paging. >>> >>> The only design I can think of that might scale up better would be >>> one using an output device larger >>> than the logical address space limit. Maybe you were just saying that >>> a hard-coded small block size >>> (for a ZX81?) is not as efficient as big blocks if you've got lots of >>> memory? I don't see that you >>> would use a chained block approach on such a tiny machine! Perhaps >>> you meant to say the design >>> doesn't scale /down/ rather than up? (And the size of chained blocks >>> can be dynamically decided at >>> run time if we like.) >>> >>> Other designs, e.g. using vector or strings will involve copying ever >>> larger blocks of memory around >>> when the vector/string is extended, so perhaps you meant to say that >>> /those/ designs don't scale up, >>> but the chained blocks scale up? >>> >> I was thinking that the chained block degenerates into effectively a >> linked list when block size becomes >> small in relation to tape length. However that isn't really a problem >> - it still works more effectively >> than a contiguous model. > > Yes, for a fixed block length it will be like a tape element linked > list, but only some small fraction of the allocation overhead. Bigger > blocks resulting in a smaller fraction. Or we could have some kind of > exponential block size growth, so we start with, say, 1 allocation cost > for the first 50000 tape elements, then getting smaller as blocks get > bigger - but 1 allocation per 50000 tape elements is already a pretty > small overhead for most purposes. E.g. writing/testing PO's Even TM, we > could make do with one single fixed block of just 20 tape elements!!! > I'd think the key thing for PO should be to get on with the exercise, > rather than playing with TM emulator efficiency. > > Mike. It is more cost-effective to make it right the first time rather than have to go back and fix it. My adaptation of David's approach to the TM tape also seems to be an objectively better way to implement std::deque. I can't possibly do the exercise until I see 100% exactly how the transition function works. Although it is exactly the same idea as a DFA state transition, its seems to not be working that way. -- Copyright 2022 Pete Olcott "Talent hits a target no one else can hit; Genius hits a target no one else can see." Arthur Schopenhauer
[toc] | [prev] | [next] | [standalone]
| From | Mike Terry <news.dead.person.stones@darjeeling.plus.com> |
|---|---|
| Date | 2022-05-12 04:03 +0100 |
| Subject | Re: Validating that the implementation meets the spec for TM transition function [ best tape ] |
| Message-ID | <t5htes$1hb4$1@gioia.aioe.org> |
| In reply to | #50255 |
On 12/05/2022 01:05, olcott wrote: > On 5/11/2022 6:01 PM, Mike Terry wrote: >> On 11/05/2022 22:30, Malcolm McLean wrote: >>> On Wednesday, 11 May 2022 at 16:27:37 UTC+1, Mike Terry wrote: >>>> On 11/05/2022 10:19, Malcolm McLean wrote: >>>>> On Wednesday, 11 May 2022 at 03:05:37 UTC+1, Mike Terry wrote: >>>>>> >>>>>> But what you suggest is quite workable... >>>>>> >>>>>> I think if I were interested in ultimate efficiency, I might go with Jeff's "chained blocks" >>>>>> with a >>>>>> comfortably large chosen page size. (But efficiency really isn't an issue for this task!) >>>>>> >>>>> The tape is unbounded. And even some very simple machines will fill it up to infinity. >>>>> If you stop the machine when the process runs out of memory, which is a reasonable >>>>> strategy, you don't want O(N) tape write operations. >>>>> >>>>> Chained blocks are probably the best model. They don't scale up, so a machine that was written >>>>> for a 16K ZX81 might struggle when ported to a 16GB typical modern desktop. If you know >>>>> the approximate szie of your tape, however, then blocks are a good solution. >>>>> >>>> I don't get why you say a chained block approach doesn't scale up. Such a design works well until >>>> the logical (user) address space is filled, which is absolutely huge on a modern 64-bit machine >>>> with >>>> page files etc.. When the tape gets very large, only a small portion of it needs to be in the >>>> working set for the process to avoid paging. >>>> >>>> The only design I can think of that might scale up better would be one using an output device >>>> larger >>>> than the logical address space limit. Maybe you were just saying that a hard-coded small block size >>>> (for a ZX81?) is not as efficient as big blocks if you've got lots of memory? I don't see that you >>>> would use a chained block approach on such a tiny machine! Perhaps you meant to say the design >>>> doesn't scale /down/ rather than up? (And the size of chained blocks can be dynamically decided at >>>> run time if we like.) >>>> >>>> Other designs, e.g. using vector or strings will involve copying ever larger blocks of memory >>>> around >>>> when the vector/string is extended, so perhaps you meant to say that /those/ designs don't scale >>>> up, >>>> but the chained blocks scale up? >>>> >>> I was thinking that the chained block degenerates into effectively a linked list when block size >>> becomes >>> small in relation to tape length. However that isn't really a problem - it still works more >>> effectively >>> than a contiguous model. >> >> Yes, for a fixed block length it will be like a tape element linked list, but only some small >> fraction of the allocation overhead. Bigger blocks resulting in a smaller fraction. Or we could >> have some kind of exponential block size growth, so we start with, say, 1 allocation cost for the >> first 50000 tape elements, then getting smaller as blocks get bigger - but 1 allocation per 50000 >> tape elements is already a pretty small overhead for most purposes. E.g. writing/testing PO's >> Even TM, we could make do with one single fixed block of just 20 tape elements!!! I'd think the >> key thing for PO should be to get on with the exercise, rather than playing with TM emulator >> efficiency. >> >> Mike. > > It is more cost-effective to make it right the first time rather than have to go back and fix it. > > My adaptation of David's approach to the TM tape also seems to be an objectively better way to > implement std::deque. > > I can't possibly do the exercise until I see 100% exactly how the transition function works. > Although it is exactly the same idea as a DFA state transition, its seems to not be working that way. Yes the idea is the same but slightly more complicated. What seems not to be working that way? You could think of a TM as a DFA that's been functionally enhanced to allow at each computation step i) left/right (single) stepping of its input tape head ii) rewriting of the symbol under the tape head whereas a DFA is restricted to work with strictly right stepping of its "input tape head" so it only sees each character once (and so no concept of rewriting anything because it couldn't be reread anyway). So compared to a DFA transition rule, a TM rule still takes the same input as a DFA (current state, input character), but has to specify two additional data items: i) the direction to move the tape head. ii) the character to write back to the tape and For completeness, if you're familiar with DFAs but TMs not so much, I'll add: A) The DFA/TM termination conditions are a bit different. A DFA halts naturally at the end of the input string, so it's fine (and typical) to have accept/reject states that are entered multiple times during a computation, i.e. those states aren't "final" states in the TM sense. A TM clearly needs some other way to explicitly indicate it's finished. Typically (e.g. Linz) some TM states are designated "final" states that halt the TM - if it has accept/reject states those are final, so can only be entered once. (If we converted a DFA to a TM, we would need some obvious fiddling when we get to the DFA accept/reject states - simply designating them as TM final states wouldn't work...) B) The TM input tape is /potentially infinite/ in extent so there needs to be the rule for what's on the tape outside of its designated "input string" at the beginning of a computation. That's what the TM BLANK symbol is for. (DFA's by design can't get "beyond their input string", so no concept of a special BLANK symbol arises.) Mike.
[toc] | [prev] | [next] | [standalone]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2022-05-11 22:29 -0500 |
| Subject | Re: Validating that the implementation meets the spec for TM transition function [ best tape ] |
| Message-ID | <IIadnewQP-K84uH_nZ2dnUU7_83NnZ2d@giganews.com> |
| In reply to | #50274 |
On 5/11/2022 10:03 PM, Mike Terry wrote: > On 12/05/2022 01:05, olcott wrote: >> On 5/11/2022 6:01 PM, Mike Terry wrote: >>> On 11/05/2022 22:30, Malcolm McLean wrote: >>>> On Wednesday, 11 May 2022 at 16:27:37 UTC+1, Mike Terry wrote: >>>>> On 11/05/2022 10:19, Malcolm McLean wrote: >>>>>> On Wednesday, 11 May 2022 at 03:05:37 UTC+1, Mike Terry wrote: >>>>>>> >>>>>>> But what you suggest is quite workable... >>>>>>> >>>>>>> I think if I were interested in ultimate efficiency, I might go >>>>>>> with Jeff's "chained blocks" with a >>>>>>> comfortably large chosen page size. (But efficiency really isn't >>>>>>> an issue for this task!) >>>>>>> >>>>>> The tape is unbounded. And even some very simple machines will >>>>>> fill it up to infinity. >>>>>> If you stop the machine when the process runs out of memory, which >>>>>> is a reasonable >>>>>> strategy, you don't want O(N) tape write operations. >>>>>> >>>>>> Chained blocks are probably the best model. They don't scale up, >>>>>> so a machine that was written >>>>>> for a 16K ZX81 might struggle when ported to a 16GB typical modern >>>>>> desktop. If you know >>>>>> the approximate szie of your tape, however, then blocks are a good >>>>>> solution. >>>>>> >>>>> I don't get why you say a chained block approach doesn't scale up. >>>>> Such a design works well until >>>>> the logical (user) address space is filled, which is absolutely >>>>> huge on a modern 64-bit machine with >>>>> page files etc.. When the tape gets very large, only a small >>>>> portion of it needs to be in the >>>>> working set for the process to avoid paging. >>>>> >>>>> The only design I can think of that might scale up better would be >>>>> one using an output device larger >>>>> than the logical address space limit. Maybe you were just saying >>>>> that a hard-coded small block size >>>>> (for a ZX81?) is not as efficient as big blocks if you've got lots >>>>> of memory? I don't see that you >>>>> would use a chained block approach on such a tiny machine! Perhaps >>>>> you meant to say the design >>>>> doesn't scale /down/ rather than up? (And the size of chained >>>>> blocks can be dynamically decided at >>>>> run time if we like.) >>>>> >>>>> Other designs, e.g. using vector or strings will involve copying >>>>> ever larger blocks of memory around >>>>> when the vector/string is extended, so perhaps you meant to say >>>>> that /those/ designs don't scale up, >>>>> but the chained blocks scale up? >>>>> >>>> I was thinking that the chained block degenerates into effectively a >>>> linked list when block size becomes >>>> small in relation to tape length. However that isn't really a >>>> problem - it still works more effectively >>>> than a contiguous model. >>> >>> Yes, for a fixed block length it will be like a tape element linked >>> list, but only some small fraction of the allocation overhead. >>> Bigger blocks resulting in a smaller fraction. Or we could have some >>> kind of exponential block size growth, so we start with, say, 1 >>> allocation cost for the first 50000 tape elements, then getting >>> smaller as blocks get bigger - but 1 allocation per 50000 tape >>> elements is already a pretty small overhead for most purposes. E.g. >>> writing/testing PO's Even TM, we could make do with one single fixed >>> block of just 20 tape elements!!! I'd think the key thing for PO >>> should be to get on with the exercise, rather than playing with TM >>> emulator efficiency. >>> >>> Mike. >> >> It is more cost-effective to make it right the first time rather than >> have to go back and fix it. >> >> My adaptation of David's approach to the TM tape also seems to be an >> objectively better way to implement std::deque. >> >> I can't possibly do the exercise until I see 100% exactly how the >> transition function works. Although it is exactly the same idea as a >> DFA state transition, its seems to not be working that way. > > Yes the idea is the same but slightly more complicated. What seems not > to be working that way? > > You could think of a TM as a DFA that's been functionally enhanced to > allow at each computation step > i) left/right (single) stepping of its input tape head > ii) rewriting of the symbol under the tape head > whereas a DFA is restricted to work with strictly right stepping of its > "input tape head" so it only sees each character once (and so no concept > of rewriting anything because it couldn't be reread anyway). > > So compared to a DFA transition rule, a TM rule still takes the same > input as a DFA (current state, input character), but has to specify two > additional data items: > i) the direction to move the tape head. > ii) the character to write back to the tape and > > For completeness, if you're familiar with DFAs but TMs not so much, I'll > add: > > A) The DFA/TM termination conditions are a bit different. A DFA halts > naturally at the end of the input string, so it's fine (and typical) to > have accept/reject states that are entered multiple times during a > computation, i.e. those states aren't "final" states in the TM sense. A > TM clearly needs some other way to explicitly indicate it's finished. > Typically (e.g. Linz) some TM states are designated "final" states that > halt the TM - if it has accept/reject states those are final, so can > only be entered once. (If we converted a DFA to a TM, we would need > some obvious fiddling when we get to the DFA accept/reject states - > simply designating them as TM final states wouldn't work...) > > B) The TM input tape is /potentially infinite/ in extent so there needs > to be the rule for what's on the tape outside of its designated "input > string" at the beginning of a computation. That's what the TM BLANK > symbol is for. (DFA's by design can't get "beyond their input string", > so no concept of a special BLANK symbol arises.) > > > Mike. I think that I already knew all that stuff. I have two patents on DFA's so I know them well. They match screen pixels to recognized characters. The second patent is a patentable memory optimization of the first. I only got an very detailed looks at TM's in the last few days on the basis of this system: http://www.lns.mit.edu/~dsw/turing/turing.html I am rewriting it so that it has a three minute learning curve. -- Copyright 2022 Pete Olcott "Talent hits a target no one else can hit; Genius hits a target no one else can see." Arthur Schopenhauer
[toc] | [prev] | [next] | [standalone]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2022-05-11 22:37 -0500 |
| Subject | Re: Validating that the implementation meets the spec for TM transition function [ best tape ] |
| Message-ID | <XtydnWO7kvJnHeH_nZ2dnUU7_83NnZ2d@giganews.com> |
| In reply to | #50274 |
On 5/11/2022 10:03 PM, Mike Terry wrote: > On 12/05/2022 01:05, olcott wrote: >> On 5/11/2022 6:01 PM, Mike Terry wrote: >>> On 11/05/2022 22:30, Malcolm McLean wrote: >>>> On Wednesday, 11 May 2022 at 16:27:37 UTC+1, Mike Terry wrote: >>>>> On 11/05/2022 10:19, Malcolm McLean wrote: >>>>>> On Wednesday, 11 May 2022 at 03:05:37 UTC+1, Mike Terry wrote: >>>>>>> >>>>>>> But what you suggest is quite workable... >>>>>>> >>>>>>> I think if I were interested in ultimate efficiency, I might go >>>>>>> with Jeff's "chained blocks" with a >>>>>>> comfortably large chosen page size. (But efficiency really isn't >>>>>>> an issue for this task!) >>>>>>> >>>>>> The tape is unbounded. And even some very simple machines will >>>>>> fill it up to infinity. >>>>>> If you stop the machine when the process runs out of memory, which >>>>>> is a reasonable >>>>>> strategy, you don't want O(N) tape write operations. >>>>>> >>>>>> Chained blocks are probably the best model. They don't scale up, >>>>>> so a machine that was written >>>>>> for a 16K ZX81 might struggle when ported to a 16GB typical modern >>>>>> desktop. If you know >>>>>> the approximate szie of your tape, however, then blocks are a good >>>>>> solution. >>>>>> >>>>> I don't get why you say a chained block approach doesn't scale up. >>>>> Such a design works well until >>>>> the logical (user) address space is filled, which is absolutely >>>>> huge on a modern 64-bit machine with >>>>> page files etc.. When the tape gets very large, only a small >>>>> portion of it needs to be in the >>>>> working set for the process to avoid paging. >>>>> >>>>> The only design I can think of that might scale up better would be >>>>> one using an output device larger >>>>> than the logical address space limit. Maybe you were just saying >>>>> that a hard-coded small block size >>>>> (for a ZX81?) is not as efficient as big blocks if you've got lots >>>>> of memory? I don't see that you >>>>> would use a chained block approach on such a tiny machine! Perhaps >>>>> you meant to say the design >>>>> doesn't scale /down/ rather than up? (And the size of chained >>>>> blocks can be dynamically decided at >>>>> run time if we like.) >>>>> >>>>> Other designs, e.g. using vector or strings will involve copying >>>>> ever larger blocks of memory around >>>>> when the vector/string is extended, so perhaps you meant to say >>>>> that /those/ designs don't scale up, >>>>> but the chained blocks scale up? >>>>> >>>> I was thinking that the chained block degenerates into effectively a >>>> linked list when block size becomes >>>> small in relation to tape length. However that isn't really a >>>> problem - it still works more effectively >>>> than a contiguous model. >>> >>> Yes, for a fixed block length it will be like a tape element linked >>> list, but only some small fraction of the allocation overhead. >>> Bigger blocks resulting in a smaller fraction. Or we could have some >>> kind of exponential block size growth, so we start with, say, 1 >>> allocation cost for the first 50000 tape elements, then getting >>> smaller as blocks get bigger - but 1 allocation per 50000 tape >>> elements is already a pretty small overhead for most purposes. E.g. >>> writing/testing PO's Even TM, we could make do with one single fixed >>> block of just 20 tape elements!!! I'd think the key thing for PO >>> should be to get on with the exercise, rather than playing with TM >>> emulator efficiency. >>> >>> Mike. >> >> It is more cost-effective to make it right the first time rather than >> have to go back and fix it. >> >> My adaptation of David's approach to the TM tape also seems to be an >> objectively better way to implement std::deque. >> >> I can't possibly do the exercise until I see 100% exactly how the >> transition function works. Although it is exactly the same idea as a >> DFA state transition, its seems to not be working that way. > > Yes the idea is the same but slightly more complicated. What seems not > to be working that way? > > You could think of a TM as a DFA that's been functionally enhanced to > allow at each computation step > i) left/right (single) stepping of its input tape head > ii) rewriting of the symbol under the tape head > whereas a DFA is restricted to work with strictly right stepping of its > "input tape head" so it only sees each character once (and so no concept > of rewriting anything because it couldn't be reread anyway). > > So compared to a DFA transition rule, a TM rule still takes the same > input as a DFA (current state, input character), but has to specify two > additional data items: > i) the direction to move the tape head. > ii) the character to write back to the tape and > > For completeness, if you're familiar with DFAs but TMs not so much, I'll > add: > > A) The DFA/TM termination conditions are a bit different. A DFA halts > naturally at the end of the input string, so it's fine (and typical) to > have accept/reject states that are entered multiple times during a > computation, i.e. those states aren't "final" states in the TM sense. A > TM clearly needs some other way to explicitly indicate it's finished. > Typically (e.g. Linz) some TM states are designated "final" states that > halt the TM - if it has accept/reject states those are final, so can > only be entered once. (If we converted a DFA to a TM, we would need > some obvious fiddling when we get to the DFA accept/reject states - > simply designating them as TM final states wouldn't work...) > > B) The TM input tape is /potentially infinite/ in extent so there needs > to be the rule for what's on the tape outside of its designated "input > string" at the beginning of a computation. That's what the TM BLANK > symbol is for. (DFA's by design can't get "beyond their input string", > so no concept of a special BLANK symbol arises.) > > > Mike. These are the key details of the trasition function that I have been focusing on: A transition rule of a Turing machine has the following form δ(p, X) = (q, Y, L). This means that from state p, on reading the symbol X on the tape, the machine moves to state q, replaces X with Y and moves the tape head to the left. -- Copyright 2022 Pete Olcott "Talent hits a target no one else can hit; Genius hits a target no one else can see." Arthur Schopenhauer
[toc] | [prev] | [next] | [standalone]
| From | Ben <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2022-05-12 15:02 +0100 |
| Subject | Re: Validating that the implementation meets the spec for TM transition function [ best tape ] |
| Message-ID | <87sfpe4zo3.fsf@bsb.me.uk> |
| In reply to | #50274 |
Mike Terry <news.dead.person.stones@darjeeling.plus.com> writes: > You could think of a TM as a DFA that's been functionally enhanced to > allow at each computation step > i) left/right (single) stepping of its input tape head > ii) rewriting of the symbol under the tape head whereas a DFA is > restricted to work with strictly right stepping of its "input tape > head" so it only sees each character once (and so no concept of > rewriting anything because it couldn't be reread anyway). Though one used to talk about "transducer" DFAs where each edge of the graph also had an output symbol. This was not "written" anywhere but the result was the concatenation of output after processing the input. <cut> > A) The DFA/TM termination conditions are a bit different. A DFA halts > naturally at the end of the input string, so it's fine (and typical) > to have accept/reject states that are entered multiple times during a > computation, i.e. those states aren't "final" states in the TM sense. > A TM clearly needs some other way to explicitly indicate it's > finished. Typically (e.g. Linz) some TM states are designated "final" > states that halt the TM - if it has accept/reject states those are > final, so can only be entered once. This is, as you say, typical. But it's horrid! Almost every author seems to copy this ancient idea, but there's no need for the complication. A TM halts "naturally" when in a state that has no defined transition for the current input. If you want and accept/reject notion, then one can use a simple convention that the TM accepts if it halts in a state with no defined transitions at all, but rejects if it halts in state with defined transitions, none of which apply for the current input. A few people prefer not to bother with accepting and rejecting states at all, but instead just use the resulting tape. For example, the TM is deemed to have rejected the input if the tape is empty (i.e. contains no non-blank symbols). Both of these make the presentation simpler for teaching this material. -- Ben.
[toc] | [prev] | [next] | [standalone]
| From | Mike Terry <news.dead.person.stones@darjeeling.plus.com> |
|---|---|
| Date | 2022-05-12 19:03 +0100 |
| Subject | Re: Validating that the implementation meets the spec for TM transition function [ best tape ] |
| Message-ID | <rNadnW2d0_Zm1uD_nZ2dnUU7-VfNnZ2d@brightview.co.uk> |
| In reply to | #50281 |
On 12/05/2022 15:02, Ben wrote: > Mike Terry <news.dead.person.stones@darjeeling.plus.com> writes: > >> You could think of a TM as a DFA that's been functionally enhanced to >> allow at each computation step >> i) left/right (single) stepping of its input tape head >> ii) rewriting of the symbol under the tape head whereas a DFA is >> restricted to work with strictly right stepping of its "input tape >> head" so it only sees each character once (and so no concept of >> rewriting anything because it couldn't be reread anyway). > > Though one used to talk about "transducer" DFAs where each edge of the > graph also had an output symbol. This was not "written" anywhere but > the result was the concatenation of output after processing the input. > > <cut> >> A) The DFA/TM termination conditions are a bit different. A DFA halts >> naturally at the end of the input string, so it's fine (and typical) >> to have accept/reject states that are entered multiple times during a >> computation, i.e. those states aren't "final" states in the TM sense. >> A TM clearly needs some other way to explicitly indicate it's >> finished. Typically (e.g. Linz) some TM states are designated "final" >> states that halt the TM - if it has accept/reject states those are >> final, so can only be entered once. > > This is, as you say, typical. But it's horrid! Almost every author > seems to copy this ancient idea, but there's no need for the > complication. A TM halts "naturally" when in a state that has no > defined transition for the current input. From a programming perspective, I can see how that's a bit more convenient, but I don't like the idea that much - e.g. with an explicit halt state we can see it clearly on the state transition diagram (as one of the destination circles pointed to by arrows). The alternative is having to inspect all the circles and identify those which are lacking some transition rule - that's lacking transparency in my opinion. (And if I identify such a state missing one or more arrows, am I to assume that's deliberate to create a halt condition, or does the author simply know that those conditions will never arise during execution, and was being "lazy"?) I wouldn't mind some kind of "special arrow" which incorporates a stop sign, but that's hardly different from having it lead to a proper state designated as a halt state. (The stop sign would be part of the arrow, not an actual TM state.) But now, logically we have two valid candidates for a transition rule: a normal one, or a special "stop arrow", which logically complicates the definition slightly. (But it's ok) So I'm thinking that an explicit halt state is maybe the most (conceptually) logical way to do it, and I like "conceptually logical". To me the "no defined transition rule" seems like a kind of hack invented by a programmer to save a few lines of code! (I've nothing against programmers of course, and if you teach people to program TM simulators, I can see the appeal of the idea.) > If you want and accept/reject > notion, then one can use a simple convention that the TM accepts if it > halts in a state with no defined transitions at all, but rejects if it > halts in state with defined transitions, none of which apply for the > current input. That seems (conceptually) awful to me! I mean, where's the /logic/ in that, beyond making the programming task well defined for someone building a TM simulator? It's like a programmer logically needing some extra state info (a flag, say) to represent some program condition, but saying "hang on - I don't need to create that flag, because I can use some other artificial setting of an existing variable to indicate a special condition, and look - I save having to create the extra flag!!". Well, perhaps the flag was the logical (and so IMO better) thing to do all along. (Thinks: file readchar/readbyte returning EOF as a special character value in lieu of a genuine data byte. Simply Not Logical IMO...) Perhaps if I were more bold I might suggest your perspective could be overly shaped by your day to day job experience of teaching the /simulation/ side of the subject... :) For me, TMs are /mathematical/ constructs, used to discuss the nature of computation and limits of algorithms etc.. So naturally I like logical mathematical definitions. For me, the weighting (out of 10) I'd apply to "making a programmer's job easier when coding a TM simulator" would be 0. I mean, it's not /that/ hard whichever way we go. > > A few people prefer not to bother with accepting and rejecting states at > all, but instead just use the resulting tape. For example, the TM is > deemed to have rejected the input if the tape is empty (i.e. contains no > non-blank symbols). Isn't there a problem here, in that now we can't actually tell when a computation is finished? Say after 10^234829873473829 steps no output has been written - what does that signify? OK, "nothing" is an answer, but then is this actually in line with our original intuitions which were concerning /finite/ algorithms? This is a bit more like when TMs are /acceptors/ (recognisers?) rather than deciders, but even then, if a non-blank is written to the tape, it could be subsequently blanked out again, so its not really like an acceptor. Perhaps something like "accept if 0 is ever written to the tape, reject if 1 is ever written"? That would logially work I guess. I do understand that there are a million TM variations in play in the literature, and that's before we get on to how they should be /used/ e.g. in defining computable functions, which need further decisions on how inputs/outputs are to be representated. OK it's only now occured to me that you didn't say "..not to bother with *final* states.." or "..not to bother with *halting*..". So I'm sure you meant having some explicit HALT action, followed by checking the tape to distinguish the halting reason - which makes perfect sense, and is maybe how I would have invented TMs (Terry-machines of course) :) Mike.
[toc] | [prev] | [next] | [standalone]
| From | Ben <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2022-05-12 19:30 +0100 |
| Subject | Re: Validating that the implementation meets the spec for TM transition function [ best tape ] |
| Message-ID | <87h75u4n9j.fsf@bsb.me.uk> |
| In reply to | #50290 |
Mike Terry <news.dead.person.stones@darjeeling.plus.com> writes: > On 12/05/2022 15:02, Ben wrote: >> Mike Terry <news.dead.person.stones@darjeeling.plus.com> writes: >> >>> You could think of a TM as a DFA that's been functionally enhanced to >>> allow at each computation step >>> i) left/right (single) stepping of its input tape head >>> ii) rewriting of the symbol under the tape head whereas a DFA is >>> restricted to work with strictly right stepping of its "input tape >>> head" so it only sees each character once (and so no concept of >>> rewriting anything because it couldn't be reread anyway). >> Though one used to talk about "transducer" DFAs where each edge of the >> graph also had an output symbol. This was not "written" anywhere but >> the result was the concatenation of output after processing the input. >> <cut> >>> A) The DFA/TM termination conditions are a bit different. A DFA halts >>> naturally at the end of the input string, so it's fine (and typical) >>> to have accept/reject states that are entered multiple times during a >>> computation, i.e. those states aren't "final" states in the TM sense. >>> A TM clearly needs some other way to explicitly indicate it's >>> finished. Typically (e.g. Linz) some TM states are designated "final" >>> states that halt the TM - if it has accept/reject states those are >>> final, so can only be entered once. >> This is, as you say, typical. But it's horrid! Almost every author >> seems to copy this ancient idea, but there's no need for the >> complication. A TM halts "naturally" when in a state that has no >> defined transition for the current input. > > From a programming perspective, I can see how that's a bit more > convenient, but I don't like the idea that much - e.g. with an > explicit halt state we can see it clearly on the state transition > diagram (as one of the destination circles pointed to by arrows). The > alternative is having to inspect all the circles and identify those > which are lacking some transition rule - that's lacking transparency > in my opinion. > > (And if I identify such a state missing one or more arrows, am I to > assume that's deliberate to create a halt condition, or does the > author simply know that those conditions will never arise during > execution, and was being "lazy"?) When reasoning about termination, you have to consider halting in non-final states, so I don't think it matters much. > So I'm thinking that an explicit halt state is maybe the most > (conceptually) logical way to do it, and I like "conceptually > logical". To me the "no defined transition rule" seems like a kind of > hack invented by a programmer to save a few lines of code! (I've > nothing against programmers of course, and if you teach people to > program TM simulators, I can see the appeal of the idea.) > >> If you want and accept/reject >> notion, then one can use a simple convention that the TM accepts if it >> halts in a state with no defined transitions at all, but rejects if it >> halts in state with defined transitions, none of which apply for the >> current input. > > That seems (conceptually) awful to me! I mean, where's the /logic/ in > that, beyond making the programming task well defined for someone > building a TM simulator? The logic here that you have to consider the one case anyway (halting because of no defined transition) and the second case is as explicit as you'd like -- a state with no out-going arrows. You can even agree to draw double circles of these. > Perhaps if I were more bold I might suggest your perspective could be > overly shaped by your day to day job experience of teaching the > /simulation/ side of the subject... :) That's possible. Though one almost always just does this as a sketch. The full details of a UTM are messy and don't really add much. > For me, TMs are /mathematical/ constructs, used to discuss the nature > of computation and limits of algorithms etc.. So naturally I like > logical mathematical definitions. For me, the weighting (out of 10) > I'd apply to "making a programmer's job easier when coding a TM > simulator" would be 0. I mean, it's not /that/ hard whichever way we > go. I don't see it like that at all. The reasoning about TMs is not made any easier by the usual definitions unless, possibly, you insist that the state transition function always maps every member of the tape alphabet. >> A few people prefer not to bother with accepting and rejecting states at >> all, but instead just use the resulting tape. For example, the TM is >> deemed to have rejected the input if the tape is empty (i.e. contains no >> non-blank symbols). > > Isn't there a problem here, in that now we can't actually tell when a > computation is finished? Say after 10^234829873473829 steps no output > has been written - what does that signify? OK, "nothing" is an > answer, but then is this actually in line with our original intuitions > which were concerning /finite/ algorithms? This is a bit more like > when TMs are /acceptors/ (recognisers?) rather than deciders, but even > then, if a non-blank is written to the tape, it could be subsequently > blanked out again, so its not really like an acceptor. I don't see what you are getting at. How is this different with explicit final states? There's no "we watch and see" here because, as you say, TMs are mathematical constructs and a TM/input pair either denotes a finite sequence of configurations or it does not. > Perhaps something like "accept if 0 is ever written to the tape, > reject if 1 is ever written"? That would logially work I guess. That would be weird. > OK it's only now occured to me that you didn't say "..not to bother > with *final* states.." or "..not to bother with *halting*..". So I'm > sure you meant having some explicit HALT action, followed by checking > the tape to distinguish the halting reason - which makes perfect > sense, and is maybe how I would have invented TMs (Terry-machines of > course) :) I'm not sure I follow. Maybe you do see what I'm getting at? A decider, D, for a set, L(D), is a TM that always halts. It therefore computes a total function f_D: Σ* -> Σ*. The accept/reject notion is just a convention that can just as easily be defined as f_D(s) = "" (say). Similarly, a recogniser computes a partial function. This is independent of the issue of how and when a TM halts, but my preference is for both my suggestions. -- Ben.
[toc] | [prev] | [next] | [standalone]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2022-05-12 14:23 -0500 |
| Subject | Re: Validating that the implementation meets the spec for TM transition function [ best tape ] |
| Message-ID | <z7SdnWv_pvw6w-D_nZ2dnUU7_8zNnZ2d@giganews.com> |
| In reply to | #50293 |
On 5/12/2022 1:30 PM, Ben wrote: > Mike Terry <news.dead.person.stones@darjeeling.plus.com> writes: > >> On 12/05/2022 15:02, Ben wrote: >>> Mike Terry <news.dead.person.stones@darjeeling.plus.com> writes: >>> >>>> You could think of a TM as a DFA that's been functionally enhanced to >>>> allow at each computation step >>>> i) left/right (single) stepping of its input tape head >>>> ii) rewriting of the symbol under the tape head whereas a DFA is >>>> restricted to work with strictly right stepping of its "input tape >>>> head" so it only sees each character once (and so no concept of >>>> rewriting anything because it couldn't be reread anyway). >>> Though one used to talk about "transducer" DFAs where each edge of the >>> graph also had an output symbol. This was not "written" anywhere but >>> the result was the concatenation of output after processing the input. >>> <cut> >>>> A) The DFA/TM termination conditions are a bit different. A DFA halts >>>> naturally at the end of the input string, so it's fine (and typical) >>>> to have accept/reject states that are entered multiple times during a >>>> computation, i.e. those states aren't "final" states in the TM sense. >>>> A TM clearly needs some other way to explicitly indicate it's >>>> finished. Typically (e.g. Linz) some TM states are designated "final" >>>> states that halt the TM - if it has accept/reject states those are >>>> final, so can only be entered once. >>> This is, as you say, typical. But it's horrid! Almost every author >>> seems to copy this ancient idea, but there's no need for the >>> complication. A TM halts "naturally" when in a state that has no >>> defined transition for the current input. >> >> From a programming perspective, I can see how that's a bit more >> convenient, but I don't like the idea that much - e.g. with an >> explicit halt state we can see it clearly on the state transition >> diagram (as one of the destination circles pointed to by arrows). The >> alternative is having to inspect all the circles and identify those >> which are lacking some transition rule - that's lacking transparency >> in my opinion. >> >> (And if I identify such a state missing one or more arrows, am I to >> assume that's deliberate to create a halt condition, or does the >> author simply know that those conditions will never arise during >> execution, and was being "lazy"?) > > When reasoning about termination, you have to consider halting in > non-final states, so I don't think it matters much. This is what I am going by: The Turing machine halts if it is in a state for which there is no quintuple telling it what to do for the symbol being read. The Turing machine is said to 'halt in a final state' if there is no quintuple at all on the list with the given state symbol as a first character. If a Turing machine halts in a final state for a given tape it is said to 'accept' or 'recognize' the tape. http://www.lns.mit.edu/~dsw/turing/doc/tm_manual.txt > >> So I'm thinking that an explicit halt state is maybe the most >> (conceptually) logical way to do it, and I like "conceptually >> logical". To me the "no defined transition rule" seems like a kind of >> hack invented by a programmer to save a few lines of code! (I've >> nothing against programmers of course, and if you teach people to >> program TM simulators, I can see the appeal of the idea.) >> >>> If you want and accept/reject >>> notion, then one can use a simple convention that the TM accepts if it >>> halts in a state with no defined transitions at all, but rejects if it >>> halts in state with defined transitions, none of which apply for the >>> current input. >> >> That seems (conceptually) awful to me! I mean, where's the /logic/ in >> that, beyond making the programming task well defined for someone >> building a TM simulator? > > The logic here that you have to consider the one case anyway (halting > because of no defined transition) and the second case is as explicit as > you'd like -- a state with no out-going arrows. You can even agree to > draw double circles of these. > Seems to say that same as David S. Woodruff's text quoted above. >> Perhaps if I were more bold I might suggest your perspective could be >> overly shaped by your day to day job experience of teaching the >> /simulation/ side of the subject... :) > > That's possible. Though one almost always just does this as a sketch. > The full details of a UTM are messy and don't really add much. > >> For me, TMs are /mathematical/ constructs, used to discuss the nature >> of computation and limits of algorithms etc.. So naturally I like >> logical mathematical definitions. For me, the weighting (out of 10) >> I'd apply to "making a programmer's job easier when coding a TM >> simulator" would be 0. I mean, it's not /that/ hard whichever way we >> go. > > I don't see it like that at all. The reasoning about TMs is not made > any easier by the usual definitions unless, possibly, you insist that > the state transition function always maps every member of the tape > alphabet. > >>> A few people prefer not to bother with accepting and rejecting states at >>> all, but instead just use the resulting tape. For example, the TM is >>> deemed to have rejected the input if the tape is empty (i.e. contains no >>> non-blank symbols). >> >> Isn't there a problem here, in that now we can't actually tell when a >> computation is finished? Say after 10^234829873473829 steps no output >> has been written - what does that signify? OK, "nothing" is an >> answer, but then is this actually in line with our original intuitions >> which were concerning /finite/ algorithms? This is a bit more like >> when TMs are /acceptors/ (recognisers?) rather than deciders, but even >> then, if a non-blank is written to the tape, it could be subsequently >> blanked out again, so its not really like an acceptor. > > I don't see what you are getting at. How is this different with > explicit final states? > > There's no "we watch and see" here because, as you say, TMs are > mathematical constructs and a TM/input pair either denotes a finite > sequence of configurations or it does not. > The ultimate measure of the behavior of the code is its correct simulation or direct execution. >> Perhaps something like "accept if 0 is ever written to the tape, >> reject if 1 is ever written"? That would logially work I guess. > > That would be weird. > Final states named "N" or "Y" seem fine to me. >> OK it's only now occured to me that you didn't say "..not to bother >> with *final* states.." or "..not to bother with *halting*..". So I'm >> sure you meant having some explicit HALT action, followed by checking >> the tape to distinguish the halting reason - which makes perfect >> sense, and is maybe how I would have invented TMs (Terry-machines of >> course) :) > > I'm not sure I follow. Maybe you do see what I'm getting at? A > decider, D, for a set, L(D), is a TM that always halts. It therefore > computes a total function f_D: Σ* -> Σ*. The accept/reject notion is > just a convention that can just as easily be defined as f_D(s) = "" > (say). Similarly, a recogniser computes a partial function. > > This is independent of the issue of how and when a TM halts, but my > preference is for both my suggestions. > -- Copyright 2022 Pete Olcott "Talent hits a target no one else can hit; Genius hits a target no one else can see." Arthur Schopenhauer
[toc] | [prev] | [next] | [standalone]
| From | Richard Damon <Richard@Damon-Family.org> |
|---|---|
| Date | 2022-05-12 19:19 -0400 |
| Subject | Re: Validating that the implementation meets the spec for TM transition function [ best tape ] |
| Message-ID | <fCgfK.7814$pqKf.3074@fx12.iad> |
| In reply to | #50293 |
On 5/12/22 2:30 PM, Ben wrote: > Mike Terry <news.dead.person.stones@darjeeling.plus.com> writes: > >> On 12/05/2022 15:02, Ben wrote: >>> Mike Terry <news.dead.person.stones@darjeeling.plus.com> writes: >>> >>>> You could think of a TM as a DFA that's been functionally enhanced to >>>> allow at each computation step >>>> i) left/right (single) stepping of its input tape head >>>> ii) rewriting of the symbol under the tape head whereas a DFA is >>>> restricted to work with strictly right stepping of its "input tape >>>> head" so it only sees each character once (and so no concept of >>>> rewriting anything because it couldn't be reread anyway). >>> Though one used to talk about "transducer" DFAs where each edge of the >>> graph also had an output symbol. This was not "written" anywhere but >>> the result was the concatenation of output after processing the input. >>> <cut> >>>> A) The DFA/TM termination conditions are a bit different. A DFA halts >>>> naturally at the end of the input string, so it's fine (and typical) >>>> to have accept/reject states that are entered multiple times during a >>>> computation, i.e. those states aren't "final" states in the TM sense. >>>> A TM clearly needs some other way to explicitly indicate it's >>>> finished. Typically (e.g. Linz) some TM states are designated "final" >>>> states that halt the TM - if it has accept/reject states those are >>>> final, so can only be entered once. >>> This is, as you say, typical. But it's horrid! Almost every author >>> seems to copy this ancient idea, but there's no need for the >>> complication. A TM halts "naturally" when in a state that has no >>> defined transition for the current input. >> >> From a programming perspective, I can see how that's a bit more >> convenient, but I don't like the idea that much - e.g. with an >> explicit halt state we can see it clearly on the state transition >> diagram (as one of the destination circles pointed to by arrows). The >> alternative is having to inspect all the circles and identify those >> which are lacking some transition rule - that's lacking transparency >> in my opinion. >> >> (And if I identify such a state missing one or more arrows, am I to >> assume that's deliberate to create a halt condition, or does the >> author simply know that those conditions will never arise during >> execution, and was being "lazy"?) > > When reasoning about termination, you have to consider halting in > non-final states, so I don't think it matters much. > >> So I'm thinking that an explicit halt state is maybe the most >> (conceptually) logical way to do it, and I like "conceptually >> logical". To me the "no defined transition rule" seems like a kind of >> hack invented by a programmer to save a few lines of code! (I've >> nothing against programmers of course, and if you teach people to >> program TM simulators, I can see the appeal of the idea.) >> >>> If you want and accept/reject >>> notion, then one can use a simple convention that the TM accepts if it >>> halts in a state with no defined transitions at all, but rejects if it >>> halts in state with defined transitions, none of which apply for the >>> current input. >> >> That seems (conceptually) awful to me! I mean, where's the /logic/ in >> that, beyond making the programming task well defined for someone >> building a TM simulator? > > The logic here that you have to consider the one case anyway (halting > because of no defined transition) and the second case is as explicit as > you'd like -- a state with no out-going arrows. You can even agree to > draw double circles of these. > >> Perhaps if I were more bold I might suggest your perspective could be >> overly shaped by your day to day job experience of teaching the >> /simulation/ side of the subject... :) > > That's possible. Though one almost always just does this as a sketch. > The full details of a UTM are messy and don't really add much. > >> For me, TMs are /mathematical/ constructs, used to discuss the nature >> of computation and limits of algorithms etc.. So naturally I like >> logical mathematical definitions. For me, the weighting (out of 10) >> I'd apply to "making a programmer's job easier when coding a TM >> simulator" would be 0. I mean, it's not /that/ hard whichever way we >> go. > > I don't see it like that at all. The reasoning about TMs is not made > any easier by the usual definitions unless, possibly, you insist that > the state transition function always maps every member of the tape > alphabet. > >>> A few people prefer not to bother with accepting and rejecting states at >>> all, but instead just use the resulting tape. For example, the TM is >>> deemed to have rejected the input if the tape is empty (i.e. contains no >>> non-blank symbols). >> >> Isn't there a problem here, in that now we can't actually tell when a >> computation is finished? Say after 10^234829873473829 steps no output >> has been written - what does that signify? OK, "nothing" is an >> answer, but then is this actually in line with our original intuitions >> which were concerning /finite/ algorithms? This is a bit more like >> when TMs are /acceptors/ (recognisers?) rather than deciders, but even >> then, if a non-blank is written to the tape, it could be subsequently >> blanked out again, so its not really like an acceptor. > > I don't see what you are getting at. How is this different with > explicit final states? > > There's no "we watch and see" here because, as you say, TMs are > mathematical constructs and a TM/input pair either denotes a finite > sequence of configurations or it does not. > >> Perhaps something like "accept if 0 is ever written to the tape, >> reject if 1 is ever written"? That would logially work I guess. > > That would be weird. > >> OK it's only now occured to me that you didn't say "..not to bother >> with *final* states.." or "..not to bother with *halting*..". So I'm >> sure you meant having some explicit HALT action, followed by checking >> the tape to distinguish the halting reason - which makes perfect >> sense, and is maybe how I would have invented TMs (Terry-machines of >> course) :) > > I'm not sure I follow. Maybe you do see what I'm getting at? A > decider, D, for a set, L(D), is a TM that always halts. It therefore > computes a total function f_D: Σ* -> Σ*. The accept/reject notion is > just a convention that can just as easily be defined as f_D(s) = "" > (say). Similarly, a recogniser computes a partial function. > > This is independent of the issue of how and when a TM halts, but my > preference is for both my suggestions. > The two views, Halting ONLY in "Final States" or Halting in any state that doesn't have a Rule defined for the current tape character are really equivalent (unless you are doing Turing Machine Golf, where the "size" of the machine is important. A Machine defined by the "Final State" rule automatically meets the requirements for a "No Rule" machine, as the Final States, by definition, have no rules leaving them. If you have a machine defined by the "No Rule" condition, you can convert it to a "Final State" description by filling in all the states with some but not all inputs, to transition on the undefined inputs to a final state (either unique if the end state matters, or one common Final State). The "No Rule" termination condition allows for slightly more compact machines in some cases, but unless you are actually counting states, (like Busy Beaver) it doesn't really matter.
[toc] | [prev] | [next] | [standalone]
| From | Mike Terry <news.dead.person.stones@darjeeling.plus.com> |
|---|---|
| Date | 2022-05-13 01:02 +0100 |
| Subject | Re: Validating that the implementation meets the spec for TM transition function [ best tape ] |
| Message-ID | <t5k765$1qcu$1@gioia.aioe.org> |
| In reply to | #50293 |
On 12/05/2022 19:30, Ben wrote: > Mike Terry <news.dead.person.stones@darjeeling.plus.com> writes: > >> On 12/05/2022 15:02, Ben wrote: >>> Mike Terry <news.dead.person.stones@darjeeling.plus.com> writes: >>> >>>> You could think of a TM as a DFA that's been functionally enhanced to >>>> allow at each computation step >>>> i) left/right (single) stepping of its input tape head >>>> ii) rewriting of the symbol under the tape head whereas a DFA is >>>> restricted to work with strictly right stepping of its "input tape >>>> head" so it only sees each character once (and so no concept of >>>> rewriting anything because it couldn't be reread anyway). >>> Though one used to talk about "transducer" DFAs where each edge of the >>> graph also had an output symbol. This was not "written" anywhere but >>> the result was the concatenation of output after processing the input. >>> <cut> >>>> A) The DFA/TM termination conditions are a bit different. A DFA halts >>>> naturally at the end of the input string, so it's fine (and typical) >>>> to have accept/reject states that are entered multiple times during a >>>> computation, i.e. those states aren't "final" states in the TM sense. >>>> A TM clearly needs some other way to explicitly indicate it's >>>> finished. Typically (e.g. Linz) some TM states are designated "final" >>>> states that halt the TM - if it has accept/reject states those are >>>> final, so can only be entered once. >>> This is, as you say, typical. But it's horrid! Almost every author >>> seems to copy this ancient idea, but there's no need for the >>> complication. A TM halts "naturally" when in a state that has no >>> defined transition for the current input. >> >> From a programming perspective, I can see how that's a bit more >> convenient, but I don't like the idea that much - e.g. with an >> explicit halt state we can see it clearly on the state transition >> diagram (as one of the destination circles pointed to by arrows). The >> alternative is having to inspect all the circles and identify those >> which are lacking some transition rule - that's lacking transparency >> in my opinion. >> >> (And if I identify such a state missing one or more arrows, am I to >> assume that's deliberate to create a halt condition, or does the >> author simply know that those conditions will never arise during >> execution, and was being "lazy"?) > > When reasoning about termination, you have to consider halting in > non-final states, so I don't think it matters much. > >> So I'm thinking that an explicit halt state is maybe the most >> (conceptually) logical way to do it, and I like "conceptually >> logical". To me the "no defined transition rule" seems like a kind of >> hack invented by a programmer to save a few lines of code! (I've >> nothing against programmers of course, and if you teach people to >> program TM simulators, I can see the appeal of the idea.) >> >>> If you want and accept/reject >>> notion, then one can use a simple convention that the TM accepts if it >>> halts in a state with no defined transitions at all, but rejects if it >>> halts in state with defined transitions, none of which apply for the >>> current input. >> >> That seems (conceptually) awful to me! I mean, where's the /logic/ in >> that, beyond making the programming task well defined for someone >> building a TM simulator? > > The logic here that you have to consider the one case anyway (halting > because of no defined transition) and the second case is as explicit as > you'd like -- a state with no out-going arrows. You can even agree to > draw double circles of these. (ok, but I don't like the "halt because of missing rule" idea either! :) ) > >> Perhaps if I were more bold I might suggest your perspective could be >> overly shaped by your day to day job experience of teaching the >> /simulation/ side of the subject... :) > > That's possible. Though one almost always just does this as a sketch. > The full details of a UTM are messy and don't really add much. > >> For me, TMs are /mathematical/ constructs, used to discuss the nature >> of computation and limits of algorithms etc.. So naturally I like >> logical mathematical definitions. For me, the weighting (out of 10) >> I'd apply to "making a programmer's job easier when coding a TM >> simulator" would be 0. I mean, it's not /that/ hard whichever way we >> go. > > I don't see it like that at all. The reasoning about TMs is not made > any easier by the usual definitions unless, possibly, you insist that > the state transition function always maps every member of the tape > alphabet. I'd be ok with insisting that the function is complete rather than partial. Actually, that seems mathematically most "natural" to me, but I get that it's a /pain/ for a TM programmer, so an emulator design could relax that requiremnent. But mainly my point was just that I feel (my preference) is for halting to be totally explicit, rather than a kind of default/fall back when no transition rule is found. A consequence is that NOT having a transition rule to apply must simply be not allowed. [Either the transition map is complete, or in the case of a practical TM simulator it's the TM builder's responsibility to always have a rule when not in a final state.] It's not to do with ease of use, but just my desire for the TM definition to match my intuition of "algorithm" as closely as it can. That intuition is basically the (ancient, pre-TM) flow-chart which in TM terms becomes the state transition graph, and it seems more natural to have a "STOP" box, like in a flow-chart. If a flow-chart led to a box that had no arrows readers would say WTF???, not think "aha, that must mean I've reached the end". But all this is just my preference, no big deal. Of course I understand they're all equivalent mathematically. > >>> A few people prefer not to bother with accepting and rejecting states at >>> all, but instead just use the resulting tape. For example, the TM is >>> deemed to have rejected the input if the tape is empty (i.e. contains no >>> non-blank symbols). >> >> Isn't there a problem here, in that now we can't actually tell when a >> computation is finished? Say after 10^234829873473829 steps no output >> has been written - what does that signify? OK, "nothing" is an >> answer, but then is this actually in line with our original intuitions >> which were concerning /finite/ algorithms? This is a bit more like >> when TMs are /acceptors/ (recognisers?) rather than deciders, but even >> then, if a non-blank is written to the tape, it could be subsequently >> blanked out again, so its not really like an acceptor. > > I don't see what you are getting at. How is this different with > explicit final states? Um, at this point I thought you were suggesting the TMs /didn't/ halt, but somehow just used what was written to the tape to indicate accept/reject!! See final remalks. > > There's no "we watch and see" here because, as you say, TMs are > mathematical constructs and a TM/input pair either denotes a finite > sequence of configurations or it does not. > >> Perhaps something like "accept if 0 is ever written to the tape, >> reject if 1 is ever written"? That would logially work I guess. > > That would be weird. Agreed! (at this point I was under a misapprehension - see final remarks.) > >> OK it's only now occured to me that you didn't say "..not to bother >> with *final* states.." or "..not to bother with *halting*..". So I'm >> sure you meant having some explicit HALT action, followed by checking >> the tape to distinguish the halting reason - which makes perfect >> sense, and is maybe how I would have invented TMs (Terry-machines of >> course) :) > > I'm not sure I follow. Maybe you do see what I'm getting at? A > decider, D, for a set, L(D), is a TM that always halts. It therefore > computes a total function f_D: Σ* -> Σ*. The accept/reject notion is > just a convention that can just as easily be defined as f_D(s) = "" > (say). Similarly, a recogniser computes a partial function. > > This is independent of the issue of how and when a TM halts, but my > preference is for both my suggestions. I do see what you're getting at. You were NOT saying that all TMs would by implication never terminate. (Duh, lol) You were saying that the decider TM terminates [by some agreed mechanism, even though it has no accept/reject states], and then we have to specify how we will interpret accept vs reject haltings - which can readily be done through what is finally on the tape. No problem - that's what my final paragraph was concluding. The problem was I DIDN'T read what you said that way at first, and so had written a couple of paragraphs on a faulty basis. So my fault for misreading, and also for not going back and rewriting what I'd said before. WHY would I think you were saying such a bizarre thing?? Well, in Linz (&similar), deciders have two final states, accept/reject, and I misinterpreted your "A few people prefer not to bother with accepting and rejecting states at all, but instead just use the resulting tape" as saying the TMs never halted [they have no remaining final states!] but just use the tape to indicate their decision somehow. My mistake... Mike.
[toc] | [prev] | [next] | [standalone]
| From | Jeff Barnett <jbb@notatt.com> |
|---|---|
| Date | 2022-05-11 23:13 -0600 |
| Subject | Re: Validating that the implementation meets the spec for TM transition function [ best tape ] |
| Message-ID | <t5i51b$5so$1@dont-email.me> |
| In reply to | #50247 |
On 5/11/2022 3:30 PM, Malcolm McLean wrote: > On Wednesday, 11 May 2022 at 16:27:37 UTC+1, Mike Terry wrote: >> On 11/05/2022 10:19, Malcolm McLean wrote: >>> On Wednesday, 11 May 2022 at 03:05:37 UTC+1, Mike Terry wrote: >>>> >>>> But what you suggest is quite workable... >>>> >>>> I think if I were interested in ultimate efficiency, I might go with Jeff's "chained blocks" with a >>>> comfortably large chosen page size. (But efficiency really isn't an issue for this task!) >>>> >>> The tape is unbounded. And even some very simple machines will fill it up to infinity. >>> If you stop the machine when the process runs out of memory, which is a reasonable >>> strategy, you don't want O(N) tape write operations. >>> >>> Chained blocks are probably the best model. They don't scale up, so a machine that was written >>> for a 16K ZX81 might struggle when ported to a 16GB typical modern desktop. If you know >>> the approximate szie of your tape, however, then blocks are a good solution. >>> >> I don't get why you say a chained block approach doesn't scale up. Such a design works well until >> the logical (user) address space is filled, which is absolutely huge on a modern 64-bit machine with >> page files etc.. When the tape gets very large, only a small portion of it needs to be in the >> working set for the process to avoid paging. >> >> The only design I can think of that might scale up better would be one using an output device larger >> than the logical address space limit. Maybe you were just saying that a hard-coded small block size >> (for a ZX81?) is not as efficient as big blocks if you've got lots of memory? I don't see that you >> would use a chained block approach on such a tiny machine! Perhaps you meant to say the design >> doesn't scale /down/ rather than up? (And the size of chained blocks can be dynamically decided at >> run time if we like.) >> >> Other designs, e.g. using vector or strings will involve copying ever larger blocks of memory around >> when the vector/string is extended, so perhaps you meant to say that /those/ designs don't scale up, >> but the chained blocks scale up? >> > I was thinking that the chained block degenerates into effectively a linked list when block size becomes > small in relation to tape length. However that isn't really a problem - it still works more effectively > than a contiguous model. Right. And by allocating these blocks in multiples of the page (least common multiple of swap page and cache page size), you'll keep the caches full of the right stuff. The time overhead is that you must check if the +1 or -1 positioning to see if you are at a block boundary for each increment; the storage penalty is that you must keep both a forward and backward link pointer on each page. This approach can be adapted to really, really long tapes (>> terabyte) and will be no uglier then other approaches. My (not so hidden) assumption are that nobody is really thinking of dealing with such really, really long tapes, i.e., this whole project is viewed more as a pedagogical exercise. A second assumption is that the thing to optimize is cache hits given secondary assumptions that modern user-level computers have wide and fewer cache "words" so you want something that almost guarantees that you will "pound" each cache word many times and that your program including your part of the memory management will all stay in the cache. What is really amazing to me is that Ben got such greater throughput with what he described as a very casual approach! So maybe all of our talk is rather premature until someone wants to do BB for new state size bounds. -- Jeff Barnett
[toc] | [prev] | [next] | [standalone]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2022-05-12 00:43 -0500 |
| Subject | Re: Validating that the implementation meets the spec for TM transition function [ best tape ] |
| Message-ID | <msudnevON-QSA-H_nZ2dnUU7_83NnZ2d@giganews.com> |
| In reply to | #50278 |
On 5/12/2022 12:13 AM, Jeff Barnett wrote: > On 5/11/2022 3:30 PM, Malcolm McLean wrote: >> On Wednesday, 11 May 2022 at 16:27:37 UTC+1, Mike Terry wrote: >>> On 11/05/2022 10:19, Malcolm McLean wrote: >>>> On Wednesday, 11 May 2022 at 03:05:37 UTC+1, Mike Terry wrote: >>>>> >>>>> But what you suggest is quite workable... >>>>> >>>>> I think if I were interested in ultimate efficiency, I might go >>>>> with Jeff's "chained blocks" with a >>>>> comfortably large chosen page size. (But efficiency really isn't an >>>>> issue for this task!) >>>>> >>>> The tape is unbounded. And even some very simple machines will fill >>>> it up to infinity. >>>> If you stop the machine when the process runs out of memory, which >>>> is a reasonable >>>> strategy, you don't want O(N) tape write operations. >>>> >>>> Chained blocks are probably the best model. They don't scale up, so >>>> a machine that was written >>>> for a 16K ZX81 might struggle when ported to a 16GB typical modern >>>> desktop. If you know >>>> the approximate szie of your tape, however, then blocks are a good >>>> solution. >>>> >>> I don't get why you say a chained block approach doesn't scale up. >>> Such a design works well until >>> the logical (user) address space is filled, which is absolutely huge >>> on a modern 64-bit machine with >>> page files etc.. When the tape gets very large, only a small portion >>> of it needs to be in the >>> working set for the process to avoid paging. >>> >>> The only design I can think of that might scale up better would be >>> one using an output device larger >>> than the logical address space limit. Maybe you were just saying that >>> a hard-coded small block size >>> (for a ZX81?) is not as efficient as big blocks if you've got lots of >>> memory? I don't see that you >>> would use a chained block approach on such a tiny machine! Perhaps >>> you meant to say the design >>> doesn't scale /down/ rather than up? (And the size of chained blocks >>> can be dynamically decided at >>> run time if we like.) >>> >>> Other designs, e.g. using vector or strings will involve copying ever >>> larger blocks of memory around >>> when the vector/string is extended, so perhaps you meant to say that >>> /those/ designs don't scale up, >>> but the chained blocks scale up? >>> >> I was thinking that the chained block degenerates into effectively a >> linked list when block size becomes >> small in relation to tape length. However that isn't really a problem >> - it still works more effectively >> than a contiguous model. > > Right. And by allocating these blocks in multiples of the page (least > common multiple of swap page and cache page size), you'll keep the > caches full of the right stuff. The time overhead is that you must check > if the +1 or -1 positioning to see if you are at a block boundary for > each increment; the storage penalty is that you must keep both a forward > and backward link pointer on each page. This approach can be adapted to > really, really long tapes (>> terabyte) and will be no uglier then other > approaches. > > My (not so hidden) assumption are that nobody is really thinking of > dealing with such really, really long tapes, i.e., this whole project is > viewed more as a pedagogical exercise. A second assumption is that the > thing to optimize is cache hits given secondary assumptions that modern > user-level computers have wide and fewer cache "words" so you want > something that almost guarantees that you will "pound" each cache word > many times and that your program including your part of the memory > management will all stay in the cache. > > What is really amazing to me is that Ben got such greater throughput > with what he described as a very casual approach! So maybe all of our > talk is rather premature until someone wants to do BB for new state size > bounds. I am basically making a std::deque based on std::vector that has all of the speed and space efficiency of std::vector and the functionality of std::deque. This provides the basis for a two-way TM tape. -- Copyright 2022 Pete Olcott "Talent hits a target no one else can hit; Genius hits a target no one else can see." Arthur Schopenhauer
[toc] | [prev] | [next] | [standalone]
Page 4 of 10 — ← Prev page 1 2 3 [4] 5 6 … 10 Next page →
Back to top | Article view | comp.theory
csiph-web