Talk:Post–Turing machine

2158:(afaik). First, I assume that by "2 actions per instruction" you mean the first action is either a "write", "shift", or "test", and the second action is a transfer of control (implicitly or explicitly) to the instruction to be executed next. Second, the instruction-types for Wang's machine W are "write 1", "write 0", "shift left", "shift right", and "if 1 then goto k") -- the conditional "if 0 then goto k" and the unconditional "goto k" are both optional -- so all of these instructions agree with your "2-actions per instruction" description, except for the unconditional goto (only a nit, because it's entirely optional, replaceable by a pair of conditional gotos). Third, in all Wang programs Stop exists only implicitly, as the effect of any attempted transfer to an instruction number that's not in the program. Lastly, I would consider it an inessential variation to use instruction numbers/labels (as Davis might do?) only for instructions actually referenced by some explicit goto -- under the natural assumption that the instructions are otherwise written in the sequence intended. --r.e.s. ( 915:

Jb, 4, Jb, 1) on the tape when writing a "example", even if there's a speed trade-off. The "good" thing about the "go to next instruction in sequence" is that the "next instruction in sequence" can be handled by a "hardware counter" and not waste tape (and time). The bad thing about it is it may cause longer instruction sequences, ultimately? Or perhaps another measure might be: what encoding gives the "simplest P-T machine" in "gate-count" (probably the canonical state machine version). Or, if the tape is considered a shift register each square of which has a certain "gate count" what would be the "cheapest" instruction set and machine. Just a wonderment. This reminds me of an (old) Scientific American article where a culture builds a a "computer" wandering the universe, where time is no problem but low energy use and reliability/complexity, and maybe size is, how would someone build it.

1314:

alternating the cells used for i/o with those used as "working cells", much as Turing did. Standard unary is used for the representation of numbers. Wang presents first a Turing-complete formulation using only four instruction-types equivalent to {"write 1", "shift right", "shift left", "if 1 goto k"} -- with the alternating-cell i/o convention -- and then discusses various alternative instruction-sets, e.g. involving the equivalents of "write 0", "if 0 then goto k", "(unconditonal) goto", etc., pointing out that the auxilliary cells are not needed when "write 0" is added to the set. (He states that it's an "open question" whether the auxilliary cells can be dispensed with in the non-erasing case.) BTW, it's probably worth noting also that Wang actually presented this "1957 paper" at an ACM meeting in 1954! --r.e.s. (

1130:

never to be erased, and were to form "a continuous sequence" with "no blanks until the end"), and "E-squares" (whose contents were erasable, for "rough notes to assist the memory" using "a sufficiently rich variety of symbols"). In particular, the S.D. symbols were to appear on the tape in F-squares, and the universal machine U could print any of the symbols A, C, D, 0, 1, u, v, w, x, y, z, and colon ':' (with u, v, w, x, y, z being used as erasable "markers" in E-squares). Thus, the universal machine emulates any computing machine M whose S.D. it finds on the tape in F-squares, by printing (in other F-squares) the encodings of M's successive complete configurations -- including the same subsequence of "figures" (0's and 1's) that M would print -- and using the E-squares as an auxilliary workspace.

2257:

worst screamy nightmare. RE Post-Turing machines I truly have a 'gate-equivalent' model in my head -- I could draw it in NAND gates etc in short order. And my model requires a bunch of "gates" to decode every address of every possible "next instruction" (i.e a RAM with column and row address decoders). The ironic part is I could draw this stuff easier than trying to describe it. But anyway... I do understand/respect the need for abstract modelling, truly ... and I do agree with you that we should present all the variant-models... (I need to read Wang again but if he lives up to my expectations he's "da man", now seeing that Davis in '58 did not have a Post-Turing model or references to Wang (probably a student, then), see below in boldface). wvbailey

737:

mind clear). And encoding instructions in unary with extra "marks" (for example, or blanks) that U erases (or prints) temporarily... but since we can't post original work...... unless you know of some printed stuff we can reference (and I avoid web-pages because they're not peer-reviewed)... we are restricted to published accounts of how others designed U-machines in "P-T" blank-mark code. Do you know of any? I.e. paper-published U-code in "blank-mark" sentences for a "P-T machine?" (I pretty sure I saw it years ago for a true Turing-machine i.e. a 5-tuple, I think in "Hennie". I found the reference in an old notebook of mine, that he used 0's (blanks) in unary). wvbailey

229:

1983:113). On 23 September 1936, Turing sailed from the UK to Princeton (he was on a grant); here he met Church et. al.. He got his proofs sometime in the fall (October, November) for review (cf Hodges pages 116-123). Simultaneously, on October 7 1936, Church received Emil Post's paper (Post was teaching at the City College of NY) "Finite Combinatory Processes, Formulation I" i.e. 5 months after Turing's and the same time Turing got his proofs to check. In order to publish Post's paper, Church "had to certify that the work had been complettely independent" (Hodges 1983:125). This is what he wrote as a footnote to Post's paper:

982:

unconditional "jump" plus a single conditional jump. Even the decision to use a "canonical state machine" or a "jammable up-counter" as the "instruction memory" leads to different constructions. (I built three of these variants in Excel.) Maybe this discussion here might be of use to someone-- students, say-- since it's 'off line' and we're "revealing" more. I used some of this in an effort to find a way for a microcontroller to quasi-"self-test" itself (creating "random numbers" was better, but I did discover an interesting trick from the P-T machine). This stuff may have some theoretical use we can't envision.wvbailey

1558:. If the machine is meant to stop with only one (or two, it won't matter) nonblank cells, but the input may have arbitrarily many nonblank cells, then the machine either must erase some cells or it cannot compute this function. That is why the article needs to describe the nonstandard input/output convention that Wang is using. The closest thing to a standard contemporary understanding of a Turing machine is that it represents numbers in unary, or binary (or unary plus an end marker, if you prefer) and halts at the end of a successful computation. Wang's model, apparently, does not follow these conventions. 112: 1916:-instructions with the exceptional test+branch as a specific type of instruction, yielding the following 7 instructions executed sequentially { R, L, E, P, Jb,xxx, Jm,xxx, H } . This is how I built my little model out of CMOS stuff -- I used a jammable/loadable up-counter as the "state register" aka "program counter". However, more recently I have found that when simulating a Post model on a spreadsheet, the state-machine version (each instruction followed by test+branch) is much easier to "build". 102: 81: 1719:

much simplifies "the design" of the "Turing machine" -- the Teleype just reverses its motion to locate its required "square" and punches another hole in the tape. (So what if the tape is 186,000 miles long? And a calculation takes 14.7 years to complete?) While you and I might argue "Who the hell cares about this?" (obviously Wang and Minsky did and we care enough to spend time writing about it)-- we can never know what future mind might be sparked by such an amazing proof.wvbailey

1786:, North-Holland Publishing Company first edition 1952, I think you will be startled, as I was. I suggest that this is the source of all of the Post-Turing models to follow. I was put onto this source by Martin Davis himself. (While he admits that he coined the phrase "halting problem" he attributes the proofs to Kleene in this book and ultimately to Turing's 2nd proof. After some consideration I have to agree with him.) Seriously, see if you can get a cc and peruse Chapter XIII 2447:, instruction table) for the Turing-machine is drawn per engineering convention (states down the left side, the various inputs drawn across the top) (cf Peterson, McClusky (1965), etc). This diverges from some (early ?) mathematics conventions e.g. Mirsky (1968)) where the tables are rotated so the symbols are down the left and the next state is across the top. Note that the spreadsheet version of the Post-Turing table is somewhat like this non-engineering convention. 456:

question is why I even got involved in Knowledge, just to answer: Why is Turing's proof so different from the "halting" proofs. The origin of "halting problem"(probably) wasn't Turing, but who was it? How did it happen? Ideas? The Talk:"History" and the footnotes on the "Halting Problem" page should illuminate the issue. Also, the confusions between "Hilbert's Problems" of 1900 versus his 1928 recasting of "1900 Hilbert #2" as "1928 3 Hilbert Questions" ...wvbailey

2984: 1713:"OVERPRINT" as virtually-impossible to implement with real mechanical objects (disappearing ink is one possibility, some kind of rubby-eraser-wheel is another). There are many ways of doing this if we were to move something -- e.g. a ball, a slide switch -- back and forth in a sequence of trays-as-tape but this is not in Turing's spirit of erasable, over-printable symbols on paper tape.wvbailey 3607: 50: 2191:

proposing? All my designs (i.e. using variant (ii)) built with CMOS or as a spreadsheet model have required explicit labels for every instruction. "Central control aka instruction table aka RAM" has to hunt down "the next instruction's" label with a match to the number in the state register -- usually by a parallel "match"). Lemme know what you are proposing. wvbailey

21: 2308:, Hennie doesn't even mention "Halting problem" (I forgot to check him re Wang. Minsky (1967) does give Hao Wang 5 citations in his index, PLUS our Wang (1957) as a source). Hennie delivers a very nice piece re the universal Turing machine, p. 90-103 -- examples and flowchart, but no actual code. I've only seen the entire Turing code one place-- Roger Penrose, 2436:

the "0" case and three for the "1" case, for a total of 1+2x3 instructions per B-B state. Thus we expect ~21 (3 x 7) total instructions in the 3-state B-B. But the final HALT requires one less, for a total of 20 P-T instructions. If we have to use only conditional jumps the unconditional jump ends up two jumps (for example: J,15 = J0,15 followed by J1,15).

3614: 1883:"Indeed it can be argued that the Turing machine act is already compound, and consists psychologically in a printing and a change in state of mind, followed by a motion and another change of mind. Post 1947 does thus separate the Turing act into two; we have not here, primarily because it saves space in the machine tables not to do so." 1866:

quintuplets of form (q, s, s',d',q'), Kleene's have entries (s',d',q') for each (q,s) as (row,col) -- essentially the same thing. Although the transition table can (with modern eyes) be viewed as a kind of "program", istm that the model is not a "program formulation" in nearly the same sense as those of Post and Wang. (IMO, it's hard

1425:

I-as-computer detect this condition visually. But it is simple to build a "detector". Also, we typically do this in microcontroller-based designs; at the end of a sequence of calculations we put the microcontroller into a tight loop and enable a timing interrupt; we let the interrupt "kick the dog" out of its "tight circle".wvbailey

686:

would be preferrable to restrict examples to formulation-1 variants rather than referring to Turing's universal machine and how it was coded. (I suspect that few, other than the two of us, have much interest in Turing's original model, considering that it's been "debugged" and superceded by now-standard reformulations as in the

3296: 2042:

in the spirit of Post's model is the winner. As the name was given by Davis and used by him at least once in the literature, by all rights his should be the "penultimate" model whatever it is. I could ask him what his intent was, but his answer would be unpublished and unvarifiable and yada yada yada.

2129:

model is a seven-instruction, 2-actions-per-instruction, sequentially- numbered instructions that proceed in sequence until a branch occurs. If I'm wrong about your conception of this model lemme know. I'll research the Davis monograph again (a rare find in the library so I need to go there, if i can

2124:

Oh the irony, we've already done the deed. When you google Post-Turing machine , what do you come up with? We've already defined the phrase, albeit ambiguously, for all academics for all time . If I'm not mistaken anyone who writes a dictionary finds current usage of words and eventually defines them

2062:

My concern is -- when someone talks about a Post-Turing machine what are they talking about? One of three possible models P-T #1, #2, or #3? I would like to see one model emerge only because then the words 'Post-Turing machine' becomes unambiguous. So what if we agree to define it a certain way? That

2048:

Presumably, by "P-T model" you mean the ones called that by Davis. The one with numbered instructions is apparently taken from Wang (1954/7), and the other appears to be a trivial adaptation to labelled (rather than numbered) instructions. Is there any earlier Davis publication of such a model? If

2041:

RE original research: The P-T model is significant because it is more "atomic" than the Turing model, includes HALT, and as a bonus, is (sometimes) represented as a sequence of Von Neumann-like series of numbered instructions. My criterion of choice is: the farthest away from Turing's model but still

1991:

and closely related program formulations that can be seen as derived from it. Kleene's model doesn't belong in the article, imo, because it is very much closer to what is considered the "modern" formulation of Turing machines. (In my opinion, it's the "program formulation" aspect of the models that

1602:

computation. But rather, a "bad jump" -- due to a "programming error" or "noise" or "unfortunate input" or "bad luck" or "busted machine" -- may send the machine to the HALT prematurely (best to use only one HALT in a "program") before the machine can output its calculation (number). This happens in

1455:

Sorry if the comment seemed cryptic -- I've edited (and hopefully clarified) this part of the article. Wang machines halt iff there is an attempt to transfer control to an instruction number that's not in the program. (This happens in only two ways: upon executing a goto that attempts to branch to a

1181:

Instructions were to be preceded by "D" followed by a unary-string of A's (i.e. instruction #4 is "q4" and coded as "D" followed by four A's: D A A A A). Characters to be printed (by commanding the universal machine U, only indirectly by the machine on the tape) were to be preceded by "D" followed by

736:

From your familiarity with this stuff, I'm presuming you've written the U-code for a P-T machine so you're familiar with encoding "0" and "1" as e.g. blank-mark and mark-blank, and then leaving a third square in between as a place for pointers... or whatever (some unambiguous coding so U can keep its

482:

such a problem (irrespective of questioning its decidability), it may impossible to discover that. But I think it's important to realise that Church's λ-calculus, and also combinatory logic (going back to the 1920's), both involve the idea of reducing a term to "normal form" in finitely-many steps --

253:

I know of no evidence that Church and Post knew one another personally -- we'd have to find biographies of both men -- but Post cited Church's 1935 "Unsolvable Problem of Elementary Number Theory" in his 1936 paper. Church was presumably aware of Post's 1921 PhD thesis -- a quite important paper that

2382:

What I did, to be thorough, was turn the "3-state busy beaver" into a set of seven Post-Turing instructions with a sort of rote/unthinking "algorithm" that always ends with unconditional jumps (the conditional jump comes at the beginning, as it does in Turing's model). On the article page I broached

2282:

Tidbits re Library Sleuthing: while I was in the library I looked into Davis's books (all 3 in series one after the other on the shelf -- 'the shelf' is really short, just a few recursion-theory types"). The first book was his lectures at the Courant Institute that define Post-Turing "programs", the

2180:

I think we agree, but i need some clarification re goto's. I have used both pairs of goto's, i.e. { "If 'mark' goto xxx", "goto xxx" } and the other pair { "If 'mark' goto xxx", "If blank goto xxx" } and as you note this choice is a nit. Re your point about instruction labels, I'm a bit confused and

2027:

The term "program formulation" is Wang's, who called this model a "program formulation of Turing machines". It seems likely that some later authors also recast TMs in terms of programs largely due (indirectly) to Wang's original example. But ISTM that the present article is best confined to program

1923:

assert sequential instruction execution? I say we hunt this down and nail it -- i.e. are there quotes to back up this assertion? It is an interesting one and I agree with you that in its ultimate form the P-T model represents a primitive programming language. (Davis does assert sequential operation,

1911:

Rather than quibble, what we might take away from the discussion and infuse into the article (we have plenty of verifiable backup in the quotes above from Kleene) is the strong distinction between TMs and P-T's -- (i) the addition of HALT/STOP, (ii) the further atomization of instructions beyond the

1029:

The educational thing was the source of my original interest in this, so many years ago: to identify a cheap, challenging "teaching computer"-like thing. But I did discover that it was basically "too" challenging. Only the simplest programs were do-able by the average mortal. (The multiplier program

3540:

Additional Post-Turing instructions 15 through 20 erase the symbols created by the busy beaver. These are more "efficient" -- to accomplish the same task a Post-Turing machine will (usually) require fewer Post-Turing states than a Turing-machine simply-converted with 7 equivalent Post-Turing states

2435:

This is just a test of a macro that converts Excel spreadsheet tables into wiki-tables. It worked! The passage from Turing- to Post-Turing machine is a simple, primitive conversion -- each state of the B-B (Turing instruction) gets converted into an initial conditional jump then 3 instructions for

2256:

I have to agree with you. But you have to forgive my mind -- always swoopsing down toward "implementing" -- as in, how would I build the sucker. I'm an engineer, so I'm an ultra-constructivist: a "If we can't build it out of slimey goo then it doesn't exist" kind of guy, an abstract mathematician's

1718:

The idea that a Turing-equivalent machine could exist identical to a Teletype excepting the "Wang-Turing-Teletype" is able to reverse direction of the tape -- I do believe I've seen such reversing tape on some early computers (I know magnetic-tape machines do this)-- is (to me) fascinating. It very

1666:

which cause the machine to terminate with an output in the proper form (so an incorrectly formed output merely means the function is not defined for that input). This is why the input/output conventions are important - because they are integral to the definition of a computable function. There is

887:

So really there are only three fundamental instructions "move tape", "print symbol on tape", and "Jump", and they each have two variants (interesting symmetry): L/R, P/E, Jb/Jm. And if every "move" and "print" is a 3-tuple , can we dispense with jump? ... no we need to add a "no move" . Interesting

772:

I did "scan" Wang's paper but as I remember it is still in the Turing tradition of "5-tuples" or "4-tuples" Let's see... the P-T machine is both 2-tuples ("tape action:L,R,E,P" ,"next-instruction" ) and what? 3-tuples for the conditional jumps? let's see ("tape-symbol", if-symbol then-go-to-qi, if

347:

If it's a real trauma we could add a cross to "Turing-Equivalent models" but some folks know this as much by Post's work as by Turing's. This entry isn't just for mathematicians. I think the operative word is "encyclopedia". I would prefer all the models lumped into one place. If this becomes a big

1964:

This is good news. I believe we could rework the article to compress it into a single "computer-like" model that includes stop, sequential instruction execution, two "operations" per "machine cycle", and the use of a single symbol plus blank on a two way tape. Thoughts? Do you have a cc of Wang in

1712:

My reason is this: I've been trying to draw a "Turing machine" as "a mechanical contrivance" with a paper tape and an indexing "tractor wheel" similar to the old-fashioned paper-tape Teletype, or a 35mm film with its square indexing holes. But again and again I run into the problem of: "ERASE" and

1690:

include "write 0". I suggest that the main article simply omit any mention of the tangential fact that Turing completeness is possible with smaller instruction-sets, in view of the distraction this seems to have caused. It should be apparent that the six-instruction set is sufficent to simulate

1424:

There is a tricky way of doing this -- at the end of the calculation purposefully send the machine into a "tight circle" as in "xxx: unconditional jump to this instruction xxx" and use a 2nd machine (e.g. me-as-computer) to detect this condition. This is what I've done with my home-built machines;

1242:

I don't remember writing this section (couldn't have, it's too well-written). I don't have a cc of Wang, I had to find it in the Dartmouth library. I skimmed it just hunting for his model -- another correspondent had actually pointed me to Wang's model-- at the time I was hunting for the source of

1129:

Turing also used unary-like encoding as part of a machine's "Standard Description" (S.D.), which was a string using the symbols A, C, D, L, R, N, and semicolon ';'. A convention was adopted according to which the squares of the tape alternated between two types -- "F-squares" (whose contents were

941:

Interesting. I looked at the Böhm link... he used a counter in his while loops? Sounds a bit like the stuff that Minsky described in his text. At one point I added a counter to my P-T machine, with three new commands: Up (increment), Down (decrement), and Jump-if-zero. This significantly shortened

914:

I guess my wondering is: what is the "most atomized" of all the instruction sets (given such a question has meaning at all)? One measure might be: not counting the use of unary code, what encoding would give the fewest instructions (where the go-to instruction counts as "double" P, L, Jb, 1, E, R,

851:

is assumed, and Post's single "if ... then ... else" has been "atomised" into two "if ... then ..." statements. Davis and the others followed Wang in this, as far as I know. In any case, this is so close to Post that it seems quite appropriate to regard these as "Post-Turing" programs. (Btw, the

1888:

I believe what you are saying immediately above is what I observed in Kleene's statement -- that the Post-model machine (2 "operations" per line of the state table) more "atomizes" the actions of the machine than the Turing model (3 "operations" per line of the table). Clearly this distinction is

1761:

I'm not sure I could quibble with you about this; I will need to re-read the Wang model again (don't have a cc as noted above); besides Davis is more widely published than Wang. But see my observation immediately below about Kleene. All these guys (Post, Kleene, Wang, Davis, Minsky, even Chaitin)

867:

Sounds like we should put Wang on the page and ... what, remove Beltrami? (he didn't contribute anything in the historical sense, he's just another example, ditto for Penrose). In fact I'm just going to do it, copy your words into the article. Remove Beltrami and add Wang. Do you know if Wang and

685:

By "OT" I meant "off-topic" -- the topic being, as I understand it, very simple variants of Post's "formulation 1" model. To illustrate how data can be encoded in these models (which are not even "computing machines" by Turing's definition, because their alphabets are strictly binary), I think it

209:

Gurevich is not a slouch, so maybe he has his "facts" (understanding) wrong? The only way Post could have seen Turing's paper, would have been that Alonzo Church showed a cc of Turing's unpublished paper to Post, or someone else sneaked him a copy, and then Post lied about it. But what would Post

2367:

Question: below, instruction 7 is an unconditional jump to instruction 8, similarily, instruction 21 is an unconditional jump to 22. A jump to the next instruction seems unnecessary, as that is part of the definition, no? or, is such a jump considered a no-op instruction, but then why do we need

2337:

My first thought is that since any binary-tape TM in standard 5-tuple form is so very easy to rewrite as a P-T machine (just by translating each state's pair of 5-tuples into appropriately numbered instructions), any of the UTMs of that kind in the literature could be treated this way. E.g., one

2007:

I disagree with your concern about "program formulation". Your (implied) definition of "program" as a numbered sequential set of machine-commands is suspect/debatable and incorrect per certain authors. For example, the fancier TI DSPs that can execute more than one instruction in an "instruction

228:

in Princeton NJ. Meanwhile, over in the UK, via his professor, Turing submitted his paper (really his Master's thesis) on 31 May 1936 to the London Mathematical Society (Hodges 1983:112). Church was the only one who could referee the paper and so the LMS sent the paper to him for comment (Hodges

505:

Interesting, thanks. I'll look at the Church paper(s) and see where the word "terminate" is, and reference it too. As to the different forms of "the Halting Proof" (as distinct from Turing's circle-proof), about as far back as I've been able to go without a trip to the library is Minsky in 1967

2105:

As I understand it, you've credited Davis with the term "Post-Turing machine"; so your concern about what the term means is surely unfounded. "When someone talks about a Post-Turing machine", surely they must mean one of those machines popularised by Davis under that name. In an encyclopedia

2978:

of the Turing-machine equivalent of the 3-state busy beaver drawn with the Post-Turing states inside it. The state action {e.g. P for print) is drawn inside the state, and per engineering convention (McClusky, Peterson) and the state number (or identification) is drawn inside each Post-Turing

1865:

Unlike Post's model (and Wang's), Kleene's machines, by design, have the basic structure of Turing's machines -- with the "logic" embodied in a state transisition table virtually identical to Turing's (though with an explicit "halting state"). Whereas Turing's transition tables were lists of

455:

You would not believe the fight I've had re this topic of HALT/STOP versus Turing's "circles". (See the dialog on page "Halting Problem" under Talk:"History" or whatever...). This "dialog" with various persons has been going on for weeks. Also: the origin of the phrase "halting problem"? This

2190:

as in "having a fixed label". I've always done (ii) in my work because of the issue of how to indicate a "negative" offset (i.e. jump back -3 instructions); plus a third type of jump seems to be required: (if 'mark' jump_forward xxx, if 'mark' jump_back xxx, goto xxx }. Which variant are you

2185:

to the current instruction -- when confronted with a successful test the "central control" then has to "count back" or "count forward" (or use an adder plus the state register) the offset as prescribed by the number in the goto instruction (similar to the "branch" instruction in the Motorola

981:

I totally agree with the leeway issue. It is amazing: some people like me have coded with "marks" to "keep the tally", others code with "blanks" to tally, some poor people who have never actually built one try to use binary code, I suppose you can but what a nightmare. I experimented with an

1313:

The section in question was written by me ("r.e.s."), and (as noted) is not in error about the "write 0" instruction being unnecessary for Turing completeness. Wang's "program formulation" of TM's doesn't use "non-standard" i/o conventions, except (in the "nonerasing" case) in the sense of

602:

RE changes to the opening paragraph: Davis really did refer to these as "Post-Turing machines", and the programs as "Post-Turing programs." And a humorous thing: poor Davis in "What is a Computation?" slipped and in one place referred to a "Post-Turing program" (p. 256) instead of his usage

2079:(1936), Wang presented a very similar but simpler "program formulation of Turing machines" (1954/7), and Davis popularised variants of Wang's model, calling them "Post-Turing machines" (197?). If that's the historical progression, I see no problem with the article discussing it that way. 1418:

There is also a cryptic comment about Wang's machine not halting; there are instances where it is useful to have machines that don't halt, but lack of halting also means that the conventions I just specified can't hold, because the machine can never signal that its output is prepared.

2063:

isn't original research. If Wang's model is in fact "the compressed version aka penultimate model" and we agree -- and especially if it coincides with Davis's named model -- then that's the model I suggest we use. We keep the others for historical, evolutionary interest. wvbailey

1603:(badly-designed) microcontroller work all the time and is a very bad thing (injures/kills people, destroys property)-- I never use a HALT (STOP) in my work, but rather the watch-dog scheme that I described above. There's a whole science around watchdog timers and their use). 1842:

I stand corrected on the issue of whether Kleene's model required other than a strictly binary tape alphabet. After first defining "computability" in such a way that the tape alphabet was not strictly binary, he proceeds to define "1/1 computability" in such a way that it

1091:"Since we wish to be able to include numerical data as part of our input we shall want to have a way of describing ordinary numbers (by which I here mean the natural numbers 0, 1, 2, 3, 4, ...) as part of the input. One way to do this might be simply to use a string of n 603:"Turing-Post program" elsewhere in his paper. I was surprised to find the earlier Davis stuff myself, especially in something so obscure as the document I found it in (it looked like a mimeograph... but so be it...): Anyway, it's in the printed literature... it's not "me". 1380:

I start the machine with the input 11 (unary for 2) and all other cells blank. If the machine is unable to change one of those 1s to a blank, the machine cannot end up with a tape that just says 1. Therefore, Wang's model does not work with the conventions I just

1982:

Of course this isn't the place to post original work, which is what your suggested compressed "single 'computer-like' model" sounds like to me. As I see it, there are essentially only two types of computational model under discussion -- those that are essentially

1299:

In a follow-up he comments that this machine wipes out all records of its computations by converting all symbols to C's. A machine that keeps a record is also possible. I haven't read the proof; it looks straight-forward but tricky. Lemme know if you need more

1706:

I'll offer another idea (per an earlier CMummert suggestion): In the spirit of simplifying main articles, create another article -- maybe call it "Wang machine" -- as yet another example of "Turing equivalent" machines. (Cyber-paper is cheap, no minds will be

1824:

You are correct re "... others may be used in the computation";, however in his example of using | and blank that extends throughout the chapter (p. 356-386) he uses only | and blank; no other symbol appears on his tape excepting on p. 381 he let a 2 leak

1879:

wvbailey here: Kleene is explicit: "Our treatment here is closer in some respects to Post 1936. Post 1936 considered computation with a 2-way infinite tape and only 1 symbol" (p. 261 first paragraph). Then on page 379 he makes the following observation:

2376:

You are absolutely correct to question this. Because the P-T model can go sequentially, sometimes an unconditional jump is just a waste of an instruction (hence a nop). But this points out why the Post-Turing model is different from the Turing-machine

2424:

This would also have the benefit of being able to include multiple initial states (sounds like a contradiction, I know) in a P-T "program" that would cause it to behave differently depending on what state is jumped to first. Quite interesting, indeed.

942:

the universal-machine code and really speeded the machine up. The conditional jumps UP-ed the counter to "store" the jump-to address; then U moved left to the beginning of the code and then moved to the right "DOWN-ing" the counter at each instruction.

1231:

cannot be computed. I have not looked at Wang's actual writing; does anyone have easy access to it? I am sure that the issue is that Wang has some nonstandard input/output convention, just as Turing's original paper did. This needs to be clarified.

1641:

By successful computation, I merely meant terminating computation. It is indeed possible for a particular machine to be misprogrammed to that it halts but leaves illegal output. This is not a problem, though; it is handled by the definition of

477:

I see no reason to doubt that Turing's was the first proof of an undecidable problem of the "halting problem" type. (Church's undecidability proof for a problem in the λ-calculus was earlier, but wasn't of this type.) As for who might have first

953:

No counters are involved in in Böhm's "(...)" construct. It's a simple while-loop; i.e., with alphabet {0,1}, "(...)" means "while the scanned value is 1 do ... end_while", and as usual the test is performed at the beginning of each prospective

1740:

explicit use of a "stop" instruction matters little in this regard.) Although it's possible that this model may also have a place in some other article with a different topical emphasis, I'm wary of your "cyber paper is cheap" approach. BTW,

1992:

provides the main justification for not merging the article into the one on Turing machines.) About access to the Wang paper (and others) ... Like you, I rely on a university library, and have only hard-copy of selected sections. --r.e.s. (

1123:"coding", Beltrami uses "binary code" for the instructions, e.g. "write 0" has the code 000, "write 1" has the code 001, etc. Unlike the Penrose model, Beltrami uses a string of 0's to designate a jump-to address rather than a string of 1's. 2706:. This number can be reduced (by 3 or 4) to generate a more efficient machine, but we are using the simplest possible Turing- to Post-Turing conversion-convention of 7 Post-Turing instructions/states per 1 Turing-instruction/state. 595:

the "Footnote|Davis". I'm sure I'll catch mega-shit for those changes too, but I was digging deep, looking at the real stuff in the Math-department collection in the Dartmouth libarary. "Halting Problem"? Looks like Davis coined that

1965:

pdf form? I made a special trip to the library (for this and for Markov on the algorithm page) but they were all f***d up and could not get the paper from their electronic archives (grrr -- did find markov though :-) . wvbailey

967:(instead of two) interleaved sequences of bits, and used strictly unary coding throughout. I mention this to emphasise the possibly-surprising leeway that binary machines have in their organisation and use of memory.--r.e.s. ( 1396:

Usually "0" i.e. empty set { } is written in unary as |, a single mark. "1" i.e. successor to "0" is written as ||, "2" i.e. successor to "1" written as ||| -- three markes. As far as I know, no one attempts to render "0" as

680:

You expanded the entry more than what I'd intended. I was just after an example of "unary coding". And the alternate squares idea-- where you place pointers. Makes you wonder about a link to a new "universal machine" page.

576:

In any event, Turing and others were still referring to his circle-free/circular version of the problem in the late 1940s, so I suspect it was in the 1950s when the "modern" version took root -- maybe it's in Wang's paper?

375:

Not necessarily "universal"... But the three quoted: are extremely similar, just variances on the 6-to-7 instructions in the "set" plus {0,1} or {blank,mark} only on the tape . The Turing-version exists as counter-point.

1243:

the phrase "halting problem" (wasn't Wang). ... ahh... I do remember that Minsky (or someone) has a proof that there exists a Turing-equivalent machine that never erases. Yes indeed here it is, it is old Minsky himself:

3107:

Instructions for the Post-Turing version of a 2-state busy beaver, followed by a "run" of the P-T equivalent. As shown in this drawing neither the "Erase" nor the "Jump if tape-symbol is 0" are used by the busy beaver:

1762:

knew each other (I believe all overlapped at the Courant Institute at NYU at one time or another, either as students or professors) so I'm not surprised their models are similar. What I meant in my suggestion is to

1456:

nonexistent instruction number, or immediately after execution of the last instruction in the program.) Please see below for my reply re i/o conventions, which are entirely standard in Wang's "machine W". --r.e.s. (

1030:

is pretty neat, about the limit I would say). Since then I have used P-T's as challenges to myself when confronted with a "new language" e.g. to build one in C, in Excel, in assembly language, whatever... wvbailey

423:

He explains in the paper that he included the nonhalting version just for symbolic logics as a matter of taste, preferring to start with finitely many axioms encoded in the boxes, then to generate and encode all

1149:, and instead prints all the terms in succession. Thus the S.D. encodes no input for the machine to be emulated by the universal machine, whereas the S.D. alone is the essential input to the universal machine. 1076:, p. 30ff., explicitly describes the use of "unary coding" (Penrose, p. 41) although he is not the first to use this convention. (Unary encoding is found in Section 10 of Turing's 1936-1937 paper, in which the 704:

I wouldn't object if you cut it down/out and moved the reminants to the talk-page so it is back-ground reference. I guess I am still struggling with the question of what the article is "really about". wvbailey

276:

This is why I always check the talk pages; Knowledge would be a lot weaker without this this sort of information, information that would never be allowed within the rigid structure of the main page. ThankYou!

2094:

model appeared in "popular" literature (i.e. a non-specialist form) is in 1980 . Therein lies the source of difficulty, in my mind. Davis wrote another book re mid '50's that I need to look at too. wvbailey

2222:

already in the article. The "implementation" issues you mention seem to me of no concern, since we're talking about abstract theoretical models of computation. IMO, the primary focus should instead be

2125:

per the consensual/accepted usage-- wiki is a dictionary as well. (I'll look at some of the usages and see what they specify). I don't call that original research. I believe that you and I agree -- that

2383:

this with an example of a "tape-erasing" subroutine at the end of the busy beaver. I hope this explanation helps. If not, lemme know. You have pointed out a possible source of confusion, thanks.wvbailey

2283:

third was "Undecidable" (I have a personal cc, is a keeper). But the second was his 1958 "Computability and Unsolvability". Here on p. 70 appears the first known expression of "the halting problem".

2012:"An algorithm for the Turing machine consists of a set of five-tuples such that there is exactly one five-tuple for each state-symbol pair, excluding the HALT state. Such an algorithm is known as a 210:

have gained by it? When you read the historical facts (the time sequence), this makes no sense at all. So we apply Occam's Razor and stick with the simplest explanation: their work was independent.

1934:

In both the Post and Wang model, the instructions are numbered by consecutive positive integers, and by "sequential execution" I mean that instruction i+1 is executed next after instruction i:

3014:

State table for a 2-state Turing-machine busy beaver. The "Print" instruction writes a 1, the "Erase" instruction writes a 0. The tape moves "Left" or "Right" (i.e. the "head" is stationary).

278: 2304:

Davis does deliver a good full version of a Turing-machine multiply "program" (and a few others) using only mark, blank and a couple other symbols. With respect to Fredrick C. Hennie (1977)

168: 248:

Post's paper appeared in print in late 1936 (exact date?). Turing's paper appeared a bit later, in the London Mathematical Society's Proceedings, ser. 2, vol. 42 (1936-37) in January 1937.

1686:: It's only when the instruction-set omits the "write 0" that your "standard" i/o conventions are not used. In the main article "Wang's model" refers to his larger instruction-set that 1116:

system. Then the symbol '0' could be used as a space to separate different numbers from one another. It is important that we have such a means of separating numbers..." (Penrose, p. 41)

1662:) on the tape and then halts with the head at the left edge of the answer. Conversely, any Turing machine computes a unique partial function. The domain of the function is the set of 1250:! In fact, we will construct a two-symbol machine Tn that can only change blank squares on its tape to 1's but can not change a 1 back to a blank." (his italics; Minsky 1967, p.262-266) 31: 1948:

In a Wang program, execution is sequential -- except obviously when branching occurs due to a conditional "goto" instruction. The relevant material to quote is on pp64-65. --r.e.s. (

3301:

The following is a two-state Turing busy beaver with additional instructions 15-20 to demonstrate the use of "Erase", J0, etc. These will erase the 1's written by the busy beaver:

3606: 2410:

Also, to be complete, we could add an unconditional jump at the very beginning and therefore remove the requirement that the initial T-state be the first block in the P-T model.

3541:

per Turing state; a go-to (jump) can occur to any "sub-state" (e.g. P, E, L, R )within the Turing-state, a grouping of move-instructions such as L, L, L, P are possible, etc.:

1126:

The use of unary "encoding" in the creation of instructions for the universal machine also appears in Hennie. But the Hennie Model is otherwise similar to the Turing Model.

1521: 1356: 1229: 2049:

not, an encyclopedia article should give credit where due -- imo, it would be described as Wang's model as popularised by Davis, or something along those lines. --r.e.s. (

1375:

The output must be a natural number in unary, all other cells must be blank when the machine halts, and the machine must halt with the head at the left edge of the number.

1987:(Post, Wang, ...) and those that are not (Turing, Kleene, ...). There is some overlap, but to me there's enough of a distinction to keep the article focussed on Post's 1556: 1152:

For example: The following string is the code for the four instructions that would print on the tape 0 1 0 1 ... ad infinitum to the right (Turing's example p. 127 in

1372:

The input is a natural number in unary (with no gaps), all other squares being blank and the head being placed at the left edge of the number when the machine starts.

311:

I'm aware of it. As I worked on the compromise model it became a concern. Your point is well-taken. I think I'll cut because it really isn't worth the fight. wvbailey

2312:, page 56-57. Never seen a version using Post-Turing code (I've done it, but pathetically it's "OR"). Have you seen a published Post-Turing U-machine code? wvbailey 751:

whose input alphabet is binary, with strictly unary input-encoding (but it uses two additional auxilliary symbols "internally", making an alphabet of four symbols):

784:

Wang (1957), with credit to Post, is often cited as the source of the "program formulation" of binary-tape Turing machines using numbered instructions from the set

3613: 1480:

Turing's original paper, about computing real numbers, also uses nonstandard i/o conventions. Perhaps this is why it was thought that Wang's model does not.

1164:

The instructions that form the string are shown below. Here “qn” stands for “instruction #n”, “Si”stands for “symbol #i”, S0 is "blank", S1 = “0”, S2 = “1”:

390:(BTW, one unmentioned major difference between those two is that Post insisted on computations that halt, whereas Turing's computations were required to be 3693: 158: 2989:

Some figures don't work so good unless they are blown up; double click on image to see better, then select high-resolution when the picture comes up:

899:

I'm not sure what you mean, but of course the "jump" (conditional branching) instructions, or their equivalents, are necessary for Turing equivalence.

326:

On the title we disagree. I've seen the usage on the 'net. Davis used a the words "Turing-Post program". And I've cross-referenced the hell out of it.

1575:

I'd have to go away and think about whether or not the "k = 1" can be successfully programmed with a "Wang machine". With the trick described above (

2399:

Yes, I hadn't thought of that. But its true. A finite state machine's states need not be ordered. Only the initial state must be specified.wvbailey

1900:

Kleene's model was surely an important influence in bringing about the modern formulation of TMs and of TM computations that terminate. --r.e.s. (

1259:

For any Turing machine T there is an equivalent two-symbol machine which can only print 1's on blank squares but can never erase a 1, once printed

747:

I've not seen a complete program for a universal (binary) P-T machine, although I do have a published reference describing in detail a universal

644:

I have the work open before me. but there is something special about these quivalents: the simplicity. It isn't just another equivalent. wvbailey

2186:

microcontrollers such as the MC68HC05) -- thus how to indicate a "negative" offset becomes an interesting problem (offset binary?), or (ii) as

1246:"We can now demonstrate the remarkable fact, first shown by Wang , that for any Turing machine T there is an equivalent Turing machine Tn that 134: 3688: 2993: 1941:, every instruction ("direction") contains the number of the instruction to be executed next (except of course for Stop) -- and this may be 1847:

strictly binary ("1/1" referring to 1-way infinite tape, 1 symbol other than the blank). My apologies -- the confusion was mine. --r.e.s. (

2396:

I understand. Using this (simple) algorithm has the nice effect of allowing to order the originial T-states in any order in the P-T model.

1804:, especially the "Computable Functions" chapter, did indeed impress me (I read it about a year ago) -- as can be seen in my edits to the 1182:

a unary-string of C's (specifically "blank" is D, "0" is D C, "1" is D C C. Other symbols, if required, could be defined in this manner.

3633:

In the picture 'Algorithm_P-T_multiply_2.JPG', there's a 'P' missing where it 'repairs' the blank marker in 'b' after incrementing 'c'.

1767: 852:

universal Wang program I mentioned above uses the obvious extension of this instruction-set to tapes with a more-than-binary alphabet.)

282: 3295: 125: 86: 1667:

no notion of a machine computing the wrong function; if you want a different computable function, you choose a different machine.

765:

Probably it would be fairly straighforward to eliminate the two auxilliary symbols in a relatively minor recoding of the program.

2212:

I'm sorry if I wasn't clear: I wasn't proposing any new variant, which is why I tried to emphasise instead the idea of merely

2983: 1732:

Actually, I think Wang's model belongs in the present article even more than do those of Davis, since the Davis models came

511:

I think it might pay to look at Hao Wang's paper that presented a "program formulation" of TMs, evidently based on Post's

254:

first formalized the "truth table" method and dealt a significant blow to Russell's "theory of types" that he needed for

1270:= 000, A = 100, B = 100, C=110. He shows that any machine T can have an equivalent T'n with the following restrictions: 963:

To solve the data-coding problem in that case, I generalised Turing's idea of alternating types of squares so as to use

440:

on computations that halt, but rather that he made it a point to emphasise that they're sufficient for his formulation.)

61: 2285:

But nowhere does Davis mention Post-Turing or Turing-Post (machines or programs) and Hao Wang doesn't appear anywhere

2028:

formulations that are very close to Post and Wang (and Davis, who apparently adopted/adapted Wang's model). --r.e.s. (

1598:

I was out for a walk and the thought occurred: that a Turing machine at its HALT may not be stopping at the end of a

1616:

My point is that HALT cannot be trusted as an indicator of a successful computation. The question then becomes: how

2130:

get Wang on pdf I'll do that too and send you a cc) and see if Davis 1974 indeed is explicit about the above model.

1808:

article. But a couple of observations may be in order about Kleene's model in the context of the present article:

1133:

Note: In Turing's formulation, a "computing machine" -- unlike his universal machine -- is assumed to begin with a

934:

programming language (which is an equivalent to Post's formulation-1, using while-loops instead conditional gotos).

868:

Davis were on the same faculty? Somehow I think they were, or Davis was younger than Wang, maybe a student.wvbailey

322:

of a composite of published models. (This is not the same as describing a published composite as per its source.)

1782:

Actually Stephen C. Kleene (1952) beat both Wang by a year or so and Davis by a mile. If you can find a cc of his

1790:

pp. 356 ff. Observe his model in particular ("Suppose the symbol S1 is actually a tally mark '|'", etc.) wvbailey

27: 1745:

is Wang's name for the model we're discussing ("machine B" is what he called the nonerasing version). --r.e.s. (

408:

Post provided his STOP for numerical computations but not logical, where it wouldn't be used (I'm not sure why).

756:"J. W. Thatcher, Sef-describing Turing machines and self-reproducing cellular automata", in A. W. Burks (ed.), 491:". (This wasn't presented as a decidability problem, but merely a part of his development of λ-definability.)-- 240:. The present article, however, although bearing a later date, was written entirely independently of Turing's. 1819:

uses a binary alphabet, but other auxilliary tape symbols are allowed in the course of a computation. (p.360)

888:

question: what is the minimum number of total "-tuple-entries". It looks like 8 + 3 + 3 = 14. Is this true?

599:

Problem is: if a reviewer can't come back with rebutting documentation, their word is... less than useless.

3648:

Found the file (2006!), corrected the image, uploaded corrected issue. Let's hope this is successful. Bill

1062: 67: 3638: 2232: 1057:(see below for an example of his coding). Later writers have, for the most part, used a combination of 194:

that Post saw Turing's article before doing his work. Is there more evidence going one way or another?

111: 1007:

challenging (and more than just a little bit educational, if my experience is any measure). --r.e.s. (

1095:

s to represent the number n (although this could give us a difficulty with the natural number zero):

1058: 49: 20: 2106:

article, it's not for us to come up with anything else (such as a "compressed version"). --r.e.s. (

1668: 1559: 1481: 1233: 380: 3634: 1205:

instruction, for otherwise the numbers of 1s on the tape can never decrease and thus the function

1065:

coding for their "Post-like" instructions that will be put on the tape of a universal machine (cf

133:

on Knowledge. If you would like to participate, please visit the project page, where you can join

3669: 3653: 2227:" (or important predecessors so close to them as to deserve mention), and perhaps to give a nice 263: 117: 1650:

on the natural numbers is computable if there is a Turing machine that, whenever given an input

1500: 1335: 1208: 101: 80: 1120: 2444: 2339: 2159: 2107: 2050: 2029: 1993: 1949: 1901: 1848: 1746: 1696: 1457: 1315: 1160:;D A D D C R D A A ; D A A D D R D A A A ; D A A A D D C C R D A A A A ; D A A A A D D R D A 1053:

In his original paper Post did not discuss a "universal machine"; this was the invention of

1008: 968: 722: 691: 663: 659: 582: 578: 496: 492: 399: 395: 219:(a compilation of the republished papers), and Andrew Hodges' 1983 biography of Alan Turing: 1526: 258:(cf van Heijenoort 1967:264ff). So we can presume that these two men knew one another. Bill 1805: 592: 199: 3673: 3657: 3642: 3623: 3004: 2417: 2403: 2387: 2343: 2316: 2261: 2235: 2195: 2163: 2134: 2111: 2067: 2054: 2033: 1997: 1969: 1953: 1928: 1905: 1893: 1852: 1829: 1794: 1774: 1750: 1723: 1700: 1671: 1583: 1562: 1484: 1461: 1429: 1401: 1365: 1319: 1304: 1236: 1034: 1012: 986: 972: 872: 741: 726: 708: 695: 667: 648: 607: 586: 500: 460: 403: 356: 286: 267: 203: 1066: 687: 3682: 3665: 3649: 3620: 3001: 2975: 2414: 2400: 2384: 2313: 2258: 2192: 2131: 2064: 1966: 1925: 1890: 1826: 1791: 1771: 1720: 1580: 1426: 1398: 1362: 1301: 1031: 983: 927: 869: 738: 705: 645: 604: 457: 353: 312: 259: 190:

The article claims that the work of Post is independent of that of Turing. However,

2992: 931: 3664:

A day later and the file is still not the latest, corrected (current) image. Bill

2703: 2571: 2440: 1266:

The proof requires 3 pages. He starts by creating a machine T'n using 4 symbols

1054: 748: 232:

Received October 7, 1936. The reader should compare an article by A. M. Turing,

130: 215:

Here are the written facts, as known by me, derived from the Martin Davis 1965

2426: 2369: 2231:

of these -- but definitely not to describe yet another variant of our own. --

195: 191: 107: 2225:

what are the models that are known in the literature as "Post-Turing machines

2181:

need your clarification.... We can either (i) fashion the goto's so they are

930:

did lead me to code and implement a universal machine in a binary variant of

428:

derivable from them. But he points out that this is not necessary, since an

2152:

Subject to a few minor provisos, I think that's a fair summary of the model

1112:

This primitive numbering system is referred to (rather illogically) as the

1080:

value in a sequence is represented by "the number of figures 1 between the

300: 1358:

using the following input/output convention, which I believe is standard:

1912:

Turing model, (iii) possibly -- and I am uncertain here-- the notion of

1201:

With the normal input/output conventions, it's not possible to omit the

542:

Wang, Hao (1957): "A variant to Turing's theory of computing machines",

2570:

This convention for the state table follows the convention used on the

1945:

instruction in the program -- so execution is not generally sequential.

1919:

With regards to this last (iii), in your opinion does Wang and/or Post

318:

In my opinion, too much original work is occurring in this article as

1620:

we know that our machine's "product" (output number, computation) is

591:

It wasn't Wang's paper. I looked it up and scanned it; for more, See

432:

can be included with the axioms at the start, then stopping when the

2702:

The 22 instructions that make up the Post-Turing equivalent 3-state

1764:

create a new page about "the Wang model without erasure (Print 0)".

654:

But the two are different enough that a composite will just be yet

372:? If so, "Turing-equivalent models" would definitely be too broad. 637:, in which the similarity to Turing's can be briefly mentioned. 43: 15: 1695:

Kleene), using only the standard i/o conventions. --r.e.s. (

483:

so of course Church's 1936 paper discusses reductions that "

379:

I don't think you would be considering them if they weren't

1579:= 000, A = 100, B = 100, C=110) my guess is it can.wvbailey 3028: 3021: 2595: 2588: 2581: 2466: 2464: 2461: 2459: 2457: 2454: 2018:

Introduction to Computer Organization and Data Structures

1736:

Wang's and essentially duplicated it. (IMO, the implicit

999:

Writing one's own code for a universal machine in almost

544:

Journal of the Association for Computing Machinery (JACM)

3019: 2579: 2452: 1145:

term of the sequence, a "circle-free" computing machine

1766:

If you don't I may just do it myself; i.e. extend the

1529: 1503: 1338: 1211: 2338:

published by Rogozhin has only 24 states. --r.e.s. (

1811:

Unlike Post's model (and Wang's), Kleene's machines

1361:

Just curious: what is "lambda x.1?" Thanks, wvbailey

629:

I agree that it would be good to have an article on

436:

theorem is produced. (So I should not have said he

129:, a collaborative effort to improve the coverage of 1174:

Inst{ q3 S0 S2 R q4 } = D A A A D D C C R D A A A A

1550: 1515: 1350: 1223: 1069:for more details about "the universal machine"). 2016:: (italics in original, p. 9 in Harold S. Stone, 1654:in the proper form, produces the proper form for 760:, U. Illinois Press, Urbana, 1970; pp. 103-131. 1137:tape. Thus, rather than taking an input (say 301:http://en.wikipedia.org/Wikipedia:Five_pillars 238:Proceedings of the London Mathematical Society 1691:any Turing machine in the modern sense (e.g. 1003:of these primitive languages is likely to be 8: 3585: 3565: 3545: 3488: 3435: 3370: 3305: 3253: 3212: 3162: 3112: 3081: 3058: 3054: 3051: 3048: 3045: 3042: 3039: 2910: 2852: 2781: 2710: 2666: 2634: 2630: 2627: 2624: 2621: 2618: 2615: 2612: 2609: 2606: 2542: 2517: 2492: 2469: 364:Isn't the article supposed to be limited to 224:In 1936 Alonzo Church started a new journal 3037: 2604: 1177:Inst{ q4 S0 S0 R q1 } = D A A A A D D R D A 1171:Inst{ q2 S0 S0 R q3 } = D A A D D R D A A A 366:universal computational models of a design 3033: 3031: 3026: 3024: 2600: 2598: 2593: 2591: 2586: 2584: 295:Knowledge is not for posting original work 75: 1528: 1502: 1337: 1210: 1168:Inst{ q1 S0 S1 R q2 } = D A D D C R D A A 3546: 3543: 3303: 3110: 3016: 2996:3-state Busy Beaver run on a P-T machine 2991: 2708: 2576: 2449: 1332:Suppose I want a machine that computes 77: 47: 3306: 3113: 2711: 2090:1974. The second model that he called 1924:in some of his later writing).wvbailey 1889:fundamental to the Post model.wvbailey 2008:cycle". Or the following definition: 1813:do not use a strictly binary alphabet 279:2001:470:1F09:10D6:F21F:AFFF:FE54:B8C 7: 828:if scanning 1 then goto instruction 820:if scanning 0 then goto instruction 773:not-symbol-then-next-instruction ) . 348:issue we might have to arbitrate it. 123:This article is within the scope of 1768:Knowledge:Be bold in updating pages 1248:never changes a once-written symbol 66:It is of interest to the following 1874:as an early programming language.) 1088:+1) figure 0"). To quote Penrose: 320:the author's creation (and naming) 14: 3694:Low-priority mathematics articles 2358:Use a Busy Beaver as P-T example? 2020:, McGraw-Hill Book Company, 1972) 1141:) and halting after printing the 143:Knowledge:WikiProject Mathematics 30:on 27 August 2020. The result of 3612: 3605: 3294: 2982: 1047:Coding for the universal machine 146:Template:WikiProject Mathematics 110: 100: 79: 48: 19: 1802:Introduction to Metamathematics 1784:Introduction to Metamathematics 1255:He offers us a Theorem 14.5-1: 573:There's a brief description at 303:, "all editors must follow our 163:This article has been rated as 26:This article was nominated for 1539: 1533: 1523:denotes the constant function 268:18:30, 10 September 2010 (UTC) 204:17:18, 10 September 2010 (UTC) 1: 2306:Introduction to Computability 2216:those extremely similar model 287:08:25, 13 November 2014 (UTC) 226:The Journal of Symbolic Logic 137:and see a list of open tasks. 3689:B-Class mathematics articles 1035:17:48, 27 January 2006 (UTC) 1013:23:52, 26 January 2006 (UTC) 987:17:03, 26 January 2006 (UTC) 973:01:05, 26 January 2006 (UTC) 873:17:13, 27 January 2006 (UTC) 742:16:52, 25 January 2006 (UTC) 727:03:21, 3 February 2006 (UTC) 721:Done -- see below.--r.e.s. ( 709:17:03, 26 January 2006 (UTC) 696:01:05, 26 January 2006 (UTC) 668:20:58, 12 January 2006 (UTC) 649:21:36, 12 January 2006 (UTC) 608:00:25, 18 January 2006 (UTC) 587:20:03, 13 January 2006 (UTC) 501:09:16, 13 January 2006 (UTC) 461:02:06, 13 January 2006 (UTC) 404:00:36, 13 January 2006 (UTC) 357:21:36, 12 January 2006 (UTC) 3586: 3566: 2543: 2518: 2493: 2470: 2418:21:41, 17 August 2006 (UTC) 2404:21:41, 17 August 2006 (UTC) 2388:20:54, 15 August 2006 (UTC) 1646:, namely, a total function 1516:{\displaystyle \lambda x.1} 1351:{\displaystyle \lambda x.1} 1224:{\displaystyle \lambda x.1} 758:Essays on cellular automata 658:Turing-equivalent model. -- 370:to those of Post and Turing 186:Post independent of Turing? 3710: 3624:14:05, 2 August 2006 (UTC) 3561: 3558: 3555: 3552: 3549: 3366: 3363: 3360: 3357: 3354: 3351: 3348: 3345: 3342: 3339: 3336: 3333: 3330: 3327: 3324: 3321: 3318: 3315: 3312: 3309: 3158: 3155: 3152: 3149: 3146: 3143: 3140: 3137: 3134: 3131: 3128: 3125: 3122: 3119: 3116: 3005:20:39, 2 August 2006 (UTC) 2777: 2774: 2771: 2768: 2765: 2762: 2759: 2756: 2753: 2750: 2747: 2744: 2741: 2738: 2735: 2732: 2729: 2726: 2723: 2720: 2717: 2714: 1770:to creating them. wvbailey 236:, shortly forthcoming the 3674:14:03, 9 April 2013 (UTC) 3658:15:22, 8 April 2013 (UTC) 3643:10:07, 8 April 2013 (UTC) 3489: 3436: 3371: 3254: 3213: 3163: 3082: 3059: 2911: 2853: 2782: 2667: 2635: 2344:08:49, 30 July 2006 (UTC) 2317:03:40, 30 July 2006 (UTC) 2262:03:40, 30 July 2006 (UTC) 2236:00:57, 30 July 2006 (UTC) 2196:14:50, 29 July 2006 (UTC) 2164:00:03, 29 July 2006 (UTC) 2135:15:14, 28 July 2006 (UTC) 2112:02:49, 28 July 2006 (UTC) 2068:22:40, 27 July 2006 (UTC) 2055:02:49, 28 July 2006 (UTC) 2034:02:49, 28 July 2006 (UTC) 1998:01:03, 27 July 2006 (UTC) 1970:22:01, 26 July 2006 (UTC) 1954:20:57, 26 July 2006 (UTC) 1929:15:24, 26 July 2006 (UTC) 1906:04:53, 26 July 2006 (UTC) 1894:15:29, 26 July 2006 (UTC) 1853:21:44, 26 July 2006 (UTC) 1830:15:24, 26 July 2006 (UTC) 1795:23:27, 25 July 2006 (UTC) 1775:23:53, 25 July 2006 (UTC) 1751:21:11, 25 July 2006 (UTC) 1724:19:59, 25 July 2006 (UTC) 1701:18:42, 25 July 2006 (UTC) 1672:17:34, 25 July 2006 (UTC) 1584:17:00, 25 July 2006 (UTC) 1563:15:56, 25 July 2006 (UTC) 1485:11:27, 25 July 2006 (UTC) 1462:23:58, 29 July 2006 (UTC) 1430:15:22, 25 July 2006 (UTC) 1402:15:22, 25 July 2006 (UTC) 1366:15:22, 25 July 2006 (UTC) 1320:05:43, 25 July 2006 (UTC) 1305:03:35, 25 July 2006 (UTC) 1237:02:42, 25 July 2006 (UTC) 673:Universal machine entries 162: 95: 74: 426:infinitely many theorems 169:project's priority scale 633:model, which he called 126:WikiProject Mathematics 2997: 2310:The Emporer's New Mind 2014:Turing machine program 1552: 1551:{\displaystyle f(x)=1} 1517: 1352: 1225: 1074:The Emporer's New Mind 56:This article is rated 2995: 2979:state/instruction). 2462:If tape symbol is 1: 1624:or even "completed"? 1553: 1518: 1353: 1226: 1119:In the creation of a 1072:Penrose, in his book 256:Principia Mathematica 234:On computable numbers 3490:Turing-state label: 3255:Turing-state label: 2912:Turing-state label: 2712:Instruction number: 1985:program formulations 1788:Computable Functions 1527: 1501: 1336: 1209: 849:sequential execution 690:article.) --r.e.s. ( 485:must (if continued) 305:no original research 192:Yuri Gurevich claims 149:mathematics articles 3010:2-state Busy Beaver 2363:3-state Busy Beaver 2075:Post presented his 1707:harmed...).wvbailey 1644:computable function 341:Post-Turing program 338:Post-Turing Machine 335:Turing-Post program 329:Turing-Post Machine 3083:tape symbol is 1: 3060:tape symbol is 0: 2998: 2668:tape symbol is 1: 2636:tape symbol is 0: 2455:tape symbol is 0: 1548: 1513: 1453:Reply to CMummert: 1348: 1221: 1186:Wang model; error 1105:| | | |, 5 -: --> 677:What's "OT" mean? 489:in the normal form 118:Mathematics portal 62:content assessment 3603: 3602: 3537: 3536: 3292: 3291: 3105: 3104: 3029:Current state B: 3022:Current state A: 2972: 2971: 2854:Jump-to number : 2699: 2698: 2596:Current state C: 2589:Current state B: 2582:Current state A: 2568: 2567: 1121:universal machine 368:extremely similar 344:Post-Turing model 332:Turing-Post model 183: 182: 179: 178: 175: 174: 42: 41: 3701: 3616: 3609: 3544: 3304: 3298: 3111: 3017: 2986: 2709: 2577: 2450: 2445:transition table 1626: 1625: 1557: 1555: 1554: 1549: 1522: 1520: 1519: 1514: 1397:"blank".wvbailey 1357: 1355: 1354: 1349: 1230: 1228: 1227: 1222: 1198: 1197: 1193: 1106:| | | | |, etc. 1104:| | |, 4 -: --> 508: 507: 151: 150: 147: 144: 141: 120: 115: 114: 104: 97: 96: 91: 83: 76: 59: 53: 52: 44: 23: 16: 3709: 3708: 3704: 3703: 3702: 3700: 3699: 3698: 3679: 3678: 3631: 3547:Instruction #: 3307:Instruction #: 3114:Instruction #: 3012: 2471:Current state: 2365: 2360: 1806:Halting Problem 1525: 1524: 1499: 1498: 1334: 1333: 1207: 1206: 1199: 1195: 1191: 1189: 1188: 1154:The Undecidable 1049: 926:My interest in 675: 593:Halting Problem 297: 217:The Undecidable 188: 148: 145: 142: 139: 138: 116: 109: 89: 60:on Knowledge's 57: 12: 11: 5: 3707: 3705: 3697: 3696: 3691: 3681: 3680: 3677: 3676: 3661: 3660: 3630: 3627: 3601: 3600: 3598: 3595: 3593: 3591: 3588: 3584: 3583: 3580: 3577: 3574: 3571: 3568: 3564: 3563: 3560: 3557: 3554: 3551: 3548: 3539: 3535: 3534: 3532: 3530: 3528: 3526: 3524: 3521: 3519: 3517: 3515: 3513: 3511: 3509: 3506: 3504: 3502: 3500: 3498: 3496: 3494: 3491: 3487: 3486: 3484: 3481: 3479: 3477: 3474: 3472: 3469: 3467: 3465: 3462: 3460: 3458: 3455: 3452: 3450: 3448: 3445: 3443: 3441: 3438: 3434: 3433: 3430: 3427: 3424: 3421: 3418: 3415: 3412: 3409: 3406: 3403: 3400: 3397: 3394: 3391: 3388: 3385: 3382: 3379: 3376: 3373: 3369: 3368: 3365: 3362: 3359: 3356: 3353: 3350: 3347: 3344: 3341: 3338: 3335: 3332: 3329: 3326: 3323: 3320: 3317: 3314: 3311: 3308: 3290: 3289: 3286: 3284: 3282: 3280: 3278: 3276: 3274: 3271: 3269: 3267: 3265: 3263: 3261: 3259: 3256: 3252: 3251: 3249: 3246: 3244: 3242: 3239: 3237: 3235: 3232: 3229: 3227: 3225: 3222: 3220: 3218: 3215: 3211: 3210: 3207: 3204: 3201: 3198: 3195: 3192: 3189: 3186: 3183: 3180: 3177: 3174: 3171: 3168: 3165: 3161: 3160: 3157: 3154: 3151: 3148: 3145: 3142: 3139: 3136: 3133: 3130: 3127: 3124: 3121: 3118: 3115: 3103: 3102: 3099: 3096: 3093: 3090: 3087: 3084: 3080: 3079: 3076: 3073: 3070: 3067: 3064: 3061: 3057: 3056: 3053: 3050: 3049:Write symbol: 3047: 3044: 3041: 3040:Write symbol: 3038: 3035: 3034: 3032: 3030: 3027: 3025: 3023: 3020: 3011: 3008: 2970: 2969: 2964: 2962: 2960: 2958: 2956: 2954: 2952: 2947: 2945: 2943: 2941: 2939: 2937: 2935: 2930: 2928: 2926: 2924: 2922: 2920: 2918: 2913: 2909: 2908: 2906: 2903: 2901: 2899: 2896: 2894: 2892: 2889: 2886: 2884: 2882: 2879: 2877: 2875: 2872: 2869: 2867: 2865: 2862: 2860: 2858: 2855: 2851: 2850: 2847: 2844: 2841: 2838: 2835: 2832: 2829: 2826: 2823: 2820: 2817: 2814: 2811: 2808: 2805: 2802: 2799: 2796: 2793: 2790: 2787: 2784: 2780: 2779: 2776: 2773: 2770: 2767: 2764: 2761: 2758: 2755: 2752: 2749: 2746: 2743: 2740: 2737: 2734: 2731: 2728: 2725: 2722: 2719: 2716: 2713: 2701: 2697: 2696: 2693: 2690: 2687: 2684: 2681: 2678: 2675: 2672: 2669: 2665: 2664: 2661: 2658: 2655: 2652: 2649: 2646: 2643: 2640: 2637: 2633: 2632: 2629: 2626: 2625:Write symbol: 2623: 2620: 2617: 2616:Write symbol: 2614: 2611: 2608: 2607:Write symbol: 2605: 2602: 2601: 2599: 2597: 2594: 2592: 2590: 2587: 2585: 2583: 2580: 2566: 2565: 2562: 2559: 2556: 2553: 2550: 2547: 2541: 2540: 2537: 2534: 2531: 2528: 2525: 2522: 2516: 2515: 2512: 2509: 2506: 2503: 2500: 2497: 2491: 2490: 2487: 2484: 2483:Write symbol: 2481: 2478: 2475: 2474:Write symbol: 2472: 2468: 2467: 2465: 2463: 2460: 2458: 2456: 2453: 2433: 2432: 2431: 2430: 2422: 2421: 2420: 2408: 2407: 2406: 2391: 2390: 2379: 2378: 2364: 2361: 2359: 2356: 2355: 2354: 2353: 2352: 2351: 2350: 2349: 2348: 2347: 2346: 2326: 2325: 2324: 2323: 2322: 2321: 2320: 2319: 2295: 2294: 2293: 2292: 2291: 2290: 2289: 2288: 2273: 2272: 2271: 2270: 2269: 2268: 2267: 2266: 2265: 2264: 2245: 2244: 2243: 2242: 2241: 2240: 2239: 2238: 2203: 2202: 2201: 2200: 2199: 2198: 2173: 2172: 2171: 2170: 2169: 2168: 2167: 2166: 2143: 2142: 2141: 2140: 2139: 2138: 2117: 2116: 2115: 2114: 2100: 2099: 2098: 2097: 2096: 2095: 2083: 2082: 2081: 2080: 2060: 2059: 2058: 2057: 2039: 2038: 2037: 2036: 2022: 2021: 2005: 2004: 2003: 2002: 2001: 2000: 1975: 1974: 1973: 1972: 1959: 1958: 1957: 1956: 1946: 1909: 1908: 1898: 1897: 1896: 1886: 1885: 1884: 1876: 1875: 1870:to see Post's 1860: 1859: 1858: 1857: 1856: 1855: 1835: 1834: 1833: 1832: 1821: 1820: 1780: 1779: 1778: 1777: 1756: 1755: 1754: 1753: 1727: 1726: 1715: 1714: 1709: 1708: 1681: 1680: 1679: 1678: 1677: 1676: 1675: 1674: 1632: 1631: 1630: 1629: 1628: 1627: 1609: 1608: 1607: 1606: 1605: 1604: 1591: 1590: 1589: 1588: 1587: 1586: 1568: 1567: 1566: 1565: 1547: 1544: 1541: 1538: 1535: 1532: 1512: 1509: 1506: 1492: 1491: 1490: 1489: 1488: 1487: 1473: 1472: 1471: 1470: 1469: 1468: 1467: 1466: 1465: 1464: 1441: 1440: 1439: 1438: 1437: 1436: 1435: 1434: 1433: 1432: 1411: 1410: 1409: 1408: 1407: 1406: 1405: 1404: 1387: 1386: 1385: 1384: 1383: 1382: 1378: 1377: 1376: 1373: 1369: 1368: 1347: 1344: 1341: 1325: 1324: 1323: 1322: 1308: 1307: 1297: 1296: 1295: 1294: 1293: 1264: 1263: 1262: 1253: 1252: 1251: 1220: 1217: 1214: 1187: 1184: 1179: 1178: 1175: 1172: 1169: 1162: 1161: 1110: 1109: 1108: 1107: 1103:| |, 3 -: --> 1067:Turing machine 1048: 1045: 1044: 1043: 1042: 1041: 1040: 1039: 1038: 1037: 1020: 1019: 1018: 1017: 1016: 1015: 992: 991: 990: 989: 976: 975: 960: 959: 958: 957: 956: 955: 946: 945: 944: 943: 936: 935: 928:Turing tarpits 923: 922: 921: 920: 919: 918: 917: 916: 905: 904: 903: 902: 901: 900: 892: 891: 890: 889: 882: 881: 880: 879: 878: 877: 876: 875: 858: 857: 856: 855: 854: 853: 840: 839: 838: 837: 836: 835: 834: 833: 825: 817: 812: 807: 802: 790: 789: 788: 787: 786: 785: 777: 776: 775: 774: 767: 766: 762: 761: 753: 752: 734: 733: 732: 731: 730: 729: 714: 713: 712: 711: 699: 698: 688:Turing machine 674: 671: 652: 651: 641: 640: 639: 638: 624: 623: 622: 621: 620: 619: 618: 617: 616: 615: 614: 613: 612: 611: 600: 597: 574: 560: 559: 558: 557: 556: 555: 554: 553: 552: 551: 550: 549: 547: 529: 528: 527: 526: 525: 524: 523: 522: 521: 520: 519: 518: 516: 468: 467: 466: 465: 464: 463: 448: 447: 446: 445: 444: 443: 442: 441: 414: 413: 412: 411: 410: 409: 388: 387: 386: 385: 384: 350: 349: 345: 342: 339: 336: 333: 330: 327: 316: 315: 296: 293: 292: 291: 290: 289: 271: 270: 250: 249: 246: 245: 244: 221: 220: 212: 211: 187: 184: 181: 180: 177: 176: 173: 172: 161: 155: 154: 152: 135:the discussion 122: 121: 105: 93: 92: 84: 72: 71: 65: 54: 40: 39: 32:the discussion 24: 13: 10: 9: 6: 4: 3: 2: 3706: 3695: 3692: 3690: 3687: 3686: 3684: 3675: 3671: 3667: 3663: 3662: 3659: 3655: 3651: 3647: 3646: 3645: 3644: 3640: 3636: 3629:Drawing error 3628: 3626: 3625: 3622: 3617: 3615: 3610: 3608: 3599: 3596: 3594: 3592: 3589: 3581: 3578: 3575: 3572: 3569: 3567:Instruction: 3542: 3533: 3531: 3529: 3527: 3525: 3522: 3520: 3518: 3516: 3514: 3512: 3510: 3507: 3505: 3503: 3501: 3499: 3497: 3495: 3492: 3485: 3482: 3480: 3478: 3475: 3473: 3470: 3468: 3466: 3463: 3461: 3459: 3456: 3453: 3451: 3449: 3446: 3444: 3442: 3439: 3431: 3428: 3425: 3422: 3419: 3416: 3413: 3410: 3407: 3404: 3401: 3398: 3395: 3392: 3389: 3386: 3383: 3380: 3377: 3374: 3372:Instruction: 3302: 3299: 3297: 3287: 3285: 3283: 3281: 3279: 3277: 3275: 3272: 3270: 3268: 3266: 3264: 3262: 3260: 3257: 3250: 3247: 3245: 3243: 3240: 3238: 3236: 3233: 3230: 3228: 3226: 3223: 3221: 3219: 3216: 3208: 3205: 3202: 3199: 3196: 3193: 3190: 3187: 3184: 3181: 3178: 3175: 3172: 3169: 3166: 3164:Instruction: 3109: 3100: 3097: 3094: 3091: 3088: 3085: 3077: 3074: 3071: 3068: 3065: 3062: 3036: 3018: 3015: 3009: 3007: 3006: 3003: 2994: 2990: 2987: 2985: 2980: 2977: 2976:state diagram 2968: 2965: 2963: 2961: 2959: 2957: 2955: 2953: 2951: 2948: 2946: 2944: 2942: 2940: 2938: 2936: 2934: 2931: 2929: 2927: 2925: 2923: 2921: 2919: 2917: 2914: 2907: 2904: 2902: 2900: 2897: 2895: 2893: 2890: 2887: 2885: 2883: 2880: 2878: 2876: 2873: 2870: 2868: 2866: 2863: 2861: 2859: 2856: 2848: 2845: 2842: 2839: 2836: 2833: 2830: 2827: 2824: 2821: 2818: 2815: 2812: 2809: 2806: 2803: 2800: 2797: 2794: 2791: 2788: 2785: 2783:Instruction: 2707: 2705: 2694: 2691: 2688: 2685: 2682: 2679: 2676: 2673: 2670: 2662: 2659: 2656: 2653: 2650: 2647: 2644: 2641: 2638: 2603: 2578: 2575: 2573: 2563: 2560: 2557: 2554: 2551: 2548: 2546: 2538: 2535: 2532: 2529: 2526: 2523: 2521: 2513: 2510: 2507: 2504: 2501: 2498: 2496: 2488: 2485: 2482: 2479: 2476: 2473: 2451: 2448: 2446: 2442: 2437: 2428: 2423: 2419: 2416: 2413:True.wvbailey 2412: 2411: 2409: 2405: 2402: 2398: 2397: 2395: 2394: 2393: 2392: 2389: 2386: 2381: 2380: 2375: 2374: 2373: 2372:Aug 15, 2006 2371: 2362: 2357: 2345: 2341: 2336: 2335: 2334: 2333: 2332: 2331: 2330: 2329: 2328: 2327: 2318: 2315: 2311: 2307: 2303: 2302: 2301: 2300: 2299: 2298: 2297: 2296: 2286: 2281: 2280: 2279: 2278: 2277: 2276: 2275: 2274: 2263: 2260: 2255: 2254: 2253: 2252: 2251: 2250: 2249: 2248: 2247: 2246: 2237: 2234: 2230: 2226: 2221: 2220: 2215: 2211: 2210: 2209: 2208: 2207: 2206: 2205: 2204: 2197: 2194: 2189: 2184: 2179: 2178: 2177: 2176: 2175: 2174: 2165: 2161: 2157: 2156: 2151: 2150: 2149: 2148: 2147: 2146: 2145: 2144: 2136: 2133: 2128: 2123: 2122: 2121: 2120: 2119: 2118: 2113: 2109: 2104: 2103: 2102: 2101: 2093: 2089: 2088: 2087: 2086: 2085: 2084: 2078: 2077:Formulation 1 2074: 2073: 2072: 2071: 2070: 2069: 2066: 2056: 2052: 2047: 2046: 2045: 2044: 2043: 2035: 2031: 2026: 2025: 2024: 2023: 2019: 2015: 2011: 2010: 2009: 1999: 1995: 1990: 1989:Formulation 1 1986: 1981: 1980: 1979: 1978: 1977: 1976: 1971: 1968: 1963: 1962: 1961: 1960: 1955: 1951: 1947: 1944: 1940: 1939:Formulation 1 1936: 1935: 1933: 1932: 1931: 1930: 1927: 1922: 1917: 1915: 1907: 1903: 1899: 1895: 1892: 1887: 1882: 1881: 1878: 1877: 1873: 1872:Formulation 1 1869: 1864: 1863: 1862: 1861: 1854: 1850: 1846: 1841: 1840: 1839: 1838: 1837: 1836: 1831: 1828: 1823: 1822: 1818: 1814: 1810: 1809: 1807: 1803: 1799: 1798: 1797: 1796: 1793: 1789: 1785: 1776: 1773: 1769: 1765: 1760: 1759: 1758: 1757: 1752: 1748: 1744: 1739: 1735: 1731: 1730: 1729: 1728: 1725: 1722: 1717: 1716: 1711: 1710: 1705: 1704: 1703: 1702: 1698: 1694: 1689: 1685: 1673: 1670: 1665: 1661: 1657: 1653: 1649: 1645: 1640: 1639: 1638: 1637: 1636: 1635: 1634: 1633: 1623: 1619: 1615: 1614: 1613: 1612: 1611: 1610: 1601: 1597: 1596: 1595: 1594: 1593: 1592: 1585: 1582: 1578: 1574: 1573: 1572: 1571: 1570: 1569: 1564: 1561: 1545: 1542: 1536: 1530: 1510: 1507: 1504: 1497:The notation 1496: 1495: 1494: 1493: 1486: 1483: 1479: 1478: 1477: 1476: 1475: 1474: 1463: 1459: 1454: 1451: 1450: 1449: 1448: 1447: 1446: 1445: 1444: 1443: 1442: 1431: 1428: 1423: 1422: 1421: 1420: 1417: 1416: 1415: 1414: 1413: 1412: 1403: 1400: 1395: 1394: 1393: 1392: 1391: 1390: 1389: 1388: 1379: 1374: 1371: 1370: 1367: 1364: 1360: 1359: 1345: 1342: 1339: 1331: 1330: 1329: 1328: 1327: 1326: 1321: 1317: 1312: 1311: 1310: 1309: 1306: 1303: 1300:info.wvbailey 1298: 1287: 1282: 1277: 1274: 1273: 1272: 1271: 1269: 1265: 1260: 1257: 1256: 1254: 1249: 1245: 1244: 1241: 1240: 1239: 1238: 1235: 1218: 1215: 1212: 1204: 1194: 1185: 1183: 1176: 1173: 1170: 1167: 1166: 1165: 1159: 1158: 1157: 1155: 1150: 1148: 1144: 1140: 1136: 1131: 1127: 1124: 1122: 1117: 1115: 1100: 1099: 1098: 1097: 1096: 1094: 1089: 1087: 1083: 1079: 1075: 1070: 1068: 1064: 1060: 1056: 1051: 1046: 1036: 1033: 1028: 1027: 1026: 1025: 1024: 1023: 1022: 1021: 1014: 1010: 1006: 1002: 998: 997: 996: 995: 994: 993: 988: 985: 980: 979: 978: 977: 974: 970: 966: 962: 961: 952: 951: 950: 949: 948: 947: 940: 939: 938: 937: 933: 929: 925: 924: 913: 912: 911: 910: 909: 908: 907: 906: 898: 897: 896: 895: 894: 893: 886: 885: 884: 883: 874: 871: 866: 865: 864: 863: 862: 861: 860: 859: 850: 846: 845: 844: 843: 842: 841: 832: 831: 826: 824: 823: 818: 816: 813: 811: 808: 806: 803: 801: 798: 797: 796: 795: 794: 793: 792: 791: 783: 782: 781: 780: 779: 778: 771: 770: 769: 768: 764: 763: 759: 755: 754: 750: 746: 745: 744: 743: 740: 728: 724: 720: 719: 718: 717: 716: 715: 710: 707: 703: 702: 701: 700: 697: 693: 689: 684: 683: 682: 678: 672: 670: 669: 665: 661: 657: 650: 647: 643: 642: 636: 635:Formulation 1 632: 628: 627: 626: 625: 609: 606: 601: 598: 594: 590: 589: 588: 584: 580: 575: 572: 571: 570: 569: 568: 567: 566: 565: 564: 563: 562: 561: 548: 545: 541: 540: 539: 538: 537: 536: 535: 534: 533: 532: 531: 530: 517: 514: 513:Formulation 1 510: 509: 504: 503: 502: 498: 494: 490: 488: 481: 476: 475: 474: 473: 472: 471: 470: 469: 462: 459: 454: 453: 452: 451: 450: 449: 439: 435: 431: 427: 422: 421: 420: 419: 418: 417: 416: 415: 407: 406: 405: 401: 397: 393: 389: 382: 378: 377: 374: 373: 371: 369: 363: 362: 361: 360: 359: 358: 355: 346: 343: 340: 337: 334: 331: 328: 325: 324: 323: 321: 314: 310: 309: 308: 306: 302: 294: 288: 284: 280: 275: 274: 273: 272: 269: 265: 261: 257: 252: 251: 247: 243: 239: 235: 231: 230: 227: 223: 222: 218: 214: 213: 208: 207: 206: 205: 201: 197: 193: 185: 170: 166: 160: 157: 156: 153: 136: 132: 128: 127: 119: 113: 108: 106: 103: 99: 98: 94: 88: 85: 82: 78: 73: 69: 63: 55: 51: 46: 45: 37: 33: 29: 25: 22: 18: 17: 3632: 3618: 3611: 3604: 3538: 3300: 3293: 3106: 3055:Next state: 3046:Next state: 3013: 2999: 2988: 2981: 2973: 2966: 2949: 2932: 2915: 2700: 2631:Next state: 2622:Next state: 2613:Next state: 2569: 2544: 2519: 2494: 2489:Next state: 2480:Next state: 2438: 2434: 2429:Aug 17, 2006 2366: 2309: 2305: 2284: 2233:4.232.96.249 2228: 2224: 2218: 2217: 2213: 2187: 2182: 2154: 2153: 2126: 2091: 2076: 2061: 2040: 2017: 2013: 2006: 1988: 1984: 1942: 1938: 1920: 1918: 1913: 1910: 1871: 1867: 1844: 1816: 1812: 1801: 1787: 1783: 1781: 1763: 1742: 1737: 1733: 1692: 1687: 1684:For CMummert 1683: 1682: 1663: 1659: 1655: 1651: 1647: 1643: 1621: 1617: 1599: 1576: 1452: 1285: 1280: 1275: 1267: 1258: 1247: 1202: 1200: 1180: 1163: 1153: 1151: 1146: 1142: 1138: 1134: 1132: 1128: 1125: 1118: 1113: 1111: 1102:|, 2 -: --> 1092: 1090: 1085: 1081: 1077: 1073: 1071: 1052: 1050: 1004: 1000: 964: 848: 829: 827: 821: 819: 814: 809: 804: 799: 757: 749:Wang program 735: 679: 676: 655: 653: 634: 630: 543: 512: 486: 484: 479: 437: 433: 429: 425: 391: 367: 365: 351: 319: 317: 304: 298: 255: 241: 237: 233: 225: 216: 189: 165:Low-priority 164: 124: 90:Low‑priority 68:WikiProjects 35: 3587:Jump-to #: 3437:Jump-to #: 3214:Jump-to #: 3052:Move tape: 3043:Move tape: 2704:busy beaver 2628:Move tape: 2619:Move tape: 2610:Move tape: 2572:busy beaver 2486:Move tape: 2477:Move tape: 2441:state table 2214:summarising 2092:Turing-Post 1825:in.wvbailey 1291:C, B -: --> 1290:B, A -: --> 1289:C, A -: --> 1190:error": --> 1147:never halts 1055:Alan Turing 140:Mathematics 131:mathematics 87:Mathematics 3683:Categories 1937:In Post's 1921:explicitly 1914:sequential 1600:successful 1381:specified. 932:Böhm's P′′ 815:move right 596:phrase.... 392:nonhalting 307:policy"). 2377:model.... 1800:Kleene's 1743:machine W 1084:and the ( 810:move left 546:4, 63-92. 487:terminate 381:universal 3666:Wvbailey 3650:Wvbailey 3621:Wvbailey 3619:wvbailey 3002:Wvbailey 3000:wvbailey 2415:Wvbailey 2401:Wvbailey 2385:Wvbailey 2314:Wvbailey 2259:Wvbailey 2193:Wvbailey 2188:absolute 2183:relative 2137:wvbailey 2132:Wvbailey 2065:Wvbailey 1967:Wvbailey 1926:Wvbailey 1891:Wvbailey 1827:Wvbailey 1792:Wvbailey 1772:Wvbailey 1721:Wvbailey 1669:CMummert 1581:Wvbailey 1560:CMummert 1482:CMummert 1427:Wvbailey 1399:Wvbailey 1363:Wvbailey 1302:Wvbailey 1234:CMummert 1101:1 -: --> 1032:Wvbailey 984:Wvbailey 870:Wvbailey 739:Wvbailey 706:Wvbailey 646:Wvbailey 610:wvbailey 605:Wvbailey 458:Wvbailey 438:insisted 354:Wvbailey 352:wvbailey 313:Wvbailey 260:Wvbailey 28:deletion 3635:Nl 2304 2229:summary 1815:-- the 1622:correct 1203:write 0 805:write 1 800:write 0 656:another 167:on the 58:B-class 2574:page: 2368:that? 1288:-: --> 1283:-: --> 1278:-: --> 1063:binary 847:where 660:r.e.s. 631:Post's 579:r.e.s. 493:r.e.s. 396:r.e.s. 242:Editor 64:scale. 2695:HALT 2564:HALT 2427:pmuet 2370:pmuet 1734:after 1135:blank 1114:unary 1059:unary 954:loop. 480:posed 196:Rgrig 3670:talk 3654:talk 3639:talk 2974:The 2439:The 2340:Talk 2160:Talk 2108:Talk 2051:Talk 2030:Talk 1994:Talk 1950:Talk 1902:Talk 1849:Talk 1747:Talk 1697:Talk 1688:does 1458:Talk 1316:Talk 1192:edit 1156:): 1061:and 1009:Talk 1005:very 969:Talk 965:four 723:Talk 692:Talk 664:Talk 583:Talk 497:Talk 400:Talk 394:!)-- 299:See 283:talk 264:talk 200:talk 36:keep 34:was 3597:17 3590:20 3579:J1 3570:J0 3562:20 3559:19 3556:18 3553:17 3550:16 3483:17 3476:20 3471:15 3457:12 3429:J1 3420:J0 3396:J1 3375:J1 3367:20 3364:19 3361:18 3358:17 3355:16 3352:15 3349:14 3346:13 3343:12 3340:11 3337:10 3248:15 3234:12 3188:J1 3167:J1 3159:15 3156:14 3153:13 3150:12 3147:11 3144:10 2905:22 2891:19 2874:12 2864:15 2828:J1 2807:J1 2786:J0 2778:22 2775:21 2772:20 2769:19 2766:18 2763:17 2760:16 2757:15 2754:14 2751:13 2748:12 2745:11 2742:10 2127:the 1943:any 1868:not 1817:i/o 1738:vs. 1693:ala 1284:B, 1279:A, 1001:any 159:Low 3685:: 3672:) 3656:) 3641:) 3582:H 3576:R 3573:E 3523:* 3508:B 3493:A 3464:1 3454:8 3447:8 3440:5 3432:H 3426:R 3423:E 3417:L 3414:J 3411:N 3408:P 3405:J 3402:L 3399:P 3393:J 3390:L 3387:P 3384:J 3381:R 3378:P 3334:9 3331:8 3328:7 3325:6 3322:5 3319:4 3316:3 3313:2 3310:1 3288:H 3273:B 3258:A 3241:1 3231:8 3224:8 3217:5 3209:H 3206:J 3203:N 3200:P 3197:J 3194:L 3191:P 3185:J 3182:L 3179:P 3176:J 3173:R 3170:P 3141:9 3138:8 3135:7 3132:6 3129:5 3126:4 3123:3 3120:2 3117:1 3101:H 3098:N 3095:1 3092:B 3089:L 3086:1 3078:A 3075:L 3072:1 3069:B 3066:R 3063:1 2898:8 2888:8 2881:1 2871:8 2857:5 2849:H 2846:J 2843:R 2840:P 2837:J 2834:L 2831:P 2825:J 2822:R 2819:P 2816:J 2813:L 2810:P 2804:J 2801:R 2798:P 2795:J 2792:L 2789:P 2739:9 2736:8 2733:7 2730:6 2727:5 2724:4 2721:3 2718:2 2715:1 2692:N 2689:1 2686:B 2683:R 2680:1 2677:C 2674:L 2671:1 2663:B 2660:L 2657:1 2654:A 2651:L 2648:1 2645:B 2642:R 2639:1 2561:R 2558:1 2555:B 2552:L 2549:1 2539:B 2536:R 2533:1 2530:A 2527:L 2524:1 2514:C 2511:L 2508:1 2505:B 2502:R 2499:1 2342:) 2162:) 2110:) 2053:) 2032:) 1996:) 1952:) 1904:) 1851:) 1845:is 1749:) 1699:) 1618:do 1511:.1 1505:λ 1460:) 1346:.1 1340:λ 1318:) 1219:.1 1213:λ 1011:) 971:) 725:) 694:) 666:) 585:) 577:-- 499:) 402:) 285:) 266:) 202:) 3668:( 3652:( 3637:( 2967:H 2950:C 2933:B 2916:A 2545:C 2520:B 2495:A 2443:( 2287:. 2223:" 2219:s 2155:s 1664:n 1660:n 1658:( 1656:f 1652:n 1648:f 1577:0 1546:1 1543:= 1540:) 1537:x 1534:( 1531:f 1508:x 1343:x 1292:C 1286:0 1281:0 1276:0 1268:0 1261:. 1216:x 1196:] 1143:n 1139:n 1093:1 1086:n 1082:n 1078:n 830:j 822:i 662:( 581:( 515:: 495:( 434:n 430:n 398:( 383:. 281:( 262:( 198:( 171:. 70:: 38:.

Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.

Index